二叉树的建立和遍历的演示.docx

《二叉树的建立和遍历的演示.docx》由会员分享，可在线阅读，更多相关《二叉树的建立和遍历的演示.docx（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、系主任（或责任老师）签名:2007年7月2日题 目:二叉树的建立和遍历的演示初始条件：理论：学习了数据结构课程，把握了基本的数据结构和常用的算法；实践：计算机技术系试验室供应计算机及软件开发环境。要求完成的主要任务：（包括课程设计工作量及其技术要求，以及说明书撰写等详细要求）1、系统应具备的功能：（1）选择树的存储结构,建立二叉树；（2）用递归算法和非递归算法实现二叉树的遍历（3）二叉树遍历的演示2、数据结构设计；3、主要算法设计；4、编程及上机实现；5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关键字；（3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、 不足之

2、处、设计体会等；（4）结束语；（5）参考文献。时间支配：2007年7月2日一7日（第18周）7月2日 查阅资料7月3日 系统设计，数据结构设计，算法设计7月4日-5日 编程并上机调试7月6日撰写报告7月7日验收程序，提交设计报告书。指导老师签名:2007年7月2日二叉树的建立及遍历的实现旋转:将新加上的虚线改为实线，并将虚线以及有关的实线顺时钟旋转45度。二叉树还原为一般树的步骤是：加线:若某结点是一父结点的左孩子，则将该结点的右孩子以及沿着右链搜寻到的全部 右孩子结点都用线与那个父结点连接起来；抹线:抹去原二叉树中全部结点与其右孩子的连线；旋转:将虚线及有关实线逆时钟旋转约45度，并将几个结

3、点按层次排列。二叉树通常有两类存储结构，挨次存储结构和链式存储结构。6 .设计心得体会通过编写这个比较基础的二叉树的建立和遍历的实现的程序，基本把握了以前学习的 一些C语言的学问。许多学问点都是通过二次看书才理解了，现在可以编写一些简洁的C 语言程序。借这个设计时间又把握了一些C语言编程的用法，对以后编写大一点的程序有 很大的关心。编写的时候虽然刚开头有些困难，但通过看书.询问同学和借由网络，都一点一点的解 决了。虽然编程有点枯燥，但是通过不断努力编写出来后心里还是特别兴奋的。就像学习 英语，一步一步的积累。在以后的学习中，盼望通过不断的编写争取写出一些功能较为浩 大的程序。7 .结束语本文主

4、要内容是二叉树的建立及其遍历的实现，计算结点数等等。是通过c语言编写的程序。参考文献1严蔚敏，吴伟名。数据结构，清华高校出版社2张颖江，胡燕。C语言程序设计，科学出版社3潭浩强。C程序设计，清华高校出版摘要：该程序主要部分有：基于静态二叉链的二叉树的建立及其遍历的实现，包括建立二 叉树，先序.中序.后序遍历二叉树，以及依据遍历数序计算二叉树中的结点数和叶子结点 数等。关键字：二叉树，建立，遍历，先序，中序，后序，结点数0.引言二叉树是一种树型结构，其特点是每个结点至多有两棵子树(有左右之分，次序不能颠倒) 其多应用在查找.排序.存储二叉链等中。对那些都有很大关心，二叉树的建立等只是基础, 是对

5、其的基本理解。1 .需求分析二叉树的建立.遍历和结点数的计算等等。2 .数据结构设计#include#include/*定义树的结点结构*/typedef struct TreeNodechar data;/*树中结点的数据是一个字符*/struct TreeNode *lchild;struct TreeNode *rchild;JTREENODE;int NodeNum = 0;/*统计数的结点数*/int LeafNum = 0;/*统计数的叶子结点数*/char ch = aJb, c,J，dJ e,甲，J g，int inc = 0;3 .算法设计二叉树建立/*建立一颗二叉树*/in

