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