第12讲线索二叉树

6.4 线索化二叉树从前面的讨论可知，遍历二叉树就是将非线性结构的二叉树线性化，即按一定规则将二叉树中的结点排列成一个线性序列依次访问。

如图6.20(a)所示的二叉树，经中序遍历得到线性序列：BADEC，经前序遍历得到线性序列：ABCDE，经后序遍历得到线性序列：BEDCA。

在这些线性序列中，二叉树中的每个结点（除第一个和最后一个外）有且仅有唯一的一个前趋和唯一的一个后继，很容易找到各个结点的直接前驱和直接后继。

但当以二叉链表作为二叉树的存储结构时，只能找到结点的左、右孩子，而不能直接找到前驱和后继，只有在遍历的动态过程中得到这些信息。

如果将这些信息在第一次遍历时保存起来，在需要再次对二叉树进行“遍历”时就可以将二叉树视为线性结构进行访问，从而简化遍历操作。

那么，如何存储遍历中得到的结点前驱和后继的信息呢？一个简单的办法是在每个结点上增加两个指针域fwd和bkwd，分别指向存储遍历中得到的结点前驱和后继。

fwd L child data R child bkwd这是采用多重链表来表示二叉树。

这种方法虽简单易行，但这种结构的存储密度将大大降低，浪费存储空间。

另一种方法，是利用原有链域L child 和R child的空链域。

在n个结点的二叉链表中有2n个孩子链域，其中仅有n-1个链域是用来指示结点的左右孩子，而另外n+1个链域是空链域。

现在把这些空链域利用起来，使其指向结点的前驱或后继；对那些原来就不为空的链域，则仍然指向左或右孩子。

如果把指向前驱和后继的指针称为线索（Thread），那么，如何区分指向左、右孩子的指针和指向前驱、后继的线索呢？在原结点结构上增加标志域定义为：0 Lchild为左指针，指向左孩子0 Rchild为右指针，指向右孩子ltag＝rtag＝1 Lchild为左线索，指向前驱 1 Rchild为右线索，指向后继以这种结点构成的二叉链表作为二叉树的存储结构，叫做线索链表，其C语言类型说明如下：Typedef struct ThreadTNode{enum{0，1} ltag, rtag;Elem Type data;Struct ThreadTNode *Lchild, *Rchild;}ThreadTNode, *ThreadTree;为了节省内存空间，我们用C语言的位段方法将结点中的左标志域和右标志域与数据域合并在一个存储单元中（即各用一位表示左标志和右标志，其余各位表示结点值）。

线索二叉树的运算1．查找某结点*p在指定次序下的前趋和后继结点（1）在中序线索二叉树中，查找结点*p的中序后继结点在中序线索二叉树中，查找结点*p的中序后继结点分两种情形：①若*p的右子树空(即p->rtag为Thread)，则p->rchild为右线索，直接指向*p的中序后继。

【例】下图的中序线索二叉树中，结点D的中序后继是A。

②若*p的右子树非空(即p->rtag为Link)，则*p的中序后继必是其右子树中第一个中序遍历到的结点。

也就是从*p的右孩子开始，沿该孩子的左链往下查找，直至找到一个没有左孩子的结点为止，该结点是*p的右子树中"最左下"的结点，即*P的中序后继结点。

【例】上图的中序线索二叉树中：A的中序后继是F，它有右孩子；F的中序后继是H，它无右孩子；B的中序后继是D，它是B的右孩子。

在中序线索二叉树中求中序后继结点的过程可【参见动画演示】，具体算法如下：BinThrNode *InorderSuccessor(BinThrNode *p){//在中序线索树中找结点*p的中序后继，设p非空BinThrNode *q；if (p->rtag==Thread) //*p的右子树为空Return p->rchild；//返回右线索所指的中序后继else{q=p->rchild；//从*p的右孩子开始查找while (q->ltag==Link)q=q->lchild；//左子树非空时，沿左链往下查找return q；//当q的左子树为空时，它就是最左下结点} //end if}该算法的时间复杂度不超过树的高度h，即O(h)。

（2）在中序线索二叉树中查找结点*p的中序前趋结点中序是一种对称序，故在中序线索二叉树中查找结点*p的中序前趋结点与找中序后继结点的方法完全对称。

具体情形如下：①若*p的左子树为空，则p->1child为左线索，直接指向*p的中序前趋结点；【例】上图所示的中序线索二叉树中，F结点的中序前趋结点是A②若*p的左子树非空，则从*p的左孩子出发，沿右指针链往下查找，直到找到一个没有右孩子的结点为止。

1在线索二叉树中如何求先序、中序的前驱、后继，为什么后续线索二叉树是不完备的？先序前驱：若左标志为1，则左链为线索，指示其前驱；否则a) 若该结点是二叉树的根，则其前驱为空；b) 若该结点是其双亲的左孩子或是其双亲的右孩子且其双亲没有左子树，则其前驱为其双亲；c) 若该结点是其双亲的右孩子且其双亲有左子树，则其前驱为其双亲的左子树中的先序遍历列出的最后一个结点。

