二叉树的建立和遍历实验报告【DOC精选】.docVIP

[题目] 建立二叉树并求指定结点路径、深度、叶子个数和左右子树交换。 [问题描述] 要求能够按先序遍历次序输入二叉树 中结点的值来构造二叉树T；然后用递归和非递归算法实现二叉树T 的中序遍历；接着编写算法实现求二叉树T中指定结点的路径，即从键盘输入二叉树T 的任一结点，可以输出从根结点到该 结点所经历的结点；最后编写二叉树的三个应用算法（求二叉树的深度、求二叉树的叶子结点个数、将二叉树左右子树交换）。 [基本要求] 分别建立二叉树存储结构的输入输出函数、输出中序遍历函数、指定节点路径函数、求深度函数、求叶子个数函数和将二叉树左右子树交换函数 一、需求与规格说明 1、定义二叉树的存储结构，每个结点中设置三个域，即值域、左指针域、右指针域。要建立二叉树T的链式存储结构，即建立二叉链表。根据输入二叉树结点的形式不同，建立的方法也不同，本系统采用先序序列递归建立二叉树，建立如下图所示的二叉树。应该在程序运行窗口的主控菜单后，先选择“1”并回车，紧接着在程序运行窗口中提示信息“输入二叉树的先序序列结点值:”之后，采用以下字符序列：abc@@de@g@@f@@@ （以@替代空格，但是程序中直接输入空格就是，详细见代码注释）作为建立二叉树T的输入字符序列并回车，窗口出现：二叉树的链式存储结构建立完成! 图1 二叉树的图形结构 2、二叉树的遍历。本系统采用非递归中序遍历算法进行中序遍历，这意味着遍历右子树时不再需要保存当前层的根指针，可直接修改栈顶记录中的指针即可。需要在程序运行窗口的主控菜单中选择“2” 并回车，程序运行窗口会出现以下中序遍历序列：该二叉树的中序遍历序列是: cbegdfa 3、求二叉树的指定结点路径。在程序运行窗口的主控菜单中选择“3” 并回车，在程序运行窗口中提示信息“输入要求路径的结点值:”输入“g” 并回车，会得到结果为： →a→b→d→e→g如果输入“i” 并回车，会得到结果为：没有要求的结点！ 4、求二叉树的深度。在程序运行窗口的主控菜单中选择“4” 并回车，在会得到结果为： 该二叉树的深度为：5 5、求二叉树的叶子结点个数。在程序运行窗口的主控菜单中选择“5” 并回车，在会得到结果为：该二叉树的叶子结点数为：3 6、将二叉树左右子树交换（此处我用交换后的中序遍历来检验是否成功）。在程序运行窗口的主控菜单中选择“6” 并回车.得到结果为：该二叉树的左右节点已交换成功，其中序遍历序列是：afdgebc 7、退出程序。在程序运行窗口的主控菜单中选择“0” 并回车。退出程序。 二、设计 1、设计思想 在二叉树上无论采用哪种遍历方法，都能够访问遍树中的所有结点。由于访问结点的顺序不同，前序遍历和中序遍历都很难达到设计的要求（求路径）；但采用后序遍历二叉树是可行的，因为后序遍历是最后访问根结点，按这个顺序将访问过的结点存储到一个顺序栈中，然后再输出即可。因此，我们可以非递归地后序遍历二叉树T，当后序遍历访问到结点*p时，此时栈中存放的所有结点均为给定结点*p的祖先，而由这些祖先便构成了一条从根结点到结点*p之间的路径。而求二叉树的深度和叶子结点数可以直接判断结点孩子的数目来完成，将二叉树的左右子树交换也可以利用递归的方法，交换左右孩子来实现。 2、设计表示 为实现上述的设计思想，首先要定义二叉树的链式存储结构，我们采用二叉链表的方式，相应的类型说明为： typedef char DataType; typedef struct node{ DataType data; struct node *lchild,*rchild; }BinTNode,*BinTree; 函数接口说明: Status CreateBiTree(BinTree bt) //1,按照先序遍历次序递归建立二叉树Status Inorder(BinTree bt) //2,二叉树非递归中序遍历算法BinTree NodePath(BinTree bt, BinTNode *ch) //3,求二叉树根结点到给定结点*p的路径int Depth(BinTree bt) //4.求二叉树的深度 int Leaf(BinTree bt)// 5.求二叉树的叶子结点个数 BinTNode *huhuan(BinTNode *p)// 将p指针指向的二叉树的左右子树进行互换 函数调用关系如图所示： 三、实现注释 二叉树的创建模块: 按照先序遍历次序递归建立二叉树非递归中序遍历算法NodePath、FindBT、Findx三个函数体构成，main函数通过先调用Findx 函数来查找结点，Findx又通过逐步调用