数据结构考研分类复习真题 第六章 答案 (五)[35]

[题目分析]按题目要求每个结点的编号大于其左右孩子的编号结点左孩子的编号小于右孩子的编号由此看出从小到大按左右根顺序这正是后序遍序的顺序故对二叉树进行后序遍历在遍历中对结点进行编号现将二叉树结点结构定义如下

typedef struct node

{ElemType data; int num; struct node *lchild *rchild; }Bnode*Btree

void PostOrder(Btree t)

//对二叉树从开始编号结点编号大于其左右子女结点编号结点的左子女编号小于其右子女编号

{typedef struct {Btree t; int tag; }node;

Btree p=t; node sns[]; //s为栈容量足够大

int k=top=; //k为结点编号top为栈顶指针

while(p!=null || top>)

{while(p) {snt=p; sntag=; s[++top]=sn; p=p>lchild;} //沿左分枝向下

while(top> && s[top]tag==){sn=s[top];snt>num=++k;}//左右孩子已遍历结点赋编号

if (top>) {s[top]tag=; p=s[top]t>rchild;}

}//while(p!=null || top>)

}结束PostOrder

[题目分析]非递归算法参考上面第题下面给出递归算法

void PreInCreat(BiTree rootElemType pre[]in[]int lhlh)

//根据二叉树前序序列pre和中序序列in建立二叉树lhlh是序列第一和最后元素下标

{root=(BiTree)malloc(sizeof(BiNode)); //申请结点

root>data=pre[l]; //pre[l]是根

for(i=l;i<=h;i++) if(in[i]==pre[l]) break; //在中序序列中根结点将树分成左右子树

if(i==l) root>lchild=null; //无左子树

else PreInCreat(root>lchildpreinl+l+(il)li) //递归建立左子树

if(i==h) root>rchild=null; //无右子树

else PreInCreat((root)>rchildpreinl+(il)+hi+h) //递归建立右子树

}//结束PreInCreat

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []