二叉树的遍历以及树与二叉树的转换课程设计

1、课程设计（数据结构）院、系 专业 姓名学号指导教师2010年 月 日树的应用摘要：关键词：树；二叉树；转换；遍历；递归和非递归1实验题目 实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实 现，应包含建树的实现。2实验分析21 总体分析2.1.1 本程序的功能是对任意二叉树进行递归前序遍历和后序遍历，用栈实现非递归的前序、和后序 遍历，还有对树的层序遍历以及树与二叉树的转换。2.1.2 本程序要求用户以字符输入，若要实现终端结点，最后以回车键建入数据。2.1.3 本程序的结果将依次打印出递归前序遍历和后序遍历，用栈实现非递归的前序和中序遍历和后 序遍历，和

2、线索化层序遍历，输入树及树传换成二叉树。2.2 具体分析2.2.1 二叉树创建2*i+1 的值存入左孩子，用链表实现创建一个树结点的结构体，从键盘输入数据，存入数组。把下标为为 2*i+2 的存入右孩子。 BiNode creat() ， BiNode stree_creat(char *a,int k)2.2.2 先序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）访问根结点；（ 2）先序遍历左子树；（ 3）先序遍历右子树。11void PreOrder(BiNode root) 。2.2.3 中序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）中序遍历左子树；（ 2 ）访问根结

3、点；（ 3）中序遍历右子树。void InOrder(BiNode root) 。2.2.4 后序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）后序遍历左子树；（ 2 ）后序遍历右子树。（3）访问根结点；void PostOrder(BiNode root)2.2.5 先序非递归算法BiNode 根指针，若 BiNode!= NULL 对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。 问题：如何用栈来保存信息， 使得在先序遍历过左子树后， 能利用栈顶信息获取 BiNode 的右子树的 根指针？ void F_PreOrder(BiNode root)2.2.6 中序非递归算法BiN

4、ode 是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。 问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取 BiNode 指针？ void F_inOrder(BiNode root) 。2.2.7 后序非递归算法BiNode 是要遍历树的根指针， 后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右 子树是否均遍历过。 void F_PostOrder(BiNode root) 。2.2.8 层次序遍历算法按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。VoidLevelOrder(BiNode root) 。2.2

5、.9 树与二叉树的转换算法转换时结点的第一个孩子变为它的左孩子， 兄弟节点变为他的有孩子。 Void exchange() ， class Tree.3. 实验步骤3.1 流程图图1、二叉树的创建图2、前序递归遍历图3、中序递归遍历图5、前序非递归遍历开始图7、后序非递归遍历图8、层序遍历3.2代码：#in ClUdeVioStream>USing n amespace std;#in clude<stdlib.h>#in clude<math.h>#defi ne maxsize 100#i nclude "tree.h"#define LE

6、N SiZeOf(StrUCt btree)int max=1;typedef StrUCt btree /二叉树节点结构体btree *lchild,*rchild;char data;*BiNode;typedef struct StackElemType/ 栈的结构体BiNode ptr;int flag;StackElemType;BiNode p ;/ 二叉树的建立BiNode stree_creat(char *a,int k)BiNode root; max+;if(ak='0'|k>maxsize)return NULL; / 判断树是否为空elseroo

7、t=(BiNode)malloc(LEN);/ 动态申请节点root->data=ak;root->lchild=stree_creat(a,2*k+1); /递归调用为左孩子赋值root->rchild=stree_creat(a,2*k+2); /递归调用为右子赋值return root;/ 返回根节点指针void print(BiNode root) / 输出所创建的二叉树BiNode hmaxsize=NULL;int top=0,base=0,j=0,k=0,n=0,m=0;htop=root;j=log(max+1)log (2)-1;if(pow(2,j+1)-

8、1<max) j+;cout<<"你刚输入的是：n"while(hbase!=NULL) /把二叉树的值依次存入数组h+top=hbase->lchild;h+top=hbase->rchild;base+;for(top=0;hk!=NULL;top+)按层输出m=pow(2,j)-top;/计算每行输出的空格数Jif(top!=0) m=m-top;for(n=0;n<m;n+)cout<<""for(base=0;base<pow(2,top)&&hk!=NULL;base+)控

