【数据结构】二叉树：结构优雅，搜索高效如疾风

一、前言

二叉树就像是一个数字的花园，数值就像花朵，节点就像枝丫。每个节点都有它自己的数值，而且有时还会伸出一些小枝丫，分别指向它的左右两个子节点。这些小枝丫就像是分支一样，把花园中的花朵串在了一起。

通过这些小枝丫，我们可以在花园中找到需要的花朵，或是将新的花朵种下去。因为每个节点只有两个小枝丫，所以整个花园呈现出了一种非常有序的形式。这种结构可以让我们在最短的时间内查找到需要的花朵，而不必花费大量时间在花园中漫无目的地寻找。

二、树形结构

1、树的定义

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

2、相关概念

1. 节点（Node）：树中的每个元素称为节点。节点可以有零个、一个或多个子节点。
2. 根节点（Root Node）：树的顶层节点，没有父节点的节点。
3. 子节点（Child Node）：一个节点的直接下级称为该节点的子节点。
4. 父节点（Parent Node）：一个节点的直接上级称为该节点的父节点。
5. 叶节点（Leaf Node）：没有子节点的节点称为叶节点，叶子节点的度都为0。
6. 边（Edge）：连接父节点和子节点的线称为边。
7. 路径（Path）：从一个节点到另一个节点的节点序列称为路径。
8. 层（Level）：根节点所在的层为第一层，其子节点所在的层为第二层，以此类推。
9. 高度（Height）：树中节点的最大层数称为树的高度。
10. 深度（Depth）：从根节点到某一节点所经过的边的数量称为该节点的深度。
11. 度（Degree）：一个节点的子节点数称为该节点的度。
    

3、重要结论

1. 节点的高度：节点到叶子节点的最长路径（边数）。
2. 节点的深度 = 根节点到这个节点所经历的边的个数。
3. 节点的层数 = 节点的深度+1。
4. 树的高度 = 根节点的高度。

三、二叉树

1、二叉树的定义

二叉树：每个节点最多两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。

2、二叉树的性质

1. 二叉树的每个节点最多有两个子节点，所以它的度数不超过2。
2. 左子树和右子树是有顺序的，即使节点只有一个子节点，也必须明确它是左子节点还是右子节点。
3. 左子树和右子树也是二叉树，它们本身也遵循上述两个性质。
4. 叶节点是没有子节点的节点，即度数为0的节点。
5. 二叉树中度为0的节点比度为2的节点多一个。
   

3、二叉树的分类

Ⅰ、完全二叉树

完全二叉树(complete binary tree)：除了最后一层，上面的层全是满的，且最后一层只缺少右侧的节点。

重要性质：

• 编号为i的子节点：左孩子编号为：2 * i，右孩子编号为：2 * 1+ 1。

  利用这个性质，可以通过父节点的编号计算得到子节点的编号。

• 可以用连续空间进行存储（数组）。

Ⅱ、满二叉树

满二叉树(full binary tree)：每个非叶子节点都是一个度为2的节点，叶子节点的度为0，所以满二叉树是没有度为1的节点。

Ⅲ、完美二叉树

完美二叉树(perfect binary tree)：每个非叶子节点都是度为2的节点，并且每个非叶子节点的两个子节点具有相同的高度，每一层都是满的。

四、二叉树的实现

1、二叉树的结构定义

//定义二叉树节点结构体，包含节点值、左子节点指针和右子节点指针
typedef struct Node {
    int key; //关键值
    struct Node *lchild, *rchild;  //左子节点指针和右子节点指针
} Node;

2、新增二叉树的节点

// 创建新节点并初始化函数，为节点分配内存空间，设定节点值，将左右子节点指针置空
Node *getNewNode(int key) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->key = key;
    p->lchild = p->rchild = NULL;
    return p;
}

3、销毁二叉树的所有节点