6、t CreateBiTree(TREENODE *T)/*按先序次序输入二叉树中结点的值，以空字符表示空树*/(char i;if(chinc+=, f)*T = NULL;else(printf(n%cnH,chinc-1);if(!(*T = (TREENODE *)malloc(sizeof(TREENODE) return -1;(*T)-data = chinc-1;printf(H%cnH,(*T)-data);CreateBiTree(&(*T)-lchild);CreateBiTree(&(*T)-rchild);)return 1;)3. 2先序遍历/*先序遍历二叉树*/in

7、t PreOderTraverse(TREENODE *T)(if(T)(printf(n%c H,T-data);PreOderTraverse(T-lchild);PreOderTraverse(T-rchild);)return 1;)3. 3中序遍历/*中序遍历二叉树*/int lnOderTraverse(TREENODE *T)(if(T)(lnOderTraverse(T-lchild);printf(n%c H,T-data);lnOderTraverse(T-rchild);)return 1;)3. 4后序遍历/*后序遍历二叉树*/int BackOderTraverse(

8、TREENODE *T)if(T)BackOderTraverse(T-lchild);BackOderTraverse(T-rchild); printf(%c H,T-data);return 1;)3. 5计算结点树/*采用先序遍历来计算树中的结点数*/ void CountNodeNum(TREENODE *T) (if(T)(NodeNum +;CountNodeNum(T-lchild);CountNodeNum(T-rchild);)3. 6计算叶子结点数/*采用先序遍历计算叶子节点数*/void CountLeafNum(TREENODE *T)(if(T)(if(!(T-lc

9、hild)&(!(T-rchild)LeafNum +;CountLeafNum(T-lchild);CountLeafNum(T-rchild);)3. 7界面的设计int main()(TREENODE *T;int i;CreateBiTree(&T);doclrscr();C i 4*o I*”*H)；*H)；puts。*you can choose:puts。* 1: Traverse the Binary tree by pre order *);puts(n* 2: Traverse the Binary tree by mid order*)；puts。* 3: Travers

10、e the Binary tree by back order*);puts。* 4: Count the node num of the Binary tree *)；puts。* 5: Count the leaf node num of the Binary tree*);puts(”*“)puts(nplease input your choice:)； scanf(H%dH,&i);switch(i)(printf(nThe preoder is:nH);PreOderT raverse(T);printf(HnH);break;case 1: printf(HThe midoder

11、 is:nH);InOderTraverse(T);printf(HnH);break;printf(HThe backoder is:nH);BackOderT raverse(T);printf(MnH);break;case 2: CountNodeNum(T);printf(HThe nodenum of the tree is:%dnH,NodeNum);break;case 3: CountLeafNum(T);printf(HThe leafnum of the tree is:%dnn,LeafNum);break;)printf(nplease input any char

12、to go onnn);getch();while(i=1)&(i32cMd.eze-问XXXXJCXXJOOCMMJOOOCXXXXJOOCXXXJOOCMJOOOOCXXXXXXJCMJOOCXMMJOC* you can choose：* 1：Traverse the Binarytree by pre order* 2：Traverse the Binarytree by mid order* 3：Traverse the Binarytree by back order* 4：Count the node nun of the Binarj/ tree*5：Count the lea

13、f nodenum of the Binarytree*XXXXXXXXXXXXXMXXMXXXXXXXMXXXXXXXXXXXXXXXXXXXXXXXXXplease input your choice：1The preoder is：a b c d e f gplease input any char to go on中序遍历:叩 C:TINDOSsyste32cMd.exe- lol x|*you can choose:* 1： Traverse theBinary tree by pre orderM* 2： Trauerse theBinary tree by mid orderM*

14、 3： Trauerse theBinaru tree by back orderM* 4： Count the node nun of the Binary tree* 5： Count the leaf node num of the Binarytree*please input your choice：2The midoder is：c b d a f e gplease input any char to go on后序遍历:计算树的结点数:计算叶子结点数:5.相关原理二叉树的遍历由于二叉树的基本运算在链式存储结构上的实现比较简洁，无需详加争论。下面争论二 叉树的一种较为简单的重要运

15、算遍历及其在二叉链表上的实现。遍历一棵二叉树就是按某种次序系统地“访问”二叉树上的全部结点，使每个结点恰好 被“访问” 一次。所谓“访问” 一个结点，是指对该结点的数据域进行某种处理，处理的 内容依详细问题而定，通常比较简洁。遍历运算的关键在于访问结点的“次序”，这种次 序应保证二叉树上的每个结点均被访问一次且仅一次。由定义可知，一棵二叉树由三部分组成:根、左子树和右子树。因此对二叉树的遍历也可相应地分解成三项“子任务”：访问根根点；遍历左子树（即依次访问左子树上的全部结点）；遍历右子树（即依次访问右子树 上的全部结点）。由于左、右子树都是二叉树（可以是空二叉树），对它们的遍历可以按上述方法连

16、续分 解，直到每棵子树均为空二叉树为止。由此可见，上述三项子任务之间的次序打算了遍历 的次序。若以D、L、R分别表示这三项子任务，则人有六种可能的次序:DLR、LDR、LRD、 DRL、RDL和RLDo通常限定“先左后右”，即子任务在子任务之前完成，这样就只剩 下前三种次序，按这三种次序进行的遍历分别称为先根遍历（或前序遍历）、中根（或中序） 遍历、后根（或后序）遍历。三种遍历方法的定义如下：先根遍历若需遍历的二叉树为空，执行空操作;否则，依次执行下列操作：访问根结点；先根遍历左子树；先根遍历右子树。中根遍历若需遍历的二叉树为空，执行空操作，否则，依次执行下列操作：中根遍历左子树;访问根结点;

17、中根遍右子树。后根遍历若需遍历的二叉树为空，执行空操作，否则，依次执行下列操作：后根遍历左子树。后根遍历右子树。访问根结点。明显，上述三种遍历方法的区分在于执行子任务”访问根结点”的“时机”不同；最 先（最终、在中间）执行此子任务，则为先根（后根、中根）遍历。按某种遍历方法遍历一棵二叉树，将得到该二叉树上全部结点的访问序列。树与二叉树之间的转换一般树转换为二叉树的基本思想是:将树中每个结点用两个链接表示就可以了，一个 指向它最左边的孩子，另一个指向它右边的一个兄弟，从图形上看，详细步骤是：加线:在兄弟结点直接加一虚线；抹线:对每个结点，除了其最左的一个孩子外，抹去该结点原来与其余孩子之间的 边线；