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

发布时间：2024-11-25 来源：未知

小中大

字号：

遍历二叉树与线索二叉树

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

遍历二叉树与线索二叉树

6.3.1

遍历二叉树

遍历定义：遍历定义：指按某条搜索路线遍访每个结点且

不重复（又称周游）。不重复（又称周游）。

遍历用途：它是树结构插入、删除、修改、遍历用途：它是树结构插入、删除、修改、查找

和排序运算的前提，和排序运算的前提，是二叉树一切运算的基础和核心。算的基础和核心。

遍历方法：对每个结点的查看通常都是“ 遍历方法：对每个结点的查看通常都是“先左后

右”。（无论是先序、中序还是后序）。（无论是先序、中序还是后序）无论是先序

遍历二叉树与线索二叉树

例1： A B D E 口诀：口诀： C

先序遍历的结果是：先序遍历的结果是：A B D E C 遍历的结果是中序遍历的结果是：中序遍历的结果是：D B E A C 遍历的结果是后序遍历的结果是：后序遍历的结果是：D E B C A 遍历的结果是

DLR—先序遍历，即先根再左、右先序遍历，即先根再左、先序遍历 LDR—中序遍历，即先左再根后右中序遍历，中序遍历 LRD—后序遍历，即先左、右再根后序遍历，后序遍历即先左、层次遍历：层次遍历： ABCDE

遍历二叉树与线索二叉树

练习

1、任何一棵二叉树的叶子结点在先序、中序、后序遍历任何一棵二叉树的叶子结点在先序、中序、序列中的相对次序不发生改变。（序列中的相对次序不发生改变。（）。 2、已知某二叉树的先序序列为ABDCE，它可能的中序序已知某二叉树的先序序列为ABDCE，列为（列为（） A. BDAEC B. BCADE C. CBADE D. BEACD 3、已知某二叉树的后序遍历序列是dabec，中序遍历序列已知某二叉树的后序遍历序列是dabec， debac,它的前序遍历序列是它的前序遍历序列是（是debac,它的前序遍历序列是（） A. acbed B. decab C. deabc D. cedba

遍历二叉树与线索二叉树

练习

4、一棵二叉树结点的（）可唯一确定一棵二叉树。一棵二叉树结点的（可唯一确定一棵二叉树。 A.先序序列和中序序列 A.先序序列和中序序列 C.后序序列 C.后序序列 C.先序序列和后序序列 C.先序序列和后序序列 D.中序序列 D.中序序列 5、图示在黑板上。写出其先序序列、中序序列和后序图示在黑板上。写出其先序序列、序列。序列。 6、某n>0个结点的二叉树的先序序列和后序序列正好相 n>0个结点的二叉树的先序序列和后序序列正好相则该二叉树一定不是（的二叉树。反，则该二叉树一定不是（）的二叉树。 A.任一结点无左孩子 A.任一结点无左孩子 B.任一结点无又孩子 B.任一结点无又孩子 C.深度为n C.深度为深度为n D.存在度为 D.存在度为2的结点存在度为2

遍历二叉树与线索二叉树

例2：画出所有中序遍历序列和后序遍历序列一致的画出所有中序遍历序列和后序遍历序

遍历二叉树与线索二叉树