9、制每层输出的个数if(hk->data='0') cout<<""<<""/当为空时输出else cout<<hk->data<<""k+;cout<<"n"for(n=0;n<( m-1); n+)cout<<""for(base=0;base<pow(2,top) &&hk!=NULL;base+)cout<<""<<&q

10、uot;"cout<<"n"/ 二叉树的后序遍历递归算法void PostOrder(BiNode root)if(root=NULL)return;/ 递归调用的约束条件 elsePostOrder(root->lchild);PostOrder(root->rchild);if(root->data='0') ;else cout<<""<<root->data<<""/ 二叉树的中序遍历递归算法void InOrder(BiNode

11、 root)if(root=NULL)return;/ 递归调用的约束条件elseInOrder(root->lchild);if(root->data='0') ;else cout<<""<<root->data<<""InOrder(root->rchild);/ 二叉树的前序递归遍历算法void PreOrder(BiNode root)if(root=NULL)return;/ 递归调用的约束条件elseif(root->data='0') ;el

12、secout<<""<<root->data<<""PreOrder(root->lchild);PreOrder(root->rchild);/ 二叉树的前序遍历非递归算法void F_PreOrder(BiNode root)BiNode smaxsize;/ 申请一个 BiNode 数组int top=0;/ 采用顺序栈，并假定不会发生上溢dowhile(root!=NULL)/ 当结点不为空时if(root->data='0') ;elsecout<<&quo

13、t;"<<root->data<<""s+top=root;/ 依次将结点压入栈root=root->lchild;/ 根赋值为它的左孩子if(top>0)/ 当节点为空但栈顶不为零时root=stop-;栈顶下移把栈顶元素负给根结点root=root->rchild; 根赋值为它的右子while(root!=NULL|top>0);/ 中序非递归遍历算法void F_inOrder(BiNode root)BiNode smaxsize; /申请一个 BiNode 数组int top=0; / 采用顺序栈，并

14、假定不会发生上溢dowhile(root!=NULL) / 当结点不为空时s+top = root; /依次将结点压入栈root = root->lchild; / 根赋值为它的左孩子if(top>0) / 当节点为空但栈顶不为零时root = stop;把栈顶元素负给根结点if(root->data='0') ;else cout<<""<<root->data<<""/ 输出根结点root=stop-;栈顶下移把栈顶元素负给根结点root=root->rchild; 根

