二叉树的生成与遍历

1、课程设计报告课程名称数据结构课程设计专 业：信息管理与信息系统班 级：姓 名学 号： 指导教师：成 绩：2016 年一 12_ 月 _16_ 日、实验一问题分析和任务定义题目：二叉树的生成和遍历任务：1、将二叉树以广义表形式存储在一个 TXT文件上，通过读取TXT文件,建立二叉树；2、求树的高度；3、实现二叉树的前序、中序和后序遍历；4、将输出结果存储在文件内需求分析：在二叉树的应用中，常常要求在树中查找具有某种特征的结点， 或者 对树中全部结点逐一进行某种处理， 这就是二叉树的遍历问题。对二叉树的数据 结构进行定义，建立一棵二叉树，然后进行各种实验操作。二叉树是一个非线性 结构，遍历时要先明

2、确遍历的规则，先访问根结点还时先访问子树， 然后先访问 左子树还是先访问有右子树，这些要事先定好，因为采用不同的遍历规则会产生 不同的结果。本次实验要实现先序、中序、后序三种遍历。基于二叉树的递归定 义，以及遍历规则，本次实验也采用的是先序遍历的规则进行建树的以及用递归 的方式进行二叉树的遍历。二、逻辑设计：系统总框架图1、构造二叉树，本程序构造二叉树所输入广义表为a（b（d，e）,c （，f）2、遍历功能模块 可以通过要求对所构造的二叉树进行先序遍历、中序遍 历、后序遍历，广度优先遍历。3、求二叉树的深度。功能设计：1) Struct BTNode() 使用链式存储结构定义一个结构体数组，保

3、存二叉树 的字符信息和定义指向其左孩子和右孩子的指针。2) CreateBTree() 从键盘上输入构造二叉树的字符以 * 表示结点的空孩子。3) PreOrder() 此函数的功能是完成所构造二叉树的先序遍历。4) InOrder()此函数的功能是完成所构造二叉树的中序遍历。5) PostOrder() 此函数的功能是完成所构造二叉树的后序遍历。6) Levelorder ()此函数的功能是完成所构造的二叉树的广度优先遍历7) BTreeDepth() 对构造好的二叉树求其深度。三、详细设计：1、二叉链表由头指针唯一确定，若二叉树为空，则头指针指向空，若结点的某 个孩子不存在，则相应的指针为

4、空。2遍历模块1) 先序遍历：先访问根节点，然后分别遍历左子树，右子树，遍历左子树和右 子树的方法和遍历整个二叉树的方法一样， 而访问根节点是一个固定操作， 所以 可用递归方法实现。遍历的结束条件是二叉树为空。2) 中序遍历：中序遍历的算法思想和先序遍历一样，仅仅是处理结点的次序不 同其思想为，若二叉树为空，则结束遍历操作，否则中序遍历根节点的左子树， 访问根节点中序遍历根结点的右子树。3) 后序遍历：后序遍历的基本思想为，若二叉树为空，则结束遍历操作，否则 后序遍历根结点的左子树，后序遍历根节点的右子树，访问根结点。4) 广度优先遍历：广度优先遍历的思想为，若二叉树为空，则结束遍历操作，否

5、则按层进行遍历。5) 求二叉树的深度。四、程序编码：1、二叉链表由头指针唯一确定，若二叉树为空，则头指针指向空，若结点的某 个孩子不存在，则相应的指针为空。用广义表输出二叉树。源代码：void CreateBTree(struct BTreeNode * BT,char * a)/* 根据 a 所定义的二叉树广义表字符串建立对应的存储结构 */struct BTreeNode * p;/*定义 s 数组作为存储根结点指针的栈使用 */struct BTreeNode * sStackMaxSize;/*定义top作为s栈的栈顶指针，初值为-1，表示空栈*/int top=-1;/*用 k 作为

6、处理结点的左子树和右子树的标记， k=1 处理左子树， k=2 处理右子树 */ int k;/*用i扫描数组a中存储的二叉树广义表字符串，初值为 0*/int i=0;/*把树根指针置为空，即从空树开始建立二叉树 */*BT=NULL;/*每循环一次处理一个字符，直到扫描到字符串结束 0为止*/while (ai)switch(ai)case :/* 对空格不做任何处理 */break;case (:if(top=StackMaxSize -1)printf( 栈空间太小，需增加 StackMaxSize!n);exit(1); top+; stop=p;k=1;break;case ):i

