软件设计师试题疑难解答之四
问题1:关于二叉树的排序,有这样一个程序:
由二叉树的前序遍历和中序遍历两个遍历序列能唯一确定一棵二叉树.
如前序遍历:a,b,d,e,c,f,g; 中序遍历:d,b,e,a,,c,g,f;如以下事例;
a
b c
d e f
g
本程序实现已知某二叉树的前序遍历和中序遍历序列,生成一棵连接表示的二叉树.
构造二叉树的算法要点是:由前序遍历序列,该序列的第一元素是根接点元素(例中a).该元素将中序遍历序列分成左右两部分,那些位于该元素之前的元素是它的左子树上的元素(如d,b,e);位于该元素之后的元素是它右子树上的元素(如c,g,f);对于左右子树,由他们的前序遍历序列的第一个元素可确定左,右子树的根接点,参照中序遍历序列又可进一步确定子树的左右子树元素.如此递归参照两个遍历序列,最终构造出二叉树
两个遍历序列作为主函数main()的参数.为简单起见,程序假定两个遍历序列是相容的.主函数调用函数restore()建立的二叉树.函数restore()以树(子树)的前序遍历和中序遍历两序列及序列长为参数,采用递归方法建立树(子树).
函数postorder()实现二叉树的后续遍历输出,用来验证函数restore()建立的二叉树.
#include <stadio.h>
#include<stdlib.h>
#define max 100
typedef struct node{
char info;
struct node *llink,*rlink;
}tnode;
char pred[max],inod[max];
tnode restore(char*,char *,int);
main(int argc,char **argv)
{ tnode *root;
if(argc<3)exit(0);
strcpy(pred,argv[1]);
strcpy(inod,argv[2]);
root=restore(pred,inod,strlen(pred));
postorder(root);
printf(“\n\n”);
}
tnode*restore(char*ppos,char*ipos,int n)
// char*ppos为前序列，char*ipos为中序列 ，n为长度
{ tnode *pre;
char *rpos;
int k;
if(n<=0) return null;
ptr=(tndoe *)malloc(sizeof(tndoe));
ptr->info=ppos .info; 1 //确定根节点
for(rpos=ipos;rpos<ipos+n;rpos++) 2
if(*rpos==*ppos)break;
k=ipos+n-rpos; 3
ptr->llink=restore(ppos+1,ipos,k); 4
ptr->rlink=testore(ppos+k, 5
rpos+1,
n-1-k);
return ptr;
}
postorder(tndoe *ptr)
{ if (ptr==null) return;
postorder(ptràllink);
postorder(ptràrlink);
printf(“%c”,ptràinfo);
}
解答：
首先我先说明我的答案是我自己根据题目给出的信息得出的答案，如果你有标准答案可以给我发过来，大家一起研究
看这个题目，主要就是两个序列，说明给的很清楚根据前序的节点划分中序的序列；
比如第一个空，我觉得是先确定根节点也就是前序的第一个点；
然后，遍历中序序列寻找前序的节点，如果找到，那么就递归调用左子树和右子树继续寻找；当然递归调用的参数还是两个序列和序列的长度；
ptr->llink=restore(ppos+1,ipos,k);//左子树，首先前序的根节点已经求出，那么前序序列就从ppos+1开始，中序仍然从ipos开始，，但是长度变化了，变为根节点前的部分序列的长度，因为这个部分才识左子树部分
同样的道理：ptr->rlink=testore(ppos+k, rpos+1, n-1-k)//前序序列从去掉左子树和根节点开始，中序序列就从找到跟节点的后一个位置开始，长度就是n-(k+1)，这样递归就完成了；