二叉树遍历.docx
- 文档编号:18181481
- 上传时间:2023-08-13
- 格式:DOCX
- 页数:9
- 大小:40.23KB
二叉树遍历.docx
《二叉树遍历.docx》由会员分享,可在线阅读,更多相关《二叉树遍历.docx(9页珍藏版)》请在冰点文库上搜索。
二叉树遍历
二叉树遍历
———————————————————————————————— 作者:
————————————————————————————————日期:
实验名称:
二叉树的遍历
(1)实验目的:
1.了解二叉树的基本概念、存储结构以及遍历方式;
2.了解图的基本概念、存储结构以及关键路径的寻找方式;
3. 学会使用C++构造一基本的二叉树结构;
4.掌握二叉树的遍历,并使用C++完成其中序遍历,其它遍历方式可类似编写。
(二)实验分析:
二叉树是递归定义的,因而在VB中可以依托数组很容易实现二叉树的建立及先序遍历、中序遍历、后序遍历。
首先自然是要建立一个二叉树,通过对数组赋值,建立一个简单的二叉树。
然后通过使用do while循环语句、if....then..条件语句、辅助数组等实现先序遍历、中序遍历和后序遍历等操作。
在此过程中需对数组进行多次赋值和判断,主要依据的是三种遍历中各结点之间的关系。
(3)实验步骤:
1、打开VB语言编程软件,调试好界面,做好准备工作。
2、编程:
PrivateSubForm_Load()
Show
Dimb()
Dim v()'存储二叉树个节点数值
Dimv1() '存储遍历后二叉树各节点的数值
Dimp()AsBoolean'存储该节点是否已被读取
Dimt% '记录以读取节点个数
n=Val(InputBox("请输入数组元素的个数"))
ReDimv(n)
ReDim v1(n)
ReDim p(2 *n)
'数组的生成
Print"生成数组"
Fori =1Ton
v(i) =InputBox("请给第"& i&"个元素赋值")
Printv(i); Spc(3);
Nexti
Print
'先序遍历
Print"先序遍历"
i=1
t =0
DoWhile t< UBound(v)
'读取第i个节点的数值
t= t+1
ReDimPreserveb(t)
b(t)=v(i)
Ift>=nThenExitDo'全部读完后结束
If2*i +1<= n Then '左右结点均有且未被读取
i=2*i'转到左结点
ElseIf2*i<=nThen'只有左结节点而没有右结点
'读取左结点数值
t=t+ 1
ReDim Preserveb(t)
b(t)=v(2 * i)
DoWhilei Mod2 <> 0'判断该节点属性即该结点是他双亲节点的左孩子还是右孩子
i =(i-1)/2'是双亲节点的右孩子则回到他的双亲节点
Loop
i= i+1'是双亲结点的左孩子则转到他的兄弟结点
Else'该节点为叶子节点
DoWhileiMod2<>0 '判断该节点属性即该结点是他双亲节点的左孩子还是右孩子
i=(i-1) /2'是双亲节点的右孩子则回到他的双亲节点
Loop
i=i+1'是双亲结点的左孩子则转到他的兄弟结点
End If
Loop'回到当前节点
'输出
Fori=1 Ton
Printb(i);Spc(3);
Next i
Print
'中序遍历
Print"中序遍历"
'给p(i)初始化使各个结点均为被读取(长度为2*n防止下标越界)
Fori=1To2 *n
p(i)=False
Nexti
i=1
t=0
DoWhilet If2* i +1 <=nAndp(2*i)=FalseThen'左右结点均有且未被读取 i=2 * i'转到左结点 ElseIf2*i<=nAndp(2*i) =False Then '只有左结节点而没有右结点且左节点未被读取 '读取左结点数值 t=t+ 1 ReDimPreserveb(t) b(t) =v(2* i) p(2*i)= True '设置该结点已读 '读取结点数值 t =t+ 1 ReDimPreserveb(t) b(t)=v(i)'设置该结点已读 p(i)=True Ifi Mod2 =0Then'是双亲结点的左孩子 '读取该节点的左孩子节点数值 t= t+1 ReDimPreserveb(t) b(t) =v(i/2) p(i/2)= True i =i+1'转到右孩子节点 Else'是双亲结点的右孩子 i =(i- 1)/2'转到该节点的双亲节点 EndIf Else'该节点为根节点或孩子节点全部已读取 Ifp(i)=FalseThen'判断该节点是否以读取 '未读取则读取该节点 t=t + 1 ReDimPreserveb(t) b(t)=v(i) p(i)=True EndIf IfiMod2= 0Then'该节点是双亲结点的左孩子 '读取该节点的左孩子节点 t=t +1 ReDimPreserveb(t) b(t)=v(i/2) p(i/2)=True i =i+1'转到该节点的兄弟结点即他的双亲节点的右孩子节点 Else '该节点是双亲结点的右孩子 i= (i-1) / 2'转到该节点的双亲节点 EndIf EndIf Loop '输出 Fori =1To n Printb(i);Spc(3); Nexti Print '后续遍历 Print "后序遍历" '给p(i)初始化使各个结点均为被读取(长度为2*n防止下标越界) For i=1To2*n p(i)=False Nexti i=1 t =0 DoWhilet If2*i+1<= nAndp(2* i) =False Then'左右结点均有且未被读取 i=2*i'转到左结点 ElseIf 2*i<=nAndp(2*i) =FalseThen '只有左结节点而没有右结点且左节点未被读取 '读取左结点数值 t=t+1 ReDimPreserve b(t) b(t)=v(2*i) p(2*i)=True '读取该结点数值 t=t+1 ReDim Preserveb(t) b(t)=v(i) p(i)=True IfiMod2=0Then '该节点是双亲结点的左孩子 i=i +1 '转到该节点的兄弟结点即他的双亲节点的右孩子节点 Else'该节点是双亲结点的右孩子 i =(i- 1)/2'转到该节点的双亲节点 EndIf Else'该节点为根节点或孩子节点全部已读取 '读取该节点数值 t=t+ 1 ReDim Preserve b(t) b(t)=v(i) p(i)=True If iMod2= 0Then '该节点是双亲结点的左孩子 i=i+1'转到该节点的兄弟结点即他的双亲节点的右孩子节点 Else'该节点是双亲结点的右孩子 i=(i-1)/ 2'转到该节点的双亲节点 EndIf End If Loop '输出 Fori=1Ton Print b(i);Spc(3); Nexti i=2*i EndSub 如取n=10,然后随意输入一组数,运行结果如下: (四)实验小结: 通过上面的实验结果可知,在VB语言编程软件中可以简单的实现二叉树的建立及先序遍历、中序遍历、后序遍历,但同时我们也因该注意到其在实现过程中的复杂程度,要编写的代码很多,时间上消耗很大。 而且相对于C语言编程软件来说,程序运行时的时间复杂度也很大,这是一大缺点。 但总体上来说,运用VB编程其可读性较强,后续工作简单。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 遍历
![提示](https://static.bingdoc.com/images/bang_tan.gif)