1.問題描述：
? ? 1 .由已經(jīng)給出的二叉樹的先序（后序）和中序遍歷的結(jié)果構(gòu)造二叉樹。遍歷的結(jié)果以數(shù)組的方 ? 式輸入。
? ? ?2.給定任意一棵二叉樹，使用隊列作為輔助儲存，按樹的結(jié)點(diǎn)的深度，從根開始依次訪問所有結(jié)點(diǎn).
設(shè)計用例：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 先序：abdecfg ? ? ? ? ? ? ? ? ? ? ? ? ? 中序：dbeafcg
設(shè)計代碼：
#defineLEN20
typedefcharElementtype;
typedefstructTreeNode*T;
typedefstructTreeNode*Position;
typedefstructQueueRecord*Queue;
structTreeNode
{
Elementtypedata;
Positionlchild;
Positionrchild;
};
structQueueRecord
{
intCapacity;
intFront;
intRear;
intSize;
PositionnodeArr[LEN];
};
intmain() {
voidinput (char*preArr,char*midArr);
voidbuildTree(Tt,char*preArr,char*midArr,intlength);
PositioncreateNode();
voidinitQueue(QueueQ);
voidoutputQueue(QueueQ);
charpreArr[LEN],midArr[LEN];
Ttree = createNode();
Queuequeue = (Queue)malloc(sizeof(structQueueRecord));
voidtree_to_queue(Tt,QueueQ);
input(preArr, midArr);
buildTree(tree, preArr, midArr,strlen(preArr));
initQueue(queue);
tree_to_queue(tree,queue);
outputQueue(queue);
getchar(); getchar();
return;
}
voidinput(charpreArr[],charmidArr[]) {
scanf_s("%s",preArr);
scanf_s("%s",midArr);
}
voidbuildTree(Tt,char*preArr,char*midArr,intlength)//t需要有明確的指向
{
intindexOf(char*arr,charx);
PositioncreateNode();
if(0 == strlen(preArr) || 0 == strlen(midArr))
{
t=NULL;
return;
}
Ttree =t;
tree->data =preArr[0];
intindex =
indexOf(midArr,preArr[0]);
intl_length =index;
intr_length =length- 1 - index;
if(l_length >0)
{
tree->lchild = createNode();
buildTree(tree->lchild,preArr+ 1,midArr, l_length);//midArr只是用了一部分;
}
else{
tree->lchild =NULL;
}
tree =t;
if(r_length >0)
{
tree->rchild = createNode();
buildTree(tree->rchild,preArr+ l_length+1,midArr+ 1 + l_length, r_length);
}
else{
tree->rchild =NULL;
}
tree =t;
}
voidpre_travel(Tt)
{
if(t==NULL) {
return;
}
else{
printf("%c",t->data);
pre_travel(t->lchild);
pre_travel(t->rchild);
}
}
voidmid_travel(Tt) {
if(t==NULL) {
return;
}
else{
mid_travel(t->lchild);
printf("%c",t->data);
mid_travel(t->rchild);
}
}
voidtree_to_queue(Tt,QueueQ)
{
intenterQueue(QueueQ,Positionp);
intl_index,r_index;
l_index = 1;
r_index = 1;
intf=enterQueue(Q,t);
while(l_index <=r_index)
{
if(enterQueue(Q, (Q->nodeArr[l_index])->lchild))
{
r_index++;
}
if(enterQueue(Q, (Q->nodeArr[l_index])->rchild))
{
r_index++;
}
l_index++;
}
}
PositioncreateNode()
{
return(Position)malloc(sizeof(structTreeNode));
}
intindexOf(char*arr,charx)
{
intindex = -1;
for(inti = 0; i < strlen(arr); i++)
{
if(x==arr[i])
{
index = i;
break;
}
}
returnindex;
}
voidinitQueue(QueueQ) {
Q->Capacity =50;
Q->Size = 0;
Q->Front = 1;
Q->Rear = 0;//從索引1開始存儲
}
intenterQueue(QueueQ,Positionp)
{
if(NULL==p) {
return0;
}
else{
Q->Size++;
Q->Rear++;
Q->nodeArr[Q->Rear] =p;
return1;
}
}
voidoutputQueue(QueueQ)
{
for(inti = 1; i <=Q->Size; i++)
{
printf("%c", (Q->nodeArr[i])->data);
}
}
樹的結(jié)構(gòu)：
隊列結(jié)構(gòu)：