// 销毁二叉树的所有节点
void clear(Node *root) {
    // 如果传入的节点为空，直接返回，不进行任何操作
    if (root == NULL) return ;
    // 递归清除左子树的内存，如果左子节点存在，将调用clear函数，直到遍历到叶子节点
    clear(root->lchild);
    // 递归清除右子树的内存，如果右子节点存在，将调用clear函数，直到遍历到叶子节点
    clear(root->rchild);
    // 当左右子树都被清除后，释放当前节点所占用的内存空间
    free(root);
    // 返回上一层递归
    return ;
}

4、向二叉树中插入新节点

这里有个技巧值得注意，在插入节点时使用了随机数来控制插入的方向，这样可以避免插入节点时二叉树的形状过于单一，提高了二叉树的随机性和平衡性。

// 向二叉树插入新节点的函数
Node *insert(Node *root, int key) {
    // 如果当前节点为空，创建一个新的节点并返回
    if (root == NULL) 
        return getNewNode(key);
    // 生成一个随机数并取余2，用以决定新节点是插入到左子树还是右子树
    if (rand() % 2) {
    // 如果随机数为奇数，将新节点插入到左子树
        root->lchild = insert(root->lchild, key);
    } else {
    // 如果随机数为偶数，将新节点插入到右子树
        root->rchild = insert(root->rchild, key);
    }
    // 返回当前节点（不论是否插入新节点，都需要返回当前节点）
    return root;
}

5、广搜打印二叉树的节点

bfs函数首先初始化队列头和尾指针，并将根节点加入队列。然后当队列不为空时（即队列头指针小于尾指针），从队列头部取出一个节点并打印其值。

接着检查当前节点是否有左子节点和右子节点，如果有则分别将它们加入队列尾部，并打印相应的信息。处理完当前节点后，队列头指针后移一位。最后，当所有节点都被遍历完成后，函数返回。

都知道，BFS是使用使用队列来实现层次遍历。在 BFS 过程中，队列起到了“先进先出”的作用。当遍历到一个节点时，将其子节点加入队列的尾部。然后，从队列头部取出下一个待处理的节点，继续遍历。这种方式保证了节点按照层次顺序被访问。如下图所示。

// 定义两个整数变量，分别表示队列头部和尾部指针
int head, tail;
// 使用广度优先搜索遍历并打印二叉树节点的函数
void bfs(Node *root) {
    // 初始化队列头和尾指针
    head = tail = 0;
    // 将根节点加入队列
    queue[tail++] = root;
    // 当队列不为空时，继续遍历
    while (head < tail) {
        // 取出队列头部的节点
        Node *node = queue[head];
        // 打印当前节点的值
        printf("\nnode : %d\n", node->key);
        // 如果当前节点有左子节点，将其加入队列中并打印
        if (node->lchild) {
            queue[tail++] = node->lchild;
            printf("\t%d->%d (left)\n", node->key, node->lchild->key);
        }
        // 如果当前节点有右子节点，将其加入队列中并打印
        if (node->rchild) {
            queue[tail++] = node->rchild;
            printf("\t%d->%d (right)\n", node->key, node->rchild->key);
        }
        // 队列头指针后移，表示已处理完当前节点
        head++;
    }
   	    // 函数结束，返回
    return;
}

6、深搜打印二叉树的节点

dfs函数首先检查当前节点是否为空，如果为空，则直接返回。然后递增全局变量tot，并记录当前节点访问开始的时间戳。

接下来，如果当前节点有左子节点和右子节点，则分别递归访问它们。完成子节点的访问后，再次递增tot，并记录当前节点访问结束的时间戳。最后，打印当前节点的值和访问时间戳区间。当所有节点都被遍历完成后，函数返回。

同样DFS是使用栈来实现遍历，DFS会从起始节点开始，将其压入栈中。然后，它会弹出栈顶节点并访问其未被访问的相邻节点，将这些节点压入栈中。接下来，它会重复弹出栈顶节点并访问其相邻节点的过程，直到栈为空。

