6.3 遍历二叉树和线索二叉树

01遍历二叉树


1、在二叉树的一些应用中,常常要求在树中查找具有某种特征的结点,或者对树中全部结点逐一进行某种处理。

2、遍历二叉树:即如何按某条搜索路径巡防树中每个结点,使得每个结点均被访问一次,而且仅被访问一次。

3、先序遍历二叉树的操作定义为:若二叉树为空,则空操作,否则

(1)访问根结点。

(2)先序遍历左子树。

(3)先序遍历右子树。

4、中序遍历二叉树的操作定义为:若二叉树为空,则空操作,否则

(1)中序遍历左子树。

(2)访问根结点。

(3)中序遍历右子树。

5、后序遍历二叉树的操作定义为:若二叉树为空,则空操作,否则

(1)后序遍历左子树。

(2)后序遍历右子树。

(3)访问根结点。


02线索二叉树


1、遍历二叉树的是以一定规则将二叉树中结点排列成一个线性序列,得到二叉树中结点的先序序列或中序序列或后序序列。

2、线索链表:指向结点前驱和后继的指针,叫做线索,加上线索的二叉树称之为线索二叉树。

3、对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。

C语言 | 求平均分及第n个人成绩 mp.weixin.qq.com图标

文章来源: zhuanlan.zhihu.com,作者:小林C语言,版权归原作者所有,如需转载,请联系作者。

原文链接:zhuanlan.zhihu.com/p/337457151

(完)