数据结构二叉树应用原理

《数据结构二叉树应用原理》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、二叉树一、程序设计题目：(1)建立一个字符二叉树实例，并横向打印该二叉树；(2)计算并输出二叉树的深度和叶子节点数；(3)分别按中序和后序遍历二叉树输出节点数据。二、需求分析：(1)建立一个记录字符数据的二叉树T。二叉树的数据由用户以键盘形式直接输入；(2)本程序输出用户所建立的二叉树T的深度和叶子结点数；(3)本程序还将按中序遍历和后序遍历输出结点数据。（本人认为该步骤即为横向打印二叉树，因此不再做横向打印的要求）。三、概要设计：1.抽象数据类型二叉树的定义如下：ADTBinaryTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：

2、若D=Φ，则B=Φ，称BinaryTree为空二叉树；若D≠Φ，则B={H}，H是如下二元关系：(1)在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；(2)若D-{root}≠Φ，则存在D-{root}={D1，Dr}，且D1∩Dr=Φ；(3)若D1≠Φ，则D1中存在惟一的的元素xr，∈H，且存在D1上的关系H1H；若Dr中存在惟一的元素xr，∈H，且存在Dr上的关系HrH；H={，，H1，Hr}；(4)(D1，{H1})是一棵符合本定义的二叉树，称为根的左子树，(

3、Dr，{Hr})是一棵符合本定义的二叉树，称为根的右子树。基本操作P：CreateBiTree(&T)；操作结果：构造二叉树T。DestroyBiTree(&T)；4初始条件：二叉树T存在。操作结果：销毁二叉树T。BiTreeDepth(&T)；初始条件：二叉树T存在。操作结果：返回T的深度。CountLeaf(&T)；初始条件：二叉树T存在。操作结果：求T的叶子结点数。}ADTBinaryTree2.主程序Voidmian(){初始化；构造二叉树；处理命令；}3.本程序只有两个模块，调用关系为主程序模块调用二叉树模块。四、详细设计：1.二叉树类型T

4、ypedefstructBiNode{chardata;structBiNode*lchild,*rchild;//左右孩子指针}BiNode,*BiTree;二叉树的基本操作：MidVisitBiTree(BiTree&T)//中序遍历访问二叉树TBehindVisitBiTree(BiTree&T)//后序遍历访问二叉树T其操作的伪码算法如下：voidMidVisitBiTree(BiTree&T){//按中序遍历访问二叉树T，并输出结点数据if(T){MidVisitBiTree(T->lchild);printf(“%c”,T->data);

5、MidVisitBiTree(T->rchild);4}elsereturn;return;}voidBehindVisitBiTree(BiTree&T){//按后序遍历访问二叉树T，并输出结点数据if(T){BehindVisitBiTree(T->lchild);BehindVisitBiTree(T->rchild);printf(“%c”,T->data);}elsereturn;return;}2.主程序伪码算法voidmain(){BiTreet;inthigh;printf("请按先序遍历输入一组字符数据。(每输入一个字符按回车确定,

6、结束输入仍按回车结束)");CreateBiTree(t);//构造二叉树high=BiTreeDepth(t);//求二叉树深度printf("二叉树的深度是%d",high);CountLeaf(t);//求二叉树叶子数printf("二叉树的叶子数是%d",leaf);printf("中序遍历:");MidVisitBiTree(t);printf("后序遍历:");BehindVisitBiTree(t);printf("");}3.其它伪码算法intBiTreeDepth(BiTree&T)//计算二叉树T的深度{int

7、lh,rh,h;if(T==NULL)h=0;else{//递归访问左右孩子,并计算其支路深度lh=BiTreeDepth(T->lchild);rh=BiTreeDepth(T->rchild);h=(lh>rh?lh:rh)+1;//条件运算符判断二叉树的深度}4returnh;}voidCountLeaf(BiTree&T)//计算二叉树T的叶子结点数{if(T){if(!(T->lchild&&T->rchild))leaf++;//判断当前结点是否为叶子结点CountLeaf(T->lchild);//若当前结点不是叶子,递归访问其左右孩子

8、CountLeaf(T->rchild);}return;}五、调试分析：该程序的核心算法是构造二叉树T，在