二叉树的建立和遍历实验报告.docx

《二叉树的建立和遍历实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、【二叉树的建立和遍历实验报告】二叉树的遍历实验心得　　[题目]建立二叉树并求指定结点路径、深度、叶子个数和左右子树交换。　　[问题描述]　　要求能够按先序遍历次序输入二叉树中结点的值来构造二叉树T；然后用递归和非递归算法实现二叉树T的中序遍历；接着编写算法实现求二叉树T中指定结点的路径，即从键盘输入二叉树T的任一结点，可以输出从根结点到该结点所经历的结点；最后编写二叉树的三个应用算法。　　[基本要求]　　分别建立二叉树存储结构的输入输出函数、输出中序遍历函数、指定节点路径函数、求深度函数、求叶子个数函数和将二叉树左右子树交换函数　　一

2、、需求与规格说明　　1、定义二叉树的存储结构，每个结点中设置三个域，即值域、左指针域、右指针域。要建立二叉树T的链式存储结构，即建立二叉链表。根据输入二叉树结点的形式不同，建立的方法也不同，本系统采用先序序列递归建立二叉树，建立如下图所示的二叉树。应该在程序运行窗口的主控菜单后，先选择“1”并回车，紧接着在程序运行窗口中提示信息“输入二叉树的先序序列结点值:”之后，采用以下字符序列：abc@@de@g@@f@@@作为建立二叉树T的输入字符序列并回车，窗口出现：二叉树的链式存储结构建立完成!　　图1二叉树的图形结构　　2、二叉树的遍历。

3、本系统采用非递归中序遍历算法进行中序遍历，这意味着遍历右子树时不再需要保存当前层的根指针，可直接修改栈顶记录中的指针即可。需要在程序运行窗口的主控菜单中选择“2”并回车，程序运行窗口会出现以下中序遍历序列：　　该二叉树　　的中序遍历序列是:cbegdfa　　3、求二叉树的指定结点路径。在程序运行窗口的主控菜单中选择“3”并回车，在程序运行窗口中提示信息“输入要求路径的结点值:”输入“g”并回车，会得到结果为：→a→b→d→e→g如果输入“i”并回车，会得到结果为：没有要求的结点！　　4、求二叉树的深度。在程序运行窗口的主控菜单中选择“

4、4”并回车，在会得到结果为：该二叉树的深度为：5　　5、求二叉树的叶子结点个数。在程序运行窗口的主控菜单中选择“5”并回车，在会得到结果为：该二叉树的叶子结点数为：3　　6、将二叉树左右子树交换。在程序运行窗口的主控菜单中选择“6”并回车.得到结果为：该二叉树的左右节点已交换成功，其中序遍历序列是：afdgebc　　7、退出程序。在程序运行窗口的主控菜单中选择“0”并回车。退出程序。　　二、设计　　1、设计思想　　在二叉树上无论采用哪种遍历方法，都能够访问遍树中的所有结点。由于访问结点的顺序不同，前序遍历和中序遍历都很难达到设计的要求

5、；但采用后序遍历二叉树是可行的，因为后序遍历是最后访问根结点，按这个顺序将访问过的结点存储到一个顺序栈中，然后再输出即可。因此，我们可以非递归地后序遍历二叉树T，当后序遍历访问到结点*p时，此时栈中存放的所有结点均为给定结点*p的祖先，而由这些祖先便构成了一条从根结点到结点*p之间的路径。而求二叉树的深度和叶子结点数可以直接判断结点孩子的数目来完成，将二叉树的左右子树交换也可以利用递归的方法，交换左右孩子来实现。　　2、设计表示　　为实现上述的设计思想，首先要定义二叉树的链式存储结构，我们采用二叉链表的方式，相应的类型说明为：　　ty

6、pedefcharDataType;　　typedefstructnode{　　DataTypedata;structnode*lchild,*rchild;　　}BinTNode,*BinTree;　　函数接口说明:　　StatusCreateBiTree//1,按照先序遍历次序递归建立二叉树　　StatusInorder//2,二叉树非递归中序遍历算法*/　　BinTreeNodePath//3,求二叉树根结点到给定结点*p的路径intDepth//4.求二叉树的深度　　intLeaf//5.求二叉树的叶子结点个数　　BinTNo

7、de*huhuan//将p指针指向的二叉树的左右子树进行互换　　函数调用关系如图所示：　　三、实现注释　　二叉树的创建模块:按照先序遍历次序递归建立二叉树,通过读入的字符，分配存储空间生成新结点后再逐个构建根结点、左子树和右子树。　　二叉树中序遍历模块：采用非递归中序遍历算法，先逐步扫描二叉树的左子树，并压入堆栈，如果栈不为空，左子树为空，则弹出栈顶的一个元素并输出。然后再扫描右子树，然后再重复上面的步骤扫描该分支的左子树，直至整棵二叉树都扫描完成。此时输出的序列便是该二叉树的中序遍历序列。语句注释见代码。　　二叉树指定结点路径模块：

8、该模块由NodePath、FindBT、Findx三个函数体构成，main函数通过先调用Findx函数来查找结点，Findx又通过逐步调用FindBT函数遍历查找结点的路径，最后main函数再通过调用NodePath函数