二叉树遍历.doc

实验名称：二叉树的遍历（1） 实验目的：1.了解二叉树的基本概念、存储结构以及遍历方式；2.了解图的基本概念、存储结构以及关键路径的寻找方式；3. 学会使用C+构造一基本的二叉树结构；4. 掌握二叉树的遍历，并使用C+完成其中序遍历，其它遍历方式可类似编写。（二）实验分析： 二叉树是递归定义的，因而在VB中可以依托数组很容易实现二叉树的建立及先序遍历、中序遍历、后序遍历。 首先自然是要建立一个二叉树，通过对数组赋值，建立一个简单的二叉树。然后通过使用do while循环语句、if.then.条件语句、辅助数组等实现先序遍历、中序遍历和后序遍历等操作。在此过程中需对数组进行多次赋值和判断，主要依据的是三种遍历中各结点之间的关系。（3） 实验步骤：1、 打开VB语言编程软件，调试好界面，做好准备工作。2、 编程：Private Sub Form_Load()ShowDim b()Dim v() 存储二叉树个节点数值Dim v1() 存储遍历后二叉树各节点的数值Dim p() As Boolean 存储该节点是否已被读取Dim t% 记录以读取节点个数n = Val(InputBox(请输入数组元素的个数)ReDim v(n)ReDim v1(n)ReDim p(2 * n)Print数组的生成Print 生成数组For i = 1 To nv(i) = InputBox(请给第 & i & 个元素赋值)Print v(i); Spc(3);Next iPrint先序遍历Print 先序遍历i = 1t = 0Do While t = n Then Exit Do 全部读完后结束If 2 * i + 1 = n Then 左右结点均有且未被读取 i = 2 * i 转到左结点ElseIf 2 * i = n Then 只有左结节点而没有右结点读取左结点数值 t = t + 1 ReDim Preserve b(t) b(t) = v(2 * i) Do While i Mod 2 0 判断该节点属性即该结点是他双亲节点的左孩子还是右孩子 i = (i - 1) / 2 是双亲节点的右孩子则回到他的双亲节点 Loop i = i + 1 是双亲结点的左孩子则转到他的兄弟结点Else 该节点为叶子节点 Do While i Mod 2 0 判断该节点属性即该结点是他双亲节点的左孩子还是右孩子 i = (i - 1) / 2 是双亲节点的右孩子则回到他的双亲节点 Loop i = i + 1 是双亲结点的左孩子则转到他的兄弟结点End IfLoop 回到当前节点输出For i = 1 To nPrint b(i); Spc(3);Next iPrint中序遍历Print 中序遍历给 p(i)初始化使各个结点均为被读取（长度为2*n防止下标越界）For i = 1 To 2 * n p(i) = FalseNext ii = 1t = 0Do While t nIf 2 * i + 1 = n And p(2 * i) = False Then 左右结点均有且未被读取 i = 2 * i 转到左结点ElseIf 2 * i = n And p(2 * i) = False Then 只有左结节点而没有右结点且左节点未被读取 读取左结点数值 t = t + 1 ReDim Preserve b(t) b(t) = v(2 * i) p(2 * i) = True 设置该结点已读 读取结点数值 t = t + 1 ReDim Preserve b(t) b(t) = v(i) 设置该结点已读 p(i) = True If i Mod 2 = 0 Then 是双亲结点的左孩子 读取该节点的左孩子节点数值 t = t + 1 ReDim Preserve b(t) b(t) = v(i / 2) p(i / 2) = True i = i + 1 转到右孩子节点 Else 是双亲结点的右孩子 i = (i - 1) / 2 转到该节点的双亲节点 End IfElse 该节点为根节点或孩子节点全部已读取 If p(i) = False Then 判断该节点是否以读取 未读取则读取该节点 t = t + 1 ReDim Preserve b(t) b(t) = v(i) p(i) = True End If If i Mod 2 = 0 Then 该节点是双亲结点的左孩子 读取该节点的左孩子节点 t = t + 1 ReDim Preserve b(t) b(t) = v(i / 2) p(i / 2) = True i = i + 1 转到该节点的兄弟结点即他的双亲节点的右孩子节点 Else 该节点是双亲结点的右孩子 i = (i - 1) / 2 转到该节点的双亲节点 End IfEnd IfLoop输出For i = 1 To nPrint b(i); Spc(3);Next iPrint后续遍历Print 后序遍历给 p(i)初始化使各个结点均为被读取（长度为2*n防止下标越界）For i = 1 To 2 * n p(i) = FalseNext ii = 1t = 0Do While t nIf 2 * i + 1 = n And p(2 * i) = False Then 左右结点均有且未被读取 i = 2 * i 转到左结点ElseIf 2 * i = n And p(2 * i) = False Then 只有左结节点而没有右结点且左节点未被读取 读取左结点数值 t = t + 1 ReDim Preserve b(t) b(t) = v(2 * i) p(2 * i) = True 读取该结点数值 t = t + 1 ReDim Preserve b(t) b(t) = v(i) p(i) = True If i Mod 2 = 0 Then 该节点是双亲结点的左孩子 i = i + 1 转到该节点的兄弟结点即他的双亲节点的右孩子节点 Else 该节点是双亲结点的右孩子 i = (i - 1) / 2 转到该节点的双亲节点 End If Else 该节点为根节点或孩子节点全部已读取读取该节点数值 t = t + 1 ReDim Preserve b(t) b(t) = v(i) p(i) = True If i Mod 2 = 0 Then 该节点是双亲结点的左孩子 i = i + 1 转到该节点的兄弟结点即他的双亲节点的右孩子节点 Else 该节点是双亲结点的右孩子 i = (i - 1) / 2 转到该节点的双亲节点 End IfEnd IfLoop输出For i = 1 To nPrint b(i); Spc(3);Next i i = 2 * i End Sub如取n=10，然后随意输入一组数，运行结果如下：（四）实验小结： 通过上面的