学步园

二叉树的遍历算法在其他树操作的基础

已知先序和中序求二叉树的后序遍历算法核心是

1、从先序遍历中读入根节点
2、从中序遍历中找到与根节点相等的元素，以此节点将中序序列分成两个部分，左边的为二叉树的
   左子树，右边为二叉树的右子树；
3、递归调用上述步骤得到根节点的左右子树

＃include<stdio.h><br /> ＃include<malloc.h><br /> ＃include<string.h><br /> typedef struct node<br /> {<br /> char ch;<br /> struct node *left,*right;<br /> }node; // 定义节点的结构<br /> node * creat(char *pre,char *in,int len);<br /> void print(node *head);<br /> int main()<br /> {<br /> int i,j,k,m,n,len;<br /> char pre[30],in[30]; // 存储先序和中序遍历的序列<br /> node *head;<br /> head=(node*)malloc(sizeof(node));<br /> while(scanf("%s%s",pre,in)!=EOF)<br /> { len=strlen(pre);<br /> head=creat(pre,in,len);<br /> print(head);<br /> printf("/n");<br /> }<br /> return 0;<br /> }<br /> node * creat(char *pre,char *in,int len) // 创建后序遍历的函数<br /> { int k;<br /> if(len<=0) return NULL;<br /> node *head=(node*)malloc(sizeof(node));<br /> head->ch=*pre;<br /> char *p;<br /> for(p=in;p!=NULL;p++)<br /> if(*p==*pre) break; // 在中序遍历的序列中得到与先序相同的节点<br /> k=p-in;<br /> head->left=creat(pre+1,in,k); //递归调用得到左子树<br /> head->right=creat(pre+k+1,p+1,len-k-1);//得到右子树<br /> return head;<br /> }<br /> void print(node *head) // 打印后序遍历序列<br /> {<br /> if(head==NULL) return ;<br /> print(head->left);<br /> print(head->right);<br /> printf("%c",head->ch);<br /> }