《数据结构》 第六章(中)
《 数据结构》 第六章(中)
数据结构 632线索二叉树 在二叉树的先序、中序或后序遍历序列中两个相邻 的结点互称为前驱与后继。 指向前驱或后继结点的指针称为线索。 加上线索的二叉链表表示的二叉树叫线索二叉树。 对二叉树按某种遍历次序使其变为线索二叉树的过 程叫线索化。 实现:在有n个结点的二叉链表中必定有n+1个空 链城。在线索二叉树的结点中增加两个标志城 LTag:著LTag=0, Child域指向左孩子 若LTag=1, Child域指向其前驱。 RTag:着RTag=0, 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 Child LTag data RTag rchild A BO OD B E 先序序列: ABCDE 先序线索二叉树
数据结构 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 AIBO 0D1∧ 1C E1 中序序列: BCAED 中序线索二叉树
数据结构 tjm A B C D E A B D C E T 中序序列：BCAED 中序线索二叉树 0 0 1 0 0 1 1 1 ^ 1 1 ^
数据结构 0A0 B|0 B D 1|E 后序序列: CEDA 后序线索二叉树
数据结构 tjm A B C D E A B D C E T 后序序列：CBEDA 后序线索二叉树 0 0 1 0 0 1 ^ 1 1 1 1