通软答辩_二叉树遍历问题

1、通信软件基础选题：5 二叉树练习小组成员：三枚铜钱94keyboard 时间：2015/6/1实训答辩二叉树练习THE LAST TIME二叉树练习 以先序输入方式创建二叉树； 对该二叉树进行先序遍历； 用程序实现由先序序列和中序序列确定该二叉树；1分析问题2确定框架3实现程序1分析问题p 算法思想：p 先序创建二叉树 若二叉树为空，返回空，创建结束；否则进行以下操作1) 输入根节点；2) 先序递归 输入创建根节点的左子树；3) 先序递归 输入创建根节点的右子列；分析1p 使用递归的方法，实现二叉树的前序输入创建及遍历p 输入：一颗树的前序遍历，用#代替节点的左（右）孩子为空p 例如，前序序列

2、：ABD#E#C#ABCDE#p 算法思想：p 先序遍历二叉树 若二叉树为空，遍历结束；否则进行以下操作1) 访问根节点；2) 先序遍历根节点的左子树；3) 先序遍历根节点的右子列；分析2p 一个先序遍历序列和一个中序遍历序列可以确定一颗唯一的二叉树。 u 根据先序遍历的特点可知先序序列(DLR)的首个元素(Pre 0)为二叉树的根(root)u 然后在中序序列(LDR)中查找此根(root)u 根据中序遍历特点可知在查找到的根(root) 前边的序列为根的左子树的中序遍历序列, 后边的序列为根的右子树的中序遍历序列 u 设在中序遍历序列(LDR)根前边有left个元素，则在前序序列(DLR)

3、中，紧跟着根(root)的left个元素序列(即Pre 1.left) 为根的左子树的先序遍历序列，在后边的为根的右子树的先序遍历序列；而构造左子树问题其实跟构造整个二叉树问题一样，只是此时前序序列为Pre 1.left)，中序序列为In 0.left-1，分别为原序列的子串，构造右子树同样， 显然可以用递归方法解决 先序： root | 左子树 | 右子树 中序： 左子树 | root | 右子树p 递归实现： 递归函数输入：二叉树的先序序列和中序序列；返回：建好的二叉树的根节点。p 算法思想：1) 若二叉树空，返回空；2) 若不空，取先序序列第一个元素，建立根节点；3) 在中序序列中查找根

4、节点，以此确定左右子树的先序序列和中序序列；4) 递归调用自己，建左子树；5) 递归调用自己，建右子树。 1定义字符指针变量指向字符串2输入前序、中序序列的字符串3递归实现恢复二叉树4后序遍历以确定二叉树p 确定二叉树的方法： 恢复二叉树后对它进行后序遍历 来确定唯一的二叉树；2确定框架开始Flag=1Flag=0?是否你的输入有误 ;Switch(case)DLRcreat（）；结束case=1 case=2case=3default否否否BTreeFronMid()；LRD(tree);Flag=-1；break ;是是是是/按照前序遍历的顺序创建二叉树BTNode *CreateTree

5、( ) 创建根节点； CreateTree (左子树)； CreateTree (右子树)； /先序+中序恢复二叉树，递归MakeBTree(.) 得到root 根结点 MakeBTree( 左子树 ); MakeBTree( 右子树 ); 是否root=NULL;return;当前节点创建为 root当前节点=NULL ?当前节点指向左子树开始当前节点指向右子树结束 / 按照前序遍历的顺序创建二叉树节点 getroot(前序，中序)c= （前序第 0 个字符）pos= （c 在中序中的位置）len1= 中序pos左半部分长度len2= 中序pos右半部分长度新建节点 r，令 r 的元素等于c

6、r 的左儿子=getroot(前序位置1开始的len1长度部分，中序pos位置的左半部分)r 的右儿子=getroot(前序位置len1的右半部分，中序pos位置的右半部分)return rfm/ 先序+中序恢复二叉树，递归fl=0; fr=strlen(f);ml=0; mr=strlen(m);建立左子树 递归调用参数设置 fl+1；fl+pos-ml；ml；pos-1m序列长度 ?是否m序列中 pos从当前序列首个位置ml移动到 fl元素在m序列的位置左、右子树设为NULL否当前前序序列的第 fl 个元素创建为根节点是开始m序列长度1 ?pos过序列边界？fl 移动至左子树序列尾；建立右

