二叉树的建立和遍历的演示_二叉树的遍历演示
二叉树的建立和遍历的演示由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“二叉树的遍历演示”。
武汉理工大学《数据结构》课程设计说明书
题 目: 二叉树的建立和遍历的演示 初始条件：
理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法； 实践：计算机技术系实验室提供计算机及软件开发环境。
要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
1、系统应具备的功能：
（1）选择树的存储结构,建立二叉树;（2）用递归算法和非递归算法实现二叉树的遍历（3）二叉树遍历的演示
2、数据结构设计；
3、主要算法设计；
4、编程及上机实现；
5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关键字；
（3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、不足之处、设计体会等；（4）结束语；（5）参考文献。
时间安排： 2007年7月2日－7日（第18周）
7月2日 查阅资料
7月3日 系统设计，数据结构设计，算法设计 7月4日-5日 编程并上机调试 7月6日 撰写报告
7月7日 验收程序，提交设计报告书。
指导教师签名： 2007年7月2日
系主任（或责任教师）签名： 2007年7月2日
二叉树的建立及遍历的实现
武汉理工大学《数据结构》课程设计说明书
摘要：该程序主要部分有：基于静态二叉链的二叉树的建立及其遍历的实现，包括建立二叉树，先序.中序.后序遍历二叉树，以及根据遍历数序计算二叉树中 的结点数和叶子结点数等。
关键字：二叉树，建立，遍历，先序，中序，后序，结点数
0.引言
二叉树是一种树型结构，其特点是每个结点至多有两棵子树（有左右之分，次序不能颠倒）其多应用在查找.排序.存储二叉链等中。对那些都有很大帮助，二叉树的建立等只是基础，是对其的基本理解。
1.需求分析
二叉树的建立.遍历和结点数的计算等等。
2.数据结构设计
#include #include /*定义树的结点结构*/
typedef struct TreeNode{
char data;/*树中结点的数据是一个字符*/
struct TreeNode *lchild;
struct TreeNode *rchild;}TREENODE;int NodeNum = 0;/*统计数的结点数*/ int LeafNum = 0;/*统计数的叶子结点数*/ char ch[] = {'a', 'b', 'c', ' ', ' ', 'd', ' ', ' ', 'e', 'f', ' ', ' ', 'g', ' ', ' '};int inc = 0;3.算法设计
3.1二叉树建立
/*建立一颗二叉树*/ int CreateBiTree(TREENODE **T)/*按先序次序输入二叉树中结点的值,以空字符表示空树*/ { char i;if(ch[inc++]==' ')
*T = NULL;else
武汉理工大学《数据结构》课程设计说明书
{ printf(“%cn”,ch[inc-1]);if(!(*T =(TREENODE *)malloc(sizeof(TREENODE))))
return-1;
(*T)->data = ch[inc-1];
printf(“%cn”,(*T)->data);
CreateBiTree(&((*T)->lchild));
CreateBiTree(&((*T)->rchild));} return 1;}
3.2先序遍历
/*先序遍历二叉树*/ int PreOderTraverse(TREENODE *T){ if(T){
printf(“%c ”,T->data);
PreOderTraverse(T->lchild);
PreOderTraverse(T->rchild);} return 1;}
3.3中序遍历
/* 中序遍历二叉树*/ int InOderTraverse(TREENODE *T){ if(T){
InOderTraverse(T->lchild);
printf(“%c ”,T->data);
InOderTraverse(T->rchild);} return 1;}
3.4后序遍历
/* 后序遍历二叉树*/ int BackOderTraverse(TREENODE *T)
武汉理工大学《数据结构》课程设计说明书
{ if(T){
BackOderTraverse(T->lchild);
BackOderTraverse(T->rchild);
printf(“%c ”,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->lchild))&&(!(T->rchild)))
LeafNum ++;
CountLeafNum(T->lchild);
CountLeafNum(T->rchild);} }
3.7界面的设计
int main(){ TREENODE *T;int i;CreateBiTree(&T);
武汉理工大学《数据结构》课程设计说明书
do {
clrscr();
puts(“**************************************************”);
puts(“*
you can choose:
*”);
puts(“* 1: Traverse the Binary tree by pre order
*”);
puts(“* 2: Traverse the Binary tree by mid order
*”);
puts(“* 3: Traverse 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(“please input your choice:”);
scanf(“%d”,&i);
switch(i)
{
case 1:
printf(“The preoder is:n”);
PreOderTraverse(T);
printf(“n”);
break;
case 2:
printf(“The midoder is:n”);
InOderTraverse(T);
printf(“n”);
break;
case 3:
printf(“The backoder is:n”);
BackOderTraverse(T);
printf(“n”);
break;
case 4:
CountNodeNum(T);
printf(“The nodenum of the tree is:%dn”,NodeNum);
break;
case 5:
CountLeafNum(T);
printf(“The leafnum of the tree is:%dn”,LeafNum);
break;
}
printf(“please input any char to go onn”);
getch();}while((i>=1)&&(i
getch();
武汉理工大学《数据结构》课程设计说明书
}
return 1;4.程序运行结果
主界面：
先序遍历：
中序遍历：
武汉理工大学《数据结构》课程设计说明书
后序遍历：
计算树的结点数：
武汉理工大学《数据结构》课程设计说明书
计算叶子结点数：
5.相关原理
二叉树的遍历
由于二叉树的基本运算在链式存储结构上的实现比较简单，无需详加讨论。下面研究二叉树的一种较为复杂的重要运算———遍历及其在二叉链表上的实现。
遍历一棵二叉树就是按某种次序系统地“访问”二叉树上的所有结点，使每个结点恰好被“访问”一次。所谓“访问”一个结点，是指对该结点的数据域进行某种处理，处理的内容依具体问题而定，通常比较简单。遍历运算的关键在于访问结点的“次序”，这种次序应保证二叉树上的每个结点均被访问一次且仅一次。
武汉理工大学《数据结构》课程设计说明书
由定义可知，一棵二叉树由三部分组成:根、左子树和右子树。因此对二叉树的遍历也可相应地分解成三项“子任务”:
①访问根根点;
②遍历左子树(即依次访问左子树上的全部结点);③遍历右子树(即依次访问右子树上的全部结点)。
因为左、右子树都是二叉树(可以是空二叉树)，对它们的遍历可以按上述方法继续分解，直到每棵子树均为空二叉树为止。由此可见，上述三项子任务之间的次序决定了遍历的次序。若以D、L、R分别表示这三项子任务，则人有六种可能的次序:DLR、LDR、LRD、DRL、RDL和RLD。通常限定“先左后右”，即子任务②在子任务③之前完成，这样就只剩下前三种次序，按这三种次序进行的遍历分别称为先根遍历(或前序遍历)、中根(或中序)遍历、后根(或后序)遍历。三种遍历方法的定义如下:
先根遍历 若需遍历的二叉树为空，执行空操作;否则，依次执行下列操作:
①访问根结点;
②先根遍历左子树;
③先根遍历右子树。
中根遍历 若需遍历的二叉树为空，执行空操作，否则，依次执行下列操作:
①中根遍历左子树;②访问根结点;③中根遍右子树。
后根遍历 若需遍历的二叉树为空，执行空操作，否则，依次执行下列操作:
①后根遍历左子树。②后根遍历右子树。③访问根结点。
显然，上述三种遍历方法的区别在于执行子任务“访问根结点”的“时机”不同;最先(最后、在中间)执行此子任务，则为先根(后根、中根)遍历。
按某种遍历方法遍历一棵二叉树，将得到该二叉树上所有结点的访问序列。
树与二叉树之间的转换
一般树转换为二叉树的基本思想是:将树中每个结点用两个链接表示就可以了，一个指向它最左边的孩子，另一个指向它右边的一个兄弟，从图形上看，具体步骤是:
①加线:在兄弟结点直接加一虚线;
武汉理工大学《数据结构》课程设计说明书
②抹线:对每个结点，除了其最左的一个孩子外，抹去该结点原来与其余孩子之间的边线;
③旋转:将新加上的虚线改为实线，并将虚线以及有关的实线顺时钟旋转45度。
二叉树还原为一般树的步骤是: ①加线:若某结点是一父结点的左孩子，则将该结点的右孩子以及沿着右链搜索到的所有右孩子结点都用线与那个父结点连接起来;②抹线:抹去原二叉树中所有结点与其右孩子的连线;③旋转:将虚线及有关实线逆时钟旋转约45度，并将几个结点按层次排列。二叉树通常有两类存储结构，顺序存储结构和链式存储结构。
6.设计心得体会
通过编写这个比较基础的二叉树的建立和遍历的实现的程序，基本掌握了以前学习的一些C语言的知识。很多知识点都是通过二次看书才理解了，现在可以编写一些简单的C语言程序。借这个设计时间又掌握了一些C语言编程的用法，对以后编写大一点的程序有很大的帮助。
编写的时候虽然刚开始有些困难，但通过看书.询问同学和借由网络，都一点一点的解决了。虽然编程有点枯燥，但是通过不断努力编写出来后心里还是非常兴奋的。就像学习英语，一步一步的积累。在以后的学习中，希望通过不断的编写争取写出一些功能较为庞大的程序。
7.结束语
本文主要内容是二叉树的建立及其遍历的实现，计算结点数等等。是通过C语言编写的程序。
参考文献
[1] 严蔚敏，吴伟名。《数据结构》，清华大学出版社 [2] 张颖江，胡燕。《C语言程序设计》，科学出版社 [3] 潭浩强。《C程序设计》，清华大学出版
