4树第三部分.pdf

树 树的定义和基本概念 二叉树定义和基本概念 遍历二叉树 线索二叉树 树、森林与二叉树的转换 赫夫曼树及其应用 数据结构 线索二叉树 线索二叉树的定义 二叉树的线索化 线索二叉树的遍历 数据结构 线索二叉树 T A A B C B ⋀ C ⋀ D ⋀ E ⋀ F D E F ⋀ G ⋀ ⋀ H ⋀ ⋀ I ⋀ G H I 二叉树 二叉链表存储结构  提出问题： ① 共有n+1个空指针域。如何充分利用空指针域？ ② 如何保存二叉树中每个结点在线性序列中的直接前驱和直接后继？ • 遍历二叉树以一定规则将二叉树中结点排列成一个线性序列，得到二叉树中结点的前 序序列、中序序列或后序序列。 • 对一个非线性结构进行线性化操作，使每个结点（除首尾）在线性序列中有且仅有一 个直接前驱和直接后继。 数据结构 3 数据结构 线索二叉树 解决办法：利用二叉链表的空闲指针域来存放结点的直接前驱和 直接后继。 • 指向结点前驱和后继的指针，叫做线索； • 按照某种次序遍历，加上线索的二叉链表，叫做线索链表； • 相应的二叉树称为线索二叉树。 • 对二叉树以某种次序遍历使其变为线索二叉树的过程，叫 做线索化。 数据结构 线索二叉树 以中序遍历为例，若能将中序序列中每个结点前驱、后继信息保存起来， 以后再中序遍历二叉树时就可以根据所保存的结点前驱、后继信息对二叉 树进行遍历。 A 孩子指针 前趋指针 B C 后继指针 D E F G H 线索二叉树 中序遍历序列：DBHEAFCG 在中序序列中，D的后继是B，H的前趋是B，后继是E… 数据结构 线索二叉树  若结点有左孩子，则Lchild指向其左孩子，否则指向其直接 前驱；  若结点有右孩子，则Rchild指向其右孩子，否则指向其直接 后继； 问题：如何知道某一结点的Lchild是指向左孩子还是前驱？ Rchild是指向右孩子还是后继？ 解决：增加两个标志域Ltag ，Rtag 。 Lchild Ltag data Rchild Rtag 0：Rchild域指示结点的右孩子 0：Lchild域指示结点的左孩子 Rtag = Ltag = 1：Rchild域指示结点的后继 1：Lchild域指示结点的前驱 数据结构