数据结构 二叉树实验报告.docx

一 需求分析：

、

编写一段程序，对二叉树进行复合操作，包括创建一棵二叉树，显示二叉树的树型结构，

对创建的二叉树进行先根、中根、后根三种方式进行遍历，并且打印出叶子结点，并且可以

随时删除我们创建的二叉树，然后用循环语句将上述的操作封装起来，使之能够进行可重复、

然后定义我们需要的指针类型

定 义 一 个 指 向 二 叉 树 结 点 的 指 针 的 指 针 即 ： BinTreeNode ** pbtree, 或 者 是 ：

PBinTreeNode *pbtree;用于存放树的根结点，同时，将我们创建的二叉树的地址传给它即：

首先我们定义一个 DataType 类型的变量 i,用于存放我们输入的字符（即作为缓冲区），

并用 scanf 函数去接收它，由于使用 scanf 函数时，会出现吸收我们输入的回车字符，并将

会车作为接收的字符的情况发生，为了避免这种情况，我们用函数 fflush(stdin)将缓冲区的

打印出里面的信息。

后是根结点的内容。

如果当前的左子树不为空，则遍历左子树，如果右子树不为空的话，则遍历右子树，如

果都不位空的话，分别调用左右子树，如果左右都为空的话，就释放左右结点空间，并将当

前结点置为空。

Please input char to the binatree, @ to exit current node:Please input a char:

这时用户用键盘输入，每输入一个字符回车一次,输入为 a-z 或者是 A-Z 之间的字符，

用‘@’字符作为结束当前结点的标识符

当用户，创建了二叉树之后，出现控制菜单：

Please choose the mode you want to operate with the binatree:

1.display 2.preOrder 3.inOrder 4.postOrder 5.leaves 6.free nodes 0 to exit:

此时用户可以选择操作：1. 自动的打印出树型结构 2.先根遍历 3.中根遍历 4.后根遍历

5. 打印叶子结点 6. 释放所有结点空间 0.退出

五 测试结果：

、

1． 测试完全二叉树的情形：

输入（每输入一个字符回车一次）：A B C @ @ D @ @ E F @ @ G

三种遍历方式和叶子结点，测试如下：

先根：