《数据结构》课程PPT教学课件（2015）第6章 树和二叉树（中）

《数据结构》 第六章树和二叉树（中）

《 数据结构》 第六章 树和二叉树 (中)

数据结构 6.3.2线索二叉树 在二叉树的先序、中序或后序遍历序列中两个相邻 的结点互称为前驱与后继。 指向前驱或后继结点的指针称为线索。 加上线索的二叉链表表示的二叉树叫线索二叉树。 对二叉树按某种遍历次序使其变为线索二叉树的过 程叫线索化。 实现：在有n个结点的二叉链表中必定有n+1个空 链域。在线索二叉树的结点中增加两个标志域： LTag:若LTag=0,Ichild域指向左孩子； 若LTag=1,Ichild域指向其前驱。 RTag:若RTag=O,rchild域指向右孩子； 若RTag=1,rchild域指向其后继

数据结构 tjm 6.3.2 线索二叉树 在二叉树的先序、中序或后序遍历序列中两个相邻 的结点互称为前驱与后继。 指向前驱或后继结点的指针称为线索。 加上线索的二叉链表表示的二叉树叫线索二叉树。 对二叉树按某种遍历次序使其变为线索二叉树的过 程叫线索化。 实现：在有n个结点的二叉链表中必定有n+1个空 链域。在线索二叉树的结点中增加两个标志域： LTag :若 LTag=0, lchild域指向左孩子； 若 LTag=1, lchild域指向其前驱。 RTag :若 RTag=0, rchild域指向右孩子； 若 RTag=1, rchild域指向其后继

数据结构 线索链表的类型定义参见P133 Ichild LTag data RTag rchild 0A0、 0D1 B E 1C11E1 先序序列：ABCDE 先序线索二叉树 m

数据结构 tjm A B C D E A B D C E T 先序序列：ABCDE 先序线索二叉树 0 0 1 0 0 1 1 1 1 1 ^ lchild LTag data RTag rchild 线索链表的类型定义参见P133

数据结构 A 0A0 B O D 1 E 中序序列：BCAED 中序线索二叉树 tjm

数据结构 tjm A B C D E A B D C E T 中序序列：BCAED 中序线索二叉树 0 0 1 0 0 1 1 1 ^ 1 1 ^

数据结构 0A0 A .1B0 E 1c11E1 后序序列：CBEDA 后序线索二叉树 m

数据结构 tjm A B C D E A B D C E T 后序序列：CBEDA 后序线索二叉树 0 0 1 0 0 1 ^ 1 1 1 1

数据结构 B D 0A( 1B0 1E1 0 中序序列：BCAED 中序线索二叉树 头结点：LTag=O,Ichild指向 1B0 根结点。RTag=l,rchild:指 向遍历序列中最后一个结点。 遍历序列中第一个结点的 1E1 Ichild:域和最后一个结点的 中序序列：BCAED rchild:域都指向头结点。 带头结点的中序线索二叉树

数据结构 tjm A B D C E T 中序序列：BCAED 中序线索二叉树 0 0 1 0 0 1 1 1 ^ 1 1 ^ A B C D E 头结点：LTag=0, lchild指向 根结点。RTag=1, rchild指 向遍历序列中最后一个结点。 遍历序列中第一个结点的 lchild域和最后一个结点的 rchild域都指向头结点。 0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T 中序序列：BCAED 带头结点的中序线索二叉树 0 1

数据结构 按中序线索化二叉树 算法参见P134算法 A B D E P->A pre thr /P 0A0 0B0 O D O 0 C O 0E O

数据结构 tjm A B C D E thrt 0 1 pre p P->A A B D C E T ^ ^ ^ ^ ^ ^ 0 0 0 0 0 0 0 0 0 0 按中序线索化二叉树 算法参见P134算法

数据结构 B P->B P->A E pre /1 0A0 p tjm

数据结构 tjm A B C D E A B D C E T ^ ^ ^ ^ ^ ^ thrt 0 1 pre p P->A P->B 0 0 0 0 0 0 0 0 0 0

数据结构 B D P->B P->A E pre thry o1 0A0 0B0 O D O P-NULL O C O 0E0A

数据结构 tjm A B C D E A B D C E T ^ ^ ^ ^ ^ ^ thrt 0 1 pre P=NULL P->A P->B 0 0 0 0 0 0 0 0 0 0

数据结构 A B D P->A E pre thrtr 0A0 1B0 0 CO0 EO tjm

数据结构 tjm A B C D E A B D C E T ^ ^ ^ ^ ^ ^ thrt 0 1 pre P P->A 0 0 0 0 0 0 0 0 0 0 1