最后更新时_(d)(x)2011-12-06 18:17:27
辅导评Q?a target="_blank" rel="nofollow">暑期集训
在线咨询
1Q已知一hn个结点的二叉?wi)的中序遍历序列与后序遍历序列分别存放于数?/span>IN[1Q?/span>n]?/span>POST[1Q?/span>n]中,Q设该二叉树(wi)各结点的数据值均不相同)。请写一建立该二叉树(wi)的二叉链表结构的非递归法。该二叉链表的链l点l构?/span>(lchild,data,rchild)Q其?/span>data为数据域Q?/span>lchild?/span>rhild分别为指向该l点左、右孩子的指针域Q当孩子l点不存在时Q相应指针域为空Q用nil表示Q。?a target="_blank">北京航空航天大学 1998 ?/span> (15?/span>)?/span>
【参考答案?/font>
[题目分析]知二叉树(wi)中序序列与后序序列,W?/span>30题以递归法建立了二叉树(wi)Q本题是非递归法?/span>
void InPostCreat(ElemType IN[],POST[],int l1,h1,l2,h2)
//׃叉树(wi)的中序序?/span>IN[]和后序序?/span>POST[]建立二叉?wi)?/span>l1,h1?/span>l2,h2分别是中序序列和
//后序序列W一和最后元素的下标Q初始调用时Q?/span>l1=l2=1,h1=h2=n?/span>
{typedef struct {int l1,h1,l2,h2; BiTree t; }node;
node s[],p;//s为栈Q容量够大
BiTree bt=(BiTree)malloc(sizeof(BiNode)); int top=0,i;
p.l1=l1; p.h1=h1; p.l2=l2; p.h2=h2; p.t=bt; s[++top]=p;//初始?/span>
while(top>0)
{p=s[top--]; bt=p.t; l1=p.l1; h1=p.h1; l2=p.l2; h2=p.h2;//取出栈顶数据
for(i=l1;i<=h1;i++) if(IN[i]==POST[h2]) break;//在中序序列中查等?/span>POST[h2]的结?/span>
bt->data=POST[h2]; //根结点的?/span>
if(i==l1) bt->lchild=null; //bt无左子树(wi)
else //徏立左子树(wi)的数据入?/span>
{bt->lchild=(BiTree)malloc(sizeof(BiNode)); p.t=bt->lchild;
p.l1=l1; p.h1=i-1; p.l2=l2; p.h2=l2+i-l1-1; s[++top]=p; }
if(i==h1) bt->rchild=null; //bt无右子树(wi)
else {bt->rchild=(BiTree)malloc(sizeof(BiNode)); p.t=bt->rchild;
p.l1=i+1; p.h1=h1; p.l2=l2+i-l1; p.h2=h2-1; s[++top]=p; }//叛_?wi)数据入?/span>
}// while(top>0)
}l束InPostCreat