7、子树 递归调用 参数设置 fl+1；fr；pos+1；mr输入错误结束结束否是3实现程序/ 二叉树的节点定义typedef struct node char data; struct node *rchild; / 左孩子节点struct node *lchild; / 右孩子节点 BTNode,*TNode; / 树的初始化void Init(BTNode *t) t-lchild = NULL; t-rchild=t-lchild;BTNode *DLRcreate() /先序输入建立二叉树 char ch;BTNode *root;ch=getchar();if(ch=#) root=N

8、ULL; /读入#，返回空指针else / 生成节点 root=(BTNode *)malloc(sizeof(BTNode); root-data=ch; /节点数据root-lchild=DLRcreate(); /构造左子树root-rchild=DLRcreate(); /构造右子树return root;二叉树创建 LRD(TNode tree) /后序查找 if (tree!=NULL) LRD(tree-lchild); LRD(tree-rchild); printf(%c,tree-data); void DLR(BTNode *t) /先序遍历 if(t=NULL) ret

9、urn; printf(%c,t-data); DLR(t-lchild); DLR(t-rchild); freetree(TNode tree) /释放树 if (tree!=NULL) freetree(tree-lchild); freetree(tree-rchild); 二叉树基本操作算法BTreeFronMid ( TNode *tree,char *Fron,char *Mid,int fl,int fr,int ml,int mr ) int pos; if (mldata=Fronfl;/本棵树根节点确定即先序第一个元素(*tree)-lchild=NULL; (*tree

10、)-rchild=NULL;if (mlmr) pos=ml;while(Midpos!=Fronfl&poslchild),Fron,Mid,fl+1,fl+pos-ml,ml,pos-1); /建左子树fl+=pos-ml;BTreeFronMid(&(*tree)-rchild),Fron,Mid,fl+1,fr,pos+1,mr); /建右子树 / 根据前序序列中序序列恢复唯一的二叉树/定义二叉树根节点指针TNode *tree；/前序、中序字符串指针char char *Fron，char *Mid；/前序序列位置号（开始、结束位置）int fl，int fr；/中序序列位置号（开始

11、、结束位置）int ml，int mr void main() int i, cycle=0; / 选择和结束标志位 BTNode *t; TNode tree=NULL; char *Fronarr=(char*)malloc(sizeof(char)*50); /前序序列 char *midarr=(char*)malloc(sizeof(char)*50); /中序序列 while(cycle!=(-1) printf(*n); printf(“ 先序创建并先序输出 请按：1n); printf( 由先序中序确定二叉树并后序输出 请按：2n); printf(“ 退出 请按：3nn);

12、printf(*n); 主函数/将创建二叉树的函数的首地址赋给指针变量t;/前序遍历t; printf(n); printf(请选择你的操作：n);scanf(%d,&i);switch(i) case 1: printf(input the string:);t=DLRcreate();printf(The preorder is:);DLR(t); printf(n); break;调用恢复二叉树函数；p 输入前序，中序序列p 判断两个序列长度是否一致p 调用函数恢复二叉树p 后序遍历二叉树p 释放二叉树case 2:while(1) printf(Please input preorde

13、r:);scanf(%s,Fronarr);printf(Please input midorder:);scanf(%s,midarr);if (strlen(Fronarr)!=strlen(midarr)printf(wrong input! Please input agin!n);else break; BTreeFronMid (&tree,Fronarr,midarr,0, strlen(Fronarr)-1,0,strlen(midarr)-1);printf(Postorder is:);poster(tree);printf(n);freetree(tree);break;指定 输入3 为退出程序若输入非指定（1、2、3外）值，提示输入有误，重新输入case 3:cycle=(-1);break;default:printf(n); printf(你的输入有误!n);printf(n Press Enter Contiue! n);getchar();while(getchar()!=n);break;调试 1p 例如，前