数据结构与算法之构建二叉搜索树

构建二叉搜索树

构建二叉搜索树

参考张dayu视频，原地址如下：数据结构1800题型-先/中/后序线索二叉树的构建_哔哩哔哩_bilibili

步骤

1. 根据题目求遍历(前/中/后序遍历)序列
2. 看空域：也就是左右子树空树的个数
3. 根据1求出的遍历序列开始连线

线索二叉树的介绍

基本概念

定义：遍历二叉树是以一定的跪着将二叉树中的结点排列成有一个线形序列，从而得到几种遍历序列，使得该序列中的每个结点(第一个和最后一个节点除外)都有一个直接前驱和直接后继。直接前驱和直接后驱使按照遍历序列的顺序来的(不是逻辑上的左右子树或父子关系)。
规定：若无左子树，令lchild指向其前驱结点；若无右子树，令rchild指向其后继节点。

易考点

都是画图，从图像上看出来的

1. 在中序线索树中，若某结点有右孩子，则其后继结点是它的右子树的最左下结点
2. 在中序线索树中，若某结点有左孩子，则其前驱结点是它的左子树的最右下结点
3. 线索二叉树是利用二叉树的n+1个空指针来存放结点的前驱和后继信息的
4. 后序线索二叉树的遍历需要栈的支持
5. 如果是普通的二叉树，不管是递归算法(隐含递归栈)，还是非递归算法(使用栈)都是需要栈的支持的。那么，现在不需要了，原因:使用了线索二又树

代码实现(考的不多，但是也得理解)

每一棵二叉树上，很多结点都含有未使用的指向NULL的指针域。除了度为2的结点，度为 1 的结点，有一个空的指针域；叶子结点两个指针域都为NULL。

规律：在有 n 个结点的二叉链表中必定存在 n+1 个空指针域。

线索二叉树实际上就是使用这些空指针域来存储结点之间前趋和后继关系的一种特殊的二叉树。
线索二叉树中，如果结点有左子树，则 lchild 指针域指向左孩子，否则 lchild 指针域指向该结点的直接前趋；同样，如果结点有右子树，则 rchild 指针域指向右孩子，否则 rchild 指针域指向该结点的直接后继。
为了避免指针域指向的结点的意义混淆，需要改变结点本身的结构，增加两个标志域，如图所示。

• LTag 和 RTag 为标志域。实际上就是两个布尔类型的变量：
  • LTag 值为 0 时，表示 lchild 指针域指向的是该结点的左孩子；为 1 时，表示指向的是该结点的直接前趋结点；
  • RTag 值为 0 时，表示 rchild 指针域指向的是该结点的右孩子；为 1 时，表示指向的是该结点的直接后继结点。

结点结构代码实现：

#define TElemType int//宏定义，结点中数据域的类型
//枚举，Link为0，Thread为1
typedef enum PointerTag{
    Link,
    Thread
}PointerTag;
//结点结构构造
typedef struct BiThrNode{
    TElemType data;//数据域
    struct BiThrNode* lchild,*rchild;//左孩子，右孩子指针域
   
    PointerTag Ltag,Rtag;//标志域，枚举类型
}BiThrNode,*BiThrTree;
1
2
3
4
5
6
7
8
9
10
11
12
13

表示二叉树时，使用上文所示的结点结构构成的二叉链表，被称为线索链表；构建的二叉树称为线索二叉树。
线索链表中的“线索”，指的是链表中指向结点前趋和后继的指针。二叉树经过某种遍历方法转化为线索二叉树的过程称为线索化。

对二叉树进行线索化

将二叉树转化为线索二叉树，实质上是在遍历二叉树的过程中，将二叉链表中的空指针改为指向直接前趋或者直接后继的线索。

线索化的过程即为在遍历的过程中修改空指针的过程。

在遍历过程中，如果当前结点没有左孩子，需要将该结点的 lchild 指针指向遍历过程中的前一个结点，所以在遍历过程中，设置一个指针（名为 pre ），时刻指向当前访问结点的前一个结点。
代码实现（拿中序遍历为例）：

//中序对二叉树进行线索化
void InThreading(BiThrTree p){
    //如果当前结点存在
    if (p) {
        InThreading(p->lchild);//递归当前结点的左子树，进行线索化
        //如果当前结点没有左孩子，左标志位设为1，左指针域指向上一结点 pre
        if (!p->lchild) {
            p->Ltag=Thread;
            p->lchild=pre;
        }
        //如果 pre 没有右孩子，右标志位设为 1，右指针域指向当前结点。
        if (!pre->rchild) {
            pre->Rtag=Thread;
            pre->rchild=p;
        }
        pre=p;//线索化完左子树后，让pre指针指向当前结点
        InThreading(p->rchild);//递归右子树进行线索化
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

注意：中序对二叉树进行线索化的过程中，在两个递归函数中间的运行程序，和之前介绍的中序遍历二叉树的输出函数的作用是相同的。

将中间函数移动到两个递归函数之前，就变成了前序对二叉树进行线索化的过程；后序线索化同样如此。