数据结构二叉树应用原理.doc
4页
1二叉树一、程序设计题目：(1)建立一个字符二叉树实例，并横向打印该二叉树；(2)计算并输出二叉树的深度和叶子节点数；(3) 分别按中序和后序遍历二叉树输出节点数据二、需求分析：(1)建立一个记录字符数据的二叉树 T二叉树的数据由用户以键盘形式直接输入；(2)本程序输出用户所建立的二叉树 T 的深度和叶子结点数；(3)本程序还将按中序遍历和后序遍历输出结点数据 （本人认为该步骤即为横向打印二叉树，因此不再做横向打印的要求） 三、概要设计：1.抽象数据类型二叉树的定义如下：ADT BinaryTree{数据对象 D：D 是具有相同特性的数据元素的集合数据关系 R：若 D=Φ，则 B=Φ，称 BinaryTree 为空二叉树；若 D≠Φ，则 B={H}，H 是如下二元关系：(1)在 D 中存在惟一的称为根的数据元素 root，它在关系 H 下无前驱；(2)若 D-{root}≠Φ，则存在 D-{root}={D1 ，D r }，且 D1 ∩D r =Φ；(3)若 D1 ≠Φ，则 D1中存在惟一的的元素 xr ，∈H，且存在 D1 上的关系 H1 H；若 Dr 中存在惟一的元素 xr ，∈H，且存在 Dr 上的关系 Hr H；H={，，H 1 ，H r }；(4)(D1 ，{ H1 })是一棵符合本定义的二叉树，称为根的左子树，(Dr ，{H r })是一棵符合本定义的二叉树，称为根的右子树。
基本操作 P：CreateBiTree(&T)；操作结果：构造二叉树 T2DestroyBiTree(&T)；初始条件：二叉树 T 存在操作结果：销毁二叉树 TBiTreeDepth(&T)；初始条件：二叉树 T 存在操作结果：返回 T 的深度CountLeaf(&T)；初始条件：二叉树 T 存在操作结果：求 T 的叶子结点数}ADT BinaryTree2.主程序Void mian(){初始化；构造二叉树；处理命令；}3.本程序只有两个模块，调用关系为主程序模块调用二叉树模块四、详细设计：1.二叉树类型Typedef struct BiNode{char data;struct BiNode *lchild,*rchild; //左右孩子指针}BiNode,*BiTree;二叉树的基本操作：MidVisitBiTree(BiTree &T)//中序遍历访问二叉树 TBehindVisitBiTree(BiTree &T)//后序遍历访问二叉树 T其操作的伪码算法如下：void MidVisitBiTree(BiTree &T) {//按中序遍历访问二叉树 T，并输出结点数据if(T){MidVisitBiTree(T->lchild);printf(“%c”,T->data);3MidVisitBiTree(T->rchild);}else return;return;}void BehindVisitBiTree(BiTree &T){//按后序遍历访问二叉树 T，并输出结点数据if(T){BehindVisitBiTree(T->lchild);BehindVisitBiTree(T->rchild);printf(“%c”,T->data);}else return;return;}2.主程序伪码算法void main(){BiTree t;int high;printf("请按先序遍历输入一组字符数据。
每输入一个字符按回车确定,结束输入仍按回车结束)\n");CreateBiTree(t); //构造二叉树high=BiTreeDepth(t); //求二叉树深度printf("二叉树的深度是%d\n",high);CountLeaf(t); //求二叉树叶子数printf("二叉树的叶子数是%d\n",leaf);printf("中序遍历:");MidVisitBiTree(t);printf("\n 后序遍历:");BehindVisitBiTree(t);printf("\n");}3.其它伪码算法int BiTreeDepth(BiTree &T) //计算二叉树 T 的深度{int lh,rh,h;if(T==NULL) h=0;else{ //递归访问左右孩子,并计算其支路深度lh=BiTreeDepth(T->lchild);rh=BiTreeDepth(T->rchild);h=(lh>rh ? lh:rh)+1; //条件运算符判断二叉树的深度4}return h;}void CountLeaf(BiTree &T) //计算二叉树 T 的叶子结点数{if(T){if(!(T->lchild&&T->rchild)) leaf++;//判断当前结点是否为叶子结点CountLeaf(T->lchild);//若当前结点不是叶子,递归访问其左右孩子CountLeaf(T->rchild);}return;}五、调试分析：该程序的核心算法是构造二叉树 T，在进行调试时，遇到的主要问题是，该程序是按先序次序输入字符，用户要事先确定二叉树，不能输入一连串的字符由程序自动分配。
如要强制输入的话，程序只能对其构造单支树的二叉链表为此该程序特别打出要输入左右孩子的提示其次，对二叉树的中序和后序遍历，按照课本上的算法需多出 Visit()函数，本人认为既然要让用户知道对二叉树已经遍历过了，就得将其打印出来，因此省去了 Visit()函数直接 printf输出，也合并了横向打印二叉树这一步骤该程序的主要算法 CreateBiTree 以及中序遍历 MidVisitBiTree 和后序遍历 BehinVisitBiTree 的时间复杂度均为 O(n)六、总结：对于本次编程一开始的时候还很顺利，直到调试时才注意到输入字符的复杂程度，可以说，对于不了解二叉树的用户来说是无法理解该程序的对于每次输入的字符，都应事先勾画出心中的二叉树计算二叉树深度的算法看似简单其实不然，其先用遍历二叉树算法得出每条支路的深度，然后用条件运算符比较得出二叉树的深度05 本 (3)班梁中君2005107408。