// 定义一个全局变量 tot，用于记录节点访问时间戳
int tot = 0;
// 使用深度优先搜索遍历并计算二叉树节点的访问时间戳区间的函数
void dfs(Node *root) {
    // 如果当前节点为空，直接返回
    if (root == NULL) return;
    // 定义两个局部变量，分别表示节点访问开始和结束的时间戳
    int start, end;
    // 访问当前节点，递增时间戳
    tot += 1;
    // 记录当前节点访问开始的时间戳
    start = tot;
    // 如果有左子节点，递归访问左子节点
    if (root->lchild) dfs(root->lchild);
    // 如果有右子节点，递归访问右子节点
    if (root->rchild) dfs(root->rchild);
    // 访问当前节点的子节点完成，递增时间戳
    tot += 1;
    // 记录当前节点访问结束的时间戳
    end = tot;
    // 打印当前节点的值和访问时间戳区间
    printf("%d : [%d, %d]\n", root->key, start, end);
    // 函数结束，返回
    return;
}

五、遍历与线索化

为了后续实现线索化，我们这里与前文相比，多定义了两个变量，用来记录是否为线索。

加入了线索，前面的其他代码也可以都优化一下。

// 定义二叉树
typedef struct Node {    
    int key;    // 节点的值
    int ltag, rtag;    // 标记节点左右子树指针,如果为1证明是线索，如果为0，仅是一条边。                 
    struct Node *lchild, *rchild;    // 左右子树指针
} Node;    // 定义一个名为 Node 的结构体类型的别名 Node
// 创建一个新的节点
Node *getNewNode(int key) {    
    Node *p = (Node *)malloc(sizeof(Node));    // 分配节点空间
    p->key = key;    // 初始化节点的值
    p->ltag = p->rtag = 0;    // 初始化节点的标记
    p->lchild = p->rchild = NULL;    // 初始化节点的左右子树指针
    return p;    // 返回新的节点指针
}
 // 获取指定节点的后继节点
Node *getNext(Node *root) {
    if (root->rtag == 1) return root->rchild; // 如果指定节点的右线索标记为 1，说明其后继节点为其右子节点的后继节点，直接返回其右子节点
    root = root->rchild; // 否则将指定节点移动到其右子节点
    while (root->ltag == 0 && root->lchild) root = root->lchild; // 如果右子节点存在左子树，就一直向左遍历，直到找到最左边的叶子节点
    return root; // 返回最左边的叶子节点，即指定节点的后继节点
}

 // 向二叉树中插入一个节点
Node *insert(Node *root, int key) {   
    if (root == NULL) return getNewNode(key);    // 如果当前节点为空，创建一个新的节点
    if (rand() % 2) root->lchild = insert(root->lchild, key);    // 如果随机数为奇数，向左子树插入新节点
    else root->rchild = insert(root->rchild, key);    // 如果随机数为偶数，向右子树插入新节点
    return root;    // 返回根节点指针
}
 //释放二叉树中的所有节点所占用的内存空间
void clear(Node *root) {   
    if (root == NULL) return ;    // 如果当前节点为空，直接返回
    if (root->ltag == 0) clear(root->lchild);    // 如果左子树不为空，递归释放左子树
    if (root->rtag == 0) clear(root->rchild);    // 如果右子树不为空，递归释放右子树
    free(root);    // 释放当前节点所占用的内存空间
    return ;    // 返回
}

1、二叉树的遍历

在节点结构体中增加了两个标记 ltag 和 rtag，分别用来标记左右子树指针是否为线索。如果一个节点的 ltag 或 rtag 标记为 1，说明该节点的左或右子树指针是一个指向序列中该节点的前驱或后继的线索；否则，该节点的左或右子树指针指向的是该节点的真正的左子树或右子树。

Ⅰ、前序遍历

二叉树的前序遍历是指按照根节点、左子树、右子树的顺序遍历二叉树的所有节点。

// 递归实现前序遍历
void pre_order(Node *root) {
    // 如果当前节点为空，直接返回
    if (root == NULL) return ;
    // 输出当前节点的值
    printf("%d ", root->key);
    // 如果当前节点的左子树不为空，递归遍历左子树
    if (root->ltag == 0) pre_order(root->lchild);
    // 如果当前节点的右子树不为空，递归遍历右子树
    if (root->rtag == 0) pre_order(root->rchild);
    return ;
}

