数据结构实习报告---二叉树.doc

二叉树 一、需求分析 1、设计任务 建立一棵二叉树，数据以字符串形式从键盘输入。在此二叉树上完成： （1）前序、中序、后序遍历 （2）求出叶子数 （3）求树高 （4）左右子树交换，输出交换后的前序、中序遍历序列 选做： （1）给出非递归的后序遍历 （2）扩充为中序线索树，写出非递归的中序遍历 （3）在两个数组中分别有前序和中序遍历序列，试建立该二叉树 2、输入的形式和输出值的范围 二叉树的建立：本程序的二叉树的建立函数时根据二叉树的前序排列生成的，但是其中子树为空地方用特殊符号“＊”代替。 二叉树的输出值的范围：二叉树的输出是把二叉树各节点的值按遍历顺序输出的，本程序各节点的数据类型为字符型(可以在编译预处理修改)。 3、输出的形式 二叉树的输出是根据二叉树的遍历顺序输出的（包括前序、中序和后序三种）把各节点地值输出。 4、程序所能达到的功能 本程序能够实现对二叉树的一些简单操作，例如二叉树的各种遍历(包括二叉树的前序、中序和后序的递归遍历以及非递归遍历)、求二叉树的叶子数和高以及二叉树的左右子树交换。 5、测试数据 (1)当为二叉树一时： (2)当为二叉树二时： 二、概要设计 1、树结点结构体 typedef char DataType; struct TreeNode { DataType data; TreeNode *lchild,*rchild;}; 2、棧结点结构体 struct StackNode { TreeNode* T_N; int Flag; }; 3、主程序流程 主程序开始； 调用CreateBiTree(TreeNode *Tree)函数建立二叉树； 依次调用前序、中序和后序递归及非递归遍历二叉树； 计算二叉树的树叶和树高； 交换二叉树的左右子树； 依次用前序、中序和后序的递归和非递归方法遍历二叉树； 主程序结束； 三、详细设计 (1)递归遍历的实现(以前序为例)； 算法为：先访问根结点，然后递归的访问左子树和右子树。 具体实现： void Preorder(TreeNode *p)//前序递归遍历二叉树 { if(p!=NULL) { coutp-data ; Preorder(p-lchild); Preorder(p-rchild); } } (2)非递归遍历的实现(以后序为例)； 算法为：从根结点出发，让左孩子依次进棧，并不做标记（即下次退棧时不访问该结点；然后退棧，如果该结点能被访问（即已做标记），则访问该结点，继续退棧；否则，把该结点做上标记（即下次退棧时隔一 被访问），并且把该结点的右孩子进棧。 具体实现： void _Postorder(TreeNode *t)//非递归后序遍历 { SqStack *sq; InitStack(sq); TreeNode *p; p=t; ElemType *temp; int flag; while(p!=NULL||StackEmpty(sq)==0) { while(p) { temp=new ElemType; temp-T_N=p; temp-Flag=0; Push(sq,temp); p=p-lchild; } temp=Pop(sq,flag); p=temp-T_N; flag=temp-Flag; if(flag==0) { temp-Flag=1; Push(sq,temp); p=p-rchild; } else{ coutp-data ; delete temp; p=NULL; } } } (3)求树叶树和树高的实现； 求树叶数：递归的计算左右子树叶子的数目，然后相加。 具体实现： int Count_Leaves(TreeNode *p)//叶子计数 { int m,n;//m、n分别记录点p的左右子树叶子的个数 if(p){ m=Count_Leaves(p-lchild);