二叉树的生成与遍历

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

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

3、设计：1) Struct BTNode() 使用链式存储结构定义一个结构体数组，保存二叉树的字符信息和定义指向其左孩子和右孩子的指针。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 to

6、p=-1; /*用k作为处理结点的左子树和右子树的标记，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"); e

7、xit(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(sizeof(struct BTreeNode);p->data=ai;p->left=p->right=NULL;if(*BT=NULL)*BT=p;elseif(k=1)stop->left=p;elsestop-&

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

9、左子树*/ if(BT->right!=NULL) PrintBTree(BT->right); /*输出右子树*/ printf(")"); /*输出右括号*/ 2遍历模块1）先序遍历：先访问根节点，然后分别遍历左子树，右子树，遍历左子树和右子树的方法和遍历整个二叉树的方法一样，而访问根节点是一个固定操作，所以可用递归方法实现。遍历的结束条件是二叉树为空。源代码：void Preorder(struct BTreeNode * BT)if(BT!=NULL) printf("%c",BT->data); /*访问根结点*/ Preor

10、der(BT->left); /*前序遍历左子树*/Preorder(BT->right); /*前序遍历右子树*/2）中序遍历：中序遍历的算法思想和先序遍历一样，仅仅是处理结点的次序不同其思想为，若二叉树为空，则结束遍历操作，否则中序遍历根节点的左子树访问根节点中序遍历根结点的右子树。 源代码：void Inorder(struct BTreeNode * BT)if(BT!=NULL) Inorder(BT->left); /*中序遍历左子树*/ printf("%c",BT->data); /*访问根结点*/ Inorder(BT->ri

11、ght); /*中序遍历右子树*/3）后序遍历：后序遍历的基本思想为，若二叉树为空，则结束遍历操作否则后序遍历根结点的左子树，后序遍历根节点的右子树，访问根结点。源代码 ：void Postorder(struct BTreeNode * BT)if(BT!=NULL) Postorder(BT->left); /*后序遍历左子树*/ Postorder(BT->right); /*后序遍历右子树*/ printf("%c",BT->data); /*访问根结点*/4)广度优先遍历：广度优先遍历的思想为，若二叉树为空，则结束遍历操作，否则按层进行遍历。源代

12、码：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) /*使队首指针指向队首

13、元素*/ 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; 3、求二叉树的深度

14、。 源程序：int BTreeDepth(struct BTreeNode * BT) /*求由指针指向的一颗二叉树的深度*/if(BT=NULL)return 0; /*对于空树，返回0并结束递归*/else /*计算左子树的深度*/int dep1=BTreeDepth(BT->left); /*计算右子树的深度*/int dep2=BTreeDepth(BT->right); /*返回树的深度*/if(dep1>dep2)return dep1+1;elsereturn dep2+1;五、程序调试与测试：1、建立二叉树2、主菜单界面3、前序遍历4、中序遍历5、后序遍历6

15、、广度优先遍历7、树的深度六、结果分析：在调试过程中，碰到诸多问题，比如定义表长过小，处理记录数量错误时 程序的异常，记录冲突次数等等。处理这些问题异常麻烦，有时连续错误，摸不清头绪，在不断修改调试之后，终于运行成功，并对所输入的二叉树实现了前序、中序、后序以及广度优先遍历，同时计算了树的深度。七、课程设计心得体会：二叉树是常用的数据结构。通过实验加深了我对二叉树的遍历的认识，巩固了课本中所学的关于树的基本算法。按要求完成了实验内容。通过实验，有如下几点收获和体会：1、通过实验还提高了一点改错能力，对于一些常见问题加深了印象。2、编程需要有耐心，尤其是在调试程序的时候，更是马虎不得，有时候关键

16、就是那么一步，错过了就得从头来过了。编程也需要勇气，要勇于发现自己的错误，也要勇于推翻自己之前的思路，要坚信“没有最好，只有更好”。编程需要细心，有时一个不注意小错误就能引出大问题。编程也需要规范，不仅为了他人能看得懂程序，也为了方便自己以后程序的更改与进一步的完善。3、程序由算法和数据结构组成，一个好的程序不仅算法重要，数据结构的设计也很重要。4.以前在学C语言时总觉得函数的递归调用是一样很复杂的算法，经常会理解不了而导致编程的错误。但在这次实验中，二叉树的先序、中序、后序与广度优先的输出都用了递归算法。而且用起来并不复杂，这使我更进一步学习理解了函数的递归调用并得到灵活的运用。 经过本次实

17、验基本上解决的一些所遇到的问题，我对二叉树的结构等有了较为深入的理解。我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步。八、源程序清单：# include<stdio.h># include<stdlib.h># define QueueMaxSize 20 /*定义队列数组长度*/# define StackMaxSize 10 /*定义栈数组长度*/typedef char ElemType;struct BTreeNodeElemType data; struct BTreeNode * left; struct BTreeNode * rig

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

19、处理左子树，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; brea

20、k;case ')':if(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*/ /*为扫

21、描下一个字符串修改i值*/i+;void PrintBTree(struct BTreeNode * BT) /*输出二叉数的广义表表示*/*数为空时自然结束递归，否则执行如下操作*/if(BT=NULL) /*输出根结点的值*/ printf("%c",BT->data); /*输出左、右子树*/ if(BT->left!=NULL | BT->right!=NULL) printf("("); /*输出左括号*/ PrintBTree(BT->left); /*输出左子树*/ if(BT->right!=NULL) Pr

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

23、 /*中序遍历左子树*/ 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); /*访问根结点*/void Levelorder(struct BTreeNode * BT)

24、/*按层遍历由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) /*使队首指针指向队首元素*/ front=(front+1)% QueueMaxSize; /*删除队

25、首元素，输出队首元素所指结点的值*/ 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) /*求由指针指向的一颗二

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

27、定义二叉树 n");printf(" 2、前序遍历二叉树 n");printf(" 3、中序遍历二叉树 n");printf(" 4、后序遍历二叉树 n");printf(" 5、广度优先遍历二叉树 n");printf(" 6、二叉树深度 n");printf(" 0、退出 n");printf(" n"); printf("n*:n");void Wrong()/错误提示printf("n=>按键错误!n&

28、quot;);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

29、(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("=>谢谢使用!n"); getchar(); break;case 1:printf("请重新输入二叉树广义表字符串:n");printf("输入格式为:a(c(m,d(s,z),e(t(h,k),b(i)n"); scanf("%s",b)