Ⅱ、中序遍历

二叉树的中序遍历是指按照左子树、根节点、右子树的顺序遍历二叉树的所有节点。

 // 递归实现中序遍历
void in_order(Node *root) {   
    if (root == NULL) return ;    // 如果当前节点为空，直接返回
    if (root->ltag == 0) in_order(root->lchild);    // 如果当前节点的左子树不为线索，则递归遍历左子树
    printf("%d ", root->key);    // 输出当前节点的值
    if (root->rtag == 0) in_order(root->rchild);    // 如果当前节点的右子树不为线索，则递归遍历右子树
    return ;    // 返回
}

Ⅲ、后序遍历

二叉树的后序遍历是指按照左子树、右子树、根节点的顺序遍历二叉树的所有节点。

 // 递归实现后序遍历
void post_order(Node *root) {   
    if (root == NULL) return ;    // 如果当前节点为空，直接返回
    if (root->ltag == 0) post_order(root->lchild);    // 如果当前节点的左子树不为线索，则递归遍历左子树
    if (root->rtag == 0) post_order(root->rchild);    // 如果当前节点的右子树不为线索，则递归遍历右子树
    printf("%d ", root->key);    // 输出当前节点的值
    return ;    // 返回
}

2、二叉树的线索化

二叉树的线索化是一种优化二叉树遍历的方法，它将二叉树的空指针利用起来，将空指针指向中序遍历的前驱或后继节点，从而避免了递归或使用栈等数据结构带来的额外空间开销。

使用二叉树的线索化，可以将二叉树的递归遍历改为非递归遍历，让二叉树的遍历表现的像一个链表一样。

中序线索化

索化二叉树中实现中序线索化遍历，我们的方法主要是将二叉树中序遍历的每个节点都通过线索连接起来，以便在 O(1) 时间内可以访问任意节点的前驱和后继。

// 定义两个指针变量 pre_node 和 inorder_root，分别表示当前节点的前驱和整棵树的中序遍历序列的头节点
Node *pre_node = NULL, *inorder_root = NULL; 
// 实现中序线索化遍历
void __build_inorder_thread(Node *root) { 
    if (root == NULL) return ; // 如果当前节点为空，直接返回
    if (root->ltag == 0) __build_inorder_thread(root->lchild); // 如果当前节点的左子树不为线索，则递归遍历左子树
    if (inorder_root == NULL) inorder_root = root; // 如果中序遍历序列的头节点还没有被设置，则将当前节点作为头节点
    if (root->lchild == NULL) { // 如果当前节点没有左子树，则将当前节点的左指针指向前驱节点
        root->lchild = pre_node;
        root->ltag = 1;
    }
    if (pre_node && pre_node->rchild == NULL) { // 如果前驱节点存在且没有右子树，则将前驱节点的右指针指向当前节点
        pre_node->rchild = root;
        pre_node->rtag = 1;
    }
    pre_node = root; // 将当前节点作为下一个节点的前驱
    if (root->rtag == 0) __build_inorder_thread(root->rchild); // 如果当前节点的右子树不为线索，则递归遍历右子树
    return ; // 返回
}

这段代码能实现中序线索化遍历，但是有一点小小的不完美，那就是当树的最右边节点没有右子树时，该节点的后继指针没有被正确地线索化，会指向空地址。

为了解决这个问题，我们可以进行将代码进行封装来解决这段代码的小bug。

void build_inorder_thread(Node *root) { // 定义一个函数，用于在二叉树上进行中序线索化
    __build_inorder_thread(root); // 调用 __build_inorder_thread 函数，对二叉树进行中序线索化
    pre_node->rchild = NULL; // 将最后一个节点的右指针设置为 NULL，即最后一个节点的后继节点为空
    pre_node->rtag = 1; // 将最后一个节点的右线索标记设置为 1，即最后一个节点的右指针为线索
    return ; // 返回
}