15、赋值为它的右子while(root!=NULL|top>0);/ 后序非递归遍历算法void F_PostOrder(BiNode root); 申请一个 StackElemType 数组BiNode p=root;int top = 0;dowhile(p!=NULL) / 当结点不为空时stop.flag = 0;/ 标记位负为零stop.ptr = p;/ 将树的结点依次压入栈中 17p=p->lchild;/ 树沿左子树下移 top+;while(stop-1.flag = 1)/当栈的最上面元素标记位为一时输出 if( stop-1.ptr->data='0

16、') top-;elsecout<<""<<s-top.ptr->data<<""if(top>0) / 当节点为空但栈顶不为零时stop-1.flag = 1; 栈的最上面元素标记位赋值为一 p = stop-1.ptr; 栈的最上面元素树结点赋给 p p = p->rchild; 树沿右子树下移 while(top>0);/ 层序遍算法void LevelOrder(BiNode root)BiNode smaxsize; / 申请一个 BiNode 数组int max,i=0;s0

17、= root;/ 数组首元赋为根结点 while(root!=NULL)/ 当结点不空时s2*i+1 = root->lchild;/ 左孩子赋给下标为 2*i+1 的数组员 s2*i+2 = root->rchild; / 右孩子赋给下标为 2*i+1 的数组员 i+;root = si;/root变为当前数组元素的值max = i;18for( i=0;i<max;i+)if(si->data='0') ;elsecout<<""<<si->data<<""/ 依次输出

18、void Pause()cout<<endl<<endl<<endl;system("pause");cout<<endl<<endl<<endl;/ 树转换为二叉树void exchange()Tree<char> myTree1;/ 实例化一个 Tree classmyTree1.InputTree();/ 调用 InputTree() 函数Pause();myTree1.ShowTree();/ 调用 ShowTree() 函数Pause();myTree1.Show_BinaryTr

19、ee();/ 调用 Show_BinaryTree() 函数Pause();/ 输入二叉树信息的函数BiNode creat()BiNode p=NULL ;cout<<" 请输入你的二叉树 ( 请按层次由上往下从左到右依次输入并按#结束，如果节点为空请输入 '0',本遍历器仅支持单字符 ), 输入为 :n" int i=0,j=0;char bmaxsize='#',n ;/ 当输入不为 '#' 时给数组赋值 docin>>n;if(n!='#') bi=n;i+;while(n!=&

20、#39;#');p=stree_creat(b,0);/ 创建树 print(p);/ 输出树 return p;/ 主函数int main()int k;cout<<"n "cout<<"nJ欢迎使用树的多种遍历器树与二叉树的转换cout<<" | |"cout<<" | |"cout<<"|"cout<<"n"docout<<"n "cout<<"n

21、1.创建二叉树 "cout<<"n2.前序递归遍历算法cout<<"n3.中序递归遍历算法cout<<"n4.后序递归遍历算法cout<<"n5.前序非递归遍历算法cout<<"n6.中序非递归遍历算法cout<<"n7.后序非递归遍历算法cout<<"n8.层序非递归遍历算法cout<<"n9.树与二叉树的转换cout<<"n10.退出操作 n"cout<<&quo

22、t;请选择你要进行的操作（ 数字键 ） ： "cin>>k;switch(k)case 1:p=creat();/ 调用 creat() 创建二叉树break;case 2:cout<<" 二叉树的前序递归遍历 :"PreOrder(p)； / 调用 PreOrder(p) 前序遍历 break;case 3:cout<<" 二叉树的中序递归遍历 :"InOrder(p); / 调用 InOrder(p) 中序遍历 break;case 4:cout<<" 二叉树的后序递归遍历 :&qu

23、ot;PostOrder(p); /调用 PostOrder(p) 后序遍历29 break;二叉树前序非递归遍历 :"调用 F_PreOrder(p) 前序遍历二叉树中序非递归遍历 :"调用 F_inOrder(p) 中序遍历二叉树后序非递归遍历 :"二叉树层序非递归遍历调用 exchange() 实现树与二叉树的转换返回主函数case 5:cout<<"F_PreOrder(p); /break;case 6:cout<<"F_inOrder(p); /break;case 7:cout<<"F

24、_PostOrder(p);break;case 8:cout<<"LevelOrder(p);break;case 9:exchange();/delete p;return main();/break;while(k>=0 && k<9);return 0;3.3 截图界面1.运行程序出现以下界面阿与二叉柯的艇器it4. l历聲搭5. F'JJ 力宾茫6. =PJ 7- 泄归匾（S丄叫退出-噪倍 胃诙择氓娈戈tE勺礁作祎時舉肌丄kii由上往下从左到右依柱输入并按谑裁单学肃输入丸”如尹产点詞空请输IhRlIiI=! fu ra5期输心是, 4m 历历历遍遍漏时 村遍遍一Ln戸戸口心 VBF I 一 ¾ n 刨前胃W中后层卡Fl与岀2D.; 历历历 悝sw 叉归归归 二月勇首 filr中戶 一旦 12 3 4-2. 输入1选择创建二叉树3. 输出树，输入2选择前序递归遍历运-J i3jfe 暹!弓遍厉I- 厉LF厉遍遍遍遇阳 屈遍诟遍归归归易乍 X归归归递谍孟 一 一當递 b4 刨前中戶就HK层柄鬼> -BB BBp l234 5-fi7B?4:<ll的ild行邊进存t祢旳-fl-s-F.pI:霹:霽与字10 F5 pl 頁选揪禳进行的埋仆偵字檢打3 二叉柝的申rJY