[題目分析]按題目要求每個結點的編號大於其左右孩子的編號結點左孩子的編號小於右孩子的編號由此看出從小到大按左右根順序這正是後序遍序的順序故對二叉樹進行後序遍歷在遍歷中對結點進行編號現將二叉樹結點結構定義如下
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
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23713.html
