遍历二叉树与线索二叉树

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：画出所有中序遍历序列和后序遍历序列一致的 画出所有中序遍历序列和后序遍历序

遍历二叉树与线索二叉树

遍历二叉树与线索二叉树

遍历二叉树与线索二叉树

遍历二叉树与线索二叉树

遍历二叉树与线索二叉树

遍历二叉树与线索二叉树

遍历二叉树与线索二叉树

遍历二叉树与线索二叉树

遍历二叉树与线索二叉树

遍历二叉树与线索二叉树