二叉树实验报告

1、二叉树实验报告问题描述（1）问题描述：用先序递归过程建立二叉树 (存储结构：二叉链表)。输入数据按先序遍历所得序列输入，当某结点左子树或右子树为空时，输入*号，如输入abc*d*e*得到的二叉树为：a eb dc 编写递归算法，计算二叉树中叶子结点的数目。按凹入表方式输出该二叉树。（2） 分析：此题要求用二叉链表作为存储结构，首先要定义二叉链表： typedef struct BiTNode char data; struct BiTNode *lchild, *rchild; BiTNode, * BiTree;struct BiTNode *lchild, *rchild中lchild，r

2、child分别表示该结点的左右孩子。输入时，按先序遍历所得序列输入，当某结点左子树或右子树为空时，输入*号。输出以凹入表的形式输出。算法思想（1） 按照要求，这道题采用二叉链表来存储矩阵的有关信息。存储结构定义为：typedef struct BiTNode char data; struct BiTNode *lchild, *rchild; BiTNode, * BiTree;题中共有四个函数，包括主函数main()，创建二叉树函数Status preorder(BiTree &T)，计算叶子结点函数Status calLeaf(BiTree &T)，输出函数Status output(B

3、iTree &T,int)。其中，主函数首先调用preorder()创建二叉树，然后调用函数calLeaf()。最后调用函数output()，输出二叉树。（2） 算法描述： main() BiTree T; int depth = 0; / 打印提示语 /输入先序序列 preorder(T);/调用函数，先序创建二叉树 calLeaf(T);/调用函数calLeaf()计算叶子结点数并打印 output(T,depth);/调用函数凹入输出 system(pause); return 0; /创建 Status preorder(BiTree &T) char ch; scanf(%c,&ch

4、);/读入数据 if(ch = *) T=NULL; /读到*号，表明该结点无孩子 else if ( ! (T=(BiTNode *)malloc(sizeof(BiTNode) )/动态申请 exit(OVERFLOW); T-data=ch;/将数据计入结点的数据域 /递归调用 /CreatBiTree /计算叶子结点数 Status calLeaf(BiTree &T) if(空树,无叶子) return ERROR; else if(只有左孩子或右孩子) return 1; / else 递归调用 Status output(BiTree &T,int depth) int i; i

5、f(当前结点不为空) depth +;/深度加1 /打印元素前空格 /打印数据 if (左孩子) if (! output(T-lchild,depth) return ERROR;/递归 if (右孩子) if (! output(T-rchild,depth) ) return ERROR;/递归 return OK; else return ERROR; 源程序 已提交测试结果（1） 用户使用说明：运行环境：visual C+ 6.0 Dev-c+程序启动：Ctrl+F10操作步骤：按照提示输入输入：abc*d*e* 图 1打印提示语，运行正常。按要求输入先序遍历序列，按该序列得到的二叉

6、树为图1所示二叉树，叶子结点数为3，a在第一层，b，e在第二层，c，d在第三层。运行正常。心得体会（1）Status calLeaf(BiTree &T) if(!T) return ERROR; /空树,无叶子 else if(!(calLeaf(T-lchild) num +; else if(!(calLeaf(T-lchild) num +;/递归调用 return num; 这种算法的思想是递归调用函数，当调用到没有孩子的叶子结点时，num数加1。这样依次计算，最终找到所有的叶子结点。但是，这种算法在调用时，不能统计右子树上的叶子结点，导致出现下面的错误：所以改成了现在的算法：Sta

7、tus calLeaf(BiTree &T) if(!T) return ERROR; /空树,无叶子 else if(!T-lchild & !T-rchild) return 1; /只有左孩子或右孩子 else return (calLeaf(T-lchild) + calLeaf(T-rchild);/递归调用 当T为空时，是空树，叶子结点数为0；当左孩子或右孩子有一个不存在时，叶子结点数为1；当左右孩子都存在时，递归调用，知道找到所有的叶子结点，返回左右子树上叶子结点数之和即为所求。（2） 心得体会：这道题用二叉链表存储二叉树，二叉链表由数据元素，左孩子指针和右孩子指针组成。用二叉链

8、表存储二叉树比较简单，但是不足是不能存储该节点的双亲，这种情况下，用线序序列建立二叉树比较方便。虽然是用二叉链表这种较为简单的方式存储二叉树，但对于初次接触树的概念的我还是一个很好的锻炼机会，增强了对于二叉树孩子与双亲的关系的理解，有助于更好的了解二叉树的结构。输入数据后，循环调用创建函数，依次读入数据并保存。创建二叉树，计算叶子结点数和打印凹入表都要用到递归函数。可以说，对树和操作都主要是对递归函数的调用，复习了对二叉链表的应用。对于递归算法，现在的理解一直比较模糊，通过这道题在一定程度上增加了对递归函数的理解。选做 （1）用先序和中序遍历建立二叉树。用户分别输入一个二叉树的先序遍历序列和中

9、序遍历序列，通过两个遍历序列建立二叉树。 （2）解决方法：二叉树存储方式不变，但在程序中增加两个字符数组pre和in分别用于存放两个遍历序列。用递归的算法解决问题。不难发现，pre中的第一个元素即为根节点对应的元素。而在in数组中，若第i个元素等于pre0，那么从第一个到第i-1个元素即为根节点的左子树。按照这个方法，用递归的算法即可构建一棵完整的二叉树。（3） 算法描述： Status creatTree(BiTree &T,char pre,char in,int p,int q) int i = 0; /i表示根节点在中序中的位置 动态申请 T-data = prep; /根节点 i = q; while(ini != prep) i+; if(构建左子树)