先序后继：若右标志为1，则右链为线索，指示其后继；否则，如果有左子树则遍历左子树第一个访问的结点，为其后继；如果没有左子树则遍历右子树第一个访问的结点，为其后继；中序前驱：若左标志为1，则左链为线索，指示其前驱；否则，遍历其左子树最后访问的结点，为其前驱中序后继：若右标志为1，则右链为线索，指示其后继；否则，遍历其右子树第一个访问的结点，为其后继后续后继：a) 若该结点是二叉树的根，则其后继为空；b) 若该结点是其双亲的右孩子或是其双亲的左孩子且其双亲没有右子树，则其后继为其双亲；c) 若该结点是其双亲的左孩子且其双亲有右子树，则其后继为其双亲的右子树中的后序遍历列出的第一个结点。

求后续后继需要知道双亲结点，而二叉链表无法找到双亲，因此不完备：5如果只想得到一个序列中前k（k>=5）个最小元素的部分排序序列,可以采用哪些排序方法，最好采用哪种排序方法？1插入、快速、归并需要全体排序不合适2起泡、简单选择、堆可以。

堆完成查找总时间：4n+klogn,起泡和简单选择总时间kn,因此堆较好。

5荷兰国旗问题分析：这个问题我们可以将这个问题视为一个数组排序问题，这个数组分为前部，中部和后部三个部分，每一个元素（红白蓝分别对应0、1、2）必属于其中之一。

由于红、白、蓝三色小球数量并不一定相同，所以这个三个区域不一定是等分的，也就是说如果我们将整个区域放在[0,1]的区域里，由于三色小球之间数量的比不同（此处假设1:2:2），可能前部为[0,0.2)，中部为[0.2,0.6)，后部为[0.6,1]。

简述二叉树的五种形态二叉树是一种常用的数据结构，它由节点组成，每个节点最多有两个子节点。

根据节点的分布情况，二叉树可以分为五种形态，分别是满二叉树、完全二叉树、平衡二叉树、搜索二叉树和线索二叉树。

一、满二叉树满二叉树是指除了叶子节点外，每个节点都有两个子节点的二叉树。

也就是说，满二叉树的所有层都是满的，并且最后一层的叶子节点都靠左排列。

满二叉树的节点数可以通过公式计算得到，假设树的高度为h，则节点数为2^h - 1。

满二叉树的特点是结构简单，查找速度快。

在满二叉树中，任意两个节点的路径长度都相同。

二、完全二叉树完全二叉树是指除了最后一层之外，其他层都是满的，并且最后一层的叶子节点都靠左排列的二叉树。

完全二叉树的特点是节点数较少，结构相对简单。

完全二叉树通常用数组来表示，因为它的节点之间的关系可以通过数组的下标来表示。

在完全二叉树中，任意一个节点的左子节点的下标为2i，右子节点的下标为2i+1。

三、平衡二叉树平衡二叉树是指左右子树的高度差不超过1的二叉树。

平衡二叉树的特点是查找、插入和删除的时间复杂度都为O(logn)，其中n是节点的数量。

平衡二叉树的高度可以通过节点的平衡因子来计算，平衡因子定义为左子树的高度减去右子树的高度。

平衡因子的取值范围为-1、0和1，当平衡因子的绝对值大于1时，需要通过旋转操作来调整树的平衡性。

四、搜索二叉树搜索二叉树，也称为二叉搜索树或排序二叉树，是一种特殊的二叉树。

它的特点是对于树中的任意一个节点，其左子树中的所有节点都小于它，右子树中的所有节点都大于它。

搜索二叉树的中序遍历结果是一个递增的有序序列。

搜索二叉树的特点是可以快速地查找某个节点，时间复杂度为O(logn)，其中n是节点的数量。

但是，如果搜索二叉树不平衡，即左子树或右子树过深，则会导致查找的时间复杂度退化为O(n)。