7、f(top=-1)printf( 二叉树广义表字符串错 !n);exit(1);top-;break; case ,:k=2;break;default:p=(struct BTreeNode * )malloc(sizeof(struct BTreeNode);p-data=ai;p-left=p -right=NULL;if(*BT=NULL)*BT=p;elseif(k=1) stop -left=p;elsestop -right=p; /*switch end*/* 为扫描下一个字符串修改 i 值*/i+;void PrintBTree(struct BTreeNode * BT)/

8、* 输出二叉数的广义表表示 */* 数为空时自然结束递归，否则执行如下操作*/if(BT=NULL)/* 输出根结点的值 */printf(%c,BT -data);/* 输出左、右子树 */if(BT -left!=NULL | BT -right!=NULL)printf();/* 输出左括号 */PrintBTree(BT -left); /* 输出左子树 */if(BT -right!=NULL)PrintBTree(BT -right); /* 输出右子树 */ printf(); /* 输出右括号 */ 2遍历模块1) 先序遍历：先访问根节点，然后分别遍历左子树，右子树，遍历左子树

9、和右子树的方法和遍历整个二叉树的方法一样，而访问根节点是一个固定操作，所以可用递归方法实现。遍历的结束条件是二叉树为空。源代码：void Preorder(struct BTreeNode * BT)if(BT!=NULL) printf(%c,BT -data); /* 访问根结点 */Preorder(BT-left); /* 前序遍历左子树 */Preorder(BT-right); /* 前序遍历右子树 */2) 中序遍历：中序遍历的算法思想和先序遍历一样，仅仅是处理结点的次序不 同其思想为，若二叉树为空，则结束遍历操作，否则中序遍历根节点的左子树 访问根节点中序遍历根结点的右子树。源

10、代码：void In order(struct BTreeNode * BT)if(BT!=NULL) Inorder(BT-left); /* 中序遍历左子树 */printf(%c,BT -data); /* 访问根结点 */Inorder(BT -right); /* 中序遍历右子树 */3) 后序遍历：后序遍历的基本思想为，若二叉树为空，则结束遍历操作否则后 序遍历根结点的左子树，后序遍历根节点的右子树，访问根结点。源代码：void Postorder(struct BTreeNode * BT)if(BT!=NULL) Postorder(BT-left); /* 后序遍历左子树 *

11、/Postorder(BT-right); /* 后序遍历右子树 */printf(%c,BT -data); /* 访问根结点 */4) 广度优先遍历：广度优先遍历的思想为，若二叉树为空，则结束遍历操作，否 则按层进行遍历。源代码：void Levelorder(struct BTreeNode * BT)/* 按层遍历由 BT 指针所指向的二叉树 */struct BTreeNode * p;/* 定义队列所使用的数组空间，元素类型为指向结点的指针类型*/struct BTreeNode* qQueueMaxSize; /*定义队首指针和队尾指针，初始均置0 表示空队 */int fron

12、t=0,rear=0;/* 将树根指针进队 */if(BT!=NULL) rear=(rear+1)% QueueMaxSize; qrear=BT;/* 当队列非空时执行循环 */ while(front!=rear) /* 使队首指针指向队首元素 */ front=(front+1)% QueueMaxSize;/* 删除队首元素，输出队首元素所指结点的值 */ p=qfront;printf(%c,p -data);/* 若结点存在左孩子，则左孩子指针结点进队 */if(p -left!=NULL)rear=(rear+1)% QueueMaxSize; qrear=p -left;/*

13、 若结点存在右孩子，则右孩子指针结点进队 */if(p -right!=NULL)rear=(rear+1)% QueueMaxSize; qrear=p -right;3、求二叉树的深度。源程序：int BTreeDepth(struct BTreeNode * BT)/* 求由指针指向的一颗二叉树的深度 */if(BT=NULL)return 0; /* 对于空树，返回 0 并结束递归 */else /*计算左子树的深度*/int dep仁BTreeDepth(BT -left);/*计算右子树的深度*/int dep2=BTreeDepth(BT -right); /*返回树的深度*/i

14、f(dep1dep2)retur n dep1+1;elseretur n dep2+1;五、程序调试与测试:1、建立二叉树I E:学习 Cicu gcstf. ene三異桝广乂表字符串：|a,c2、主菜单界面4、0.*请在下列序号中 选率一个并输*叉 rj-*!1七- 明礙刊段一 一 叉叉叉買历 -i 义历历历先深 重前中后广二退3、前序遍历前序：abdecf4、中序遍历中序：dbeacf5、后序遍历后序=debFca6广度优先遍历旷度优先：abcdef7、树的深度六、结果分析:在调试过程中，碰到诸多问题，比如定义表长过小，处理记录数量错误时 程 序的异常，记录冲突次数等等。处理这些问题异常

15、麻烦，有时连续错误，摸不清 头绪，在不断修改调试之后，终于运行成功，并对所输入的二叉树实现了前序、 中序、后序以及广度优先遍历，同时计算了树的深度。七、课程设计心得体会：二叉树是常用的数据结构。通过实验加深了我对二叉树的遍历的认识， 巩固 了课本中所学的关于树的基本算法。按要求完成了实验内容。通过实验，有如下几点收获和体会：1、通过实验还提高了一点改错能力，对于一些常见问题加深了印象。2、编程需要有耐心，尤其是在调试程序的时候，更是马虎不得，有时候关键就是那么一步，错过了就得从头来过了。编程也需要勇气，要勇于发现自己的 错误，也要勇于推翻自己之前的思路，要坚信“没有最好，只有更好”。编程需要细

16、心，有时一个不注意小错误就能引出大问题。 编程也需要规范，不仅为了他 人能看得懂程序，也为了方便自己以后程序的更改与进一步的完善。3、程序由算法和数据结构组成，一个好的程序不仅算法重要，数据结构的 设计也很重要。4、以前在学C语言时总觉得函数的递归调用是一样很复杂的算法， 经常会理 解不了而导致编程的错误。但在这次实验中，二叉树的先序、中序、后序与广度优先的输出都用了递归算法。而且用起来并不复杂，这使我更进一步学习理解了 函数的递归调用并得到灵活的运用。 经过本次实验基本上解决的一些所遇到的 问题，我对二叉树的结构等有了较为深入的理解。 我会继续我的兴趣编写程序的， 相信在越来越多的尝试之后，

17、自己会不断进步。八、源程序清单：# in clude# include# define QueueMaxSize 20/* 定义队列数组长度 */# define StackMaxSize 10 /* 定义栈数组长度 */typedef char ElemType;struct BTreeNodeElemType data;struct BTreeNode * left;struct BTreeNode * right;BTreeNode;void InitBTree(struct BTreeNode* BT)/* 初始化二叉树，即把树根指针置空 */*BT=NULL;void CreateB

18、Tree(struct BTreeNode * BT,char * a)/* 根据 a 所定义的二叉树广义表字符串建立对应的存储结构 */struct BTreeNode * p;/*定义 s 数组作为存储根结点指针的栈使用*/struct BTreeNode * sStackMaxSize;/*定义top作为s栈的栈顶指针，初值为-1，表示空栈*/int top=-1;/*用 k 作为处理结点的左子树和右子树的标记， k=1 处理左子树， k=2 处理右子树 */ int k;/*用i扫描数组a中存储的二叉树广义表字符串，初值为 0*/int i=0;/*把树根指针置为空，即从空树开始建立二

19、叉树 */*BT=NULL;/*每循环一次处理一个字符，直到扫描到字符串结束0为止 */while (ai)switch(ai)case : /* 对空格不做任何处理 */break;case (:if(top=StackMaxSize -1)printf( 栈空间太小，需增加 StackMaxSize!n);exit(1);top+;stop=p;k=1;break;case ):if(top= -1)printf( 二叉树广义表字符串错 !n);exit(1);top-;break;case ,:k=2;break;default:p=(struct BTreeNode * )malloc

20、(sizeof(struct BTreeNode);p-data=ai;p-left=p -right=NULL; if(*BT=NULL)*BT=p;elseif(k=1)stop -left=p;elsestop -right=p; /*switch end*/* 为扫描下一个字符串修改 i 值*/i+;void PrintBTree(struct BTreeNode * BT)/* 输出二叉数的广义表表示 */* 数为空时自然结束递归，否则执行如下操作*/if(BT=NULL)/* 输出根结点的值 */printf(%c,BT -data);/* 输出左、右子树 */if(BT -lef

21、t!=NULL | BT -right!=NULL)printf();/* 输出左括号 */PrintBTree(BT -left); /* 输出左子树 */if(BT -right!=NULL)PrintBTree(BT -right); /* 输出右子树 */ printf(); /* 输出右括号 */ void Preorder(struct BTreeNode * BT)if(BT!=NULL) printf(%c,BT -data); /* 访问根结点 */ Preorder(BT -left); /* 前序遍历左子树 */ Preorder(BT -right); /* 前序遍历右

22、子树 */ void Inorder(struct BTreeNode * BT)if(BT!=NULL) Inorder(BT -left); /* 中序遍历左子树 */ printf(%c,BT -data); /* 访问根结点 */ Inorder(BT -right); /* 中序遍历右子树 */ void Postorder(struct BTreeNode * BT)if(BT!=NULL) Postorder(BT-left); /* 后序遍历左子树 */Postorder(BT -right); /* 后序遍历右子树 */printf(%c,BT -data); /* 访问根结

23、点 */void Levelorder(struct BTreeNode * BT)/* 按层遍历由 BT 指针所指向的二叉树 */struct BTreeNode * p;/* 定义队列所使用的数组空间，元素类型为指向结点的指针类型*/struct BTreeNode* qQueueMaxSize;/*定义队首指针和队尾指针，初始均置0 表示空队 */int front=0,rear=0;/* 将树根指针进队 */if(BT!=NULL) rear=(rear+1)% QueueMaxSize;qrear=BT;/* 当队列非空时执行循环 */while(front!=rear) /* 使队

24、首指针指向队首元素 */front=(front+1)% QueueMaxSize;/* 删除队首元素，输出队首元素所指结点的值 */p=qfront;printf(%c,p -data);/* 若结点存在左孩子，则左孩子指针结点进队 */if(p -left!=NULL)rear=(rear+1)% QueueMaxSize;qrear=p -left;if(p -right!=NULL)rear=(rear+1)% QueueMaxSize; qrear=p -right;int BTreeDepth(struct BTreeNode * BT)/* 求由指针指向的一颗二叉树的深度*/if

25、(BT=NULL)return 0; /* 对于空树，返回 0 并结束递归 */ else /* 计算左子树的深度 */int dep1=BTreeDepth(BT -left);/* 计算右子树的深度 */int dep2=BTreeDepth(BT -right);/* 返回树的深度 */ if(dep1dep2) return dep1+1;elsereturn dep2+1;void menu()/ 窗体显示菜单printf(n *请在下列序号中选择一个并输入*:n);n);printf(1、重新定义二叉树n);printf(2、前序遍历二叉树n);printf(prin tf(|3、

26、中序遍历二叉树| n);prin tf(|4、后序遍历二叉树| n);printf(|5、广度优先遍历二叉树| n);printf(|6、二叉树深度| n);printf(|0、退出| n);prin tf(ln);printf(n*:n);void Wrong()/ 错误提示 printf(n= 按键错误 !n);getchar();保留错误信息的显示void main()/*定义指向二叉树节点的操作，并用指针作为树根指针*/struct BTreeNode * bt;/*定义一个用于存放二叉树广义表的字符数组*/char b50;/*定义 ElemType 类型的对象 X 和指针对象 px*/ ElemType x,* px;/*初始化二叉树，即置树根bt 为空 */InitBTree(&bt);/*从键盘向字符数组b 输入二叉树广义表标识的字符串 */printf( 输入二叉树广义表字符串 :n);printf( 输入格式为 :a(c(m,d(s,z),e(t(h,k),b(i)n); scanf(%s,b);/*建立以 bt 作为树根指针的二叉树的链接存储结构 */CreateBTree(&bt,b);menu();while(10)/ 界面的显示实现int p;scanf(%d,&p);switch(p)case 0:printf(=