五、线索二叉树线索二叉树是对二叉树进行了优化的数据结构，它通过添加指向前驱和后继节点的线索，使得遍历操作更加高效。

二叉树知识点总结二叉树是数据结构中常见且重要的一种形式，它可以用于解决许多实际问题，并在算法和编程中扮演着重要的角色。

本文将对二叉树的基本概念、性质以及常见的应用进行总结。

一、基本概念和性质1. 二叉树的定义：二叉树是一种特殊的树形结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

左子节点小于等于父节点，右子节点大于等于父节点。

2. 二叉树的特点：二叉树具有递归性质，即每个子节点都可以视为一棵二叉树。

同时，二叉树的遍历方式有前序遍历、中序遍历、后序遍历和层次遍历等。

3. 二叉树的性质：a. 二叉树的第i层至多有2^(i-1)个节点；b. 深度为k的二叉树至多有2^k - 1个节点；c. 对于任意一棵二叉树，若其叶节点数为n0，度为2的节点数为n2，则n0 = n2 + 1；d. 具有n个节点的完全二叉树的深度为(log2 n) + 1。

二、二叉树的应用1. 二叉搜索树：二叉搜索树（BST）是一种特殊的二叉树，它满足左子节点小于父节点，右子节点大于父节点的条件。

BST的特性使得查找、插入和删除操作的时间复杂度为O(log n)，因此在数据库、图形处理等领域经常被使用。

2. 平衡二叉树：由于BST的特性，如果数据插入的顺序不合理，可能导致树的高度过高，使得操作效率降低。

为了解决这个问题，人们提出了平衡二叉树（AVL）的概念。

AVL树通过旋转操作保持树的平衡，使得左右子树的高度差不超过1，从而保证了操作的效率。

3. 红黑树：红黑树是一种自平衡的二叉查找树，它在AVL树的基础上做了一些调整。

红黑树的特点是节点可以为红色或黑色，并且满足以下规则：根节点为黑色，叶节点为黑色且为空，红色节点的两个子节点都是黑色。

红黑树在C++标准库（STL）中的map和set等容器中得到了广泛应用。

4. 堆：堆是一种完全二叉树，它可以分为大顶堆和小顶堆。

大顶堆中，父节点的值大于或等于两个子节点的值，小顶堆则相反。

堆在排序算法中有广泛应用，如堆排序、优先队列等。

二叉检索树构造摘要：一、二叉检索树的定义和性质1.二叉检索树的定义2.二叉检索树的性质二、二叉检索树的构造方法1.顺序插入法2.二叉树转化法三、二叉检索树的应用1.查找2.插入3.删除正文：二叉检索树是一种特殊的二叉树，具有以下性质：若左子树不为空，则左子树上所有结点的值均小于根结点的值；若右子树不为空，则右子树上所有结点的值均大于根结点的值；左、右子树也分别为二叉检索树。

基于这些性质，二叉检索树可以用来实现高效的查找、插入和删除操作。

一、二叉检索树的定义和性质1.二叉检索树的定义二叉检索树，又称有序二叉树，是一种特殊的二叉树。

每个结点具有以下性质：若左子树不为空，则左子树上所有结点的值均小于根结点的值；若右子树不为空，则右子树上所有结点的值均大于根结点的值；左、右子树也分别为二叉检索树。

2.二叉检索树的性质二叉检索树具有以下几个基本性质：（1）若左子树不为空，则左子树上所有结点的值均小于根结点的值。

（2）若右子树不为空，则右子树上所有结点的值均大于根结点的值。

（3）左、右子树也分别为二叉检索树。

二、二叉检索树的构造方法1.顺序插入法顺序插入法是构建二叉检索树的最常用方法。

具体步骤如下：（1）将第一个结点插入到空树中，作为根结点。

（2）将后续结点依次插入到树中。

插入过程中，若当前结点的值小于根结点的值，插入到左子树上；若当前结点的值大于根结点的值，插入到右子树上。

（3）重复步骤（2），直到所有结点都插入完毕。

2.二叉树转化法二叉树转化法是一种更高效的构建方法，适用于已经存在一棵二叉树的场合。

具体步骤如下：（1）遍历二叉树，将每个结点的左子结点转化为一个新结点，并将原结点的值赋给新结点。

（2）将新结点插入到原结点的左子树上。

（3）重复步骤（2），直到所有结点都转化完毕。

三、二叉检索树的应用1.查找在二叉检索树中，查找某个结点的过程可以通过遍历树来完成。

具体步骤如下：（1）若要查找的值小于根结点的值，递归地遍历左子树。