二叉树（C语言版）

二叉树

树是一种层次结构，它在现实生活中是广泛存在的，比如：族谱(family tree)，组织机构，目录结构等。

不过今天我们只讲二叉树。

二叉树有多重要？单就面试而言，在 leetcode 中二叉树相关的题目占据了 300 多道，近三分之一。同时，二叉树在整个算法板块中还起到承上启下的作用：不但是数组和链表的延伸，又可以作为图的基础。总之，非常重要！

那什么是二叉树？

定义：二叉树是一棵树，并且二叉树的每个结点最多有两棵子树。二叉树的子树又分为左子树和右子树。

完全二叉树和满二叉树

二叉树有两种特殊的形态：完全二叉树和满二叉树。

完全二叉树：若二叉树的深度为 h，除第 h 层外，其它各层(1～h-1)的结点数目都达到最大值，第 h 层的结点都连续排列在最左边，这样的二叉树就是完全二叉树。

满二叉树：每一层的结点数目都达到最大值(包括最下面一层)。

二叉搜索树

Binary Search Tree (BST) 又叫二叉排序树。要求树中的结点可以按照某个规则进行比较，其定义如下：

1. .左子树中所有结点的 key 值都比根结点的 key 值小，并且左子树也是二叉搜索树。

2. 右子树中所有结点的 key 值都比根结点的 key 值大，并且右子树也是二叉搜索树。

基本操作

search：若 BST 为空，则直接NULL。若 BST 非空，则和根结点比较，若和根结点相等，表明找到了。若比根结点小，则在左子树中递归查找；若比根结点大，则在右子树中递归查找。

insert：若 BST 为空，则创建结点，将其作为根结点。若 BST 非空，则和根结点比较，若和根结点相等，则返回。若比根结点小，则在左子树中递归插入；若比根结点大，则在右子树中递归插入。

delete：分三种情况处理。

1. 如果要删除结点没有孩子，那么直接将该结点删除就行了。

   

2. 如果要删除结点只有一个孩子，那么需要将父亲结点对应的指针，指向它唯一 的孩子结点。

   

3. 如果要删除结点有两个孩子，那么我们可以找到这个结点的右子树中最小结点 (或者左子树中最大结点)，把它替换到要删除的结点上，然后再删除右子树的最小结点 (或左子树的最大结点)。

   

实现

代码

// BST.h
typedef char K;typedef struct tree_node {K key;struct tree_node* left;struct tree_node* right;
} TreeNode;typedef struct {TreeNode* root;
} BST;// API
BST* bst_create();
void bst_destroy(BST* tree);void bst_insert(BST* tree, K key);
TreeNode* bst_search(BST* tree, K key);
void bst_delete(BST* tree, K key);void bst_preorder(BST* tree); // 前序
void bst_inorder(BST* tree); // 中序
void bst_postorder(BST* tree); // 后序
void bst_levelorder(BST* tree); // 层序遍历

// BST.c
#include "BST.h"
#include <stdlib.h>
#include <stdio.h>BST* bst_create() {BST* bst = (BST*)malloc(sizeof(BST));bst->root = NULL;return bst;
}void freeTraversal(TreeNode* node) {// 终止条件if (node == NULL) {return;}freeTraversal(node->left); // 前freeTraversal(node->right); // 后printf("已释放结点 %d\n", node->key);free(node); // 中
}void bst_destroy(BST* tree) {TreeNode* root = tree->root;// 1.释放所有结点freeTraversal(root);// 2.释放BSTfree(tree);printf("已释放BST\n");
}void bst_insert(BST* tree, K key) {if (tree->root == NULL) { // 空树，直接作为根结点插入TreeNode* newNode = (TreeNode*)calloc(1, sizeof(TreeNode));newNode->key = key;tree->root = newNode;return;}// 迭代法TreeNode* cur = tree->root;while (cur) {if (key > cur->key) {// 大于if (cur->right == NULL) {TreeNode* newNode = (TreeNode*)calloc(1, sizeof(TreeNode));newNode->key = key;cur->right = newNode;return;} else {cur = cur->right;}}else if (key < cur->key) {// 小于if (cur->left == NULL) {TreeNode* newNode = (TreeNode*)calloc(1, sizeof(TreeNode));newNode->key = key;cur->left = newNode;return;} else {cur = cur->left;}}else return;} // cur == NULL
}TreeNode* bst_search(BST* tree, K key) {TreeNode* cur = tree->root;while (cur) {if (key > cur->key)cur = cur->right;else if (key < cur->key)cur = cur->left;else {printf("找到结点，结点值 %d\n", cur->key);return cur;}}printf("没找到结点\n");return NULL;
}TreeNode* deleteOneNode(TreeNode* targetNode) {if (targetNode == NULL) return NULL;if (targetNode->right == NULL) { // 右空 左空或不空TreeNode* tmpNode = targetNode->left;free(targetNode);return tmpNode;}// 右不空，左不空或空TreeNode* cur = targetNode->right;while (cur->left) {cur = cur->left;} // 右子树的最左结点 cur->left == NULLcur->left = targetNode->left;TreeNode* tmpNode = targetNode->right;free(targetNode);return tmpNode;
}void bst_delete(BST* tree, K key) {TreeNode* cur = tree->root;TreeNode* prev = NULL;while (cur) {if (cur->key == key) {if (prev == NULL) {// 要删除根节点tree->root = deleteOneNode(cur);}else if (prev->left && prev->left->key == key) {prev->left = deleteOneNode(cur);}else if (prev->right && prev->right->key == key) {prev->right = deleteOneNode(cur);}break;}prev = cur;if (key > cur->key) cur = cur->right;if (key < cur->key) cur = cur->left;}}/* **************************************** */
/*               深度优先遍历                 */
/* **************************************** */// 前序遍历（递归法）
void preorder_traversal(TreeNode* node) {// 终止条件if (node == NULL) {return;}printf(" %d", node->key); // 中preorder_traversal(node->left); // 左preorder_traversal(node->right); // 后
}void bst_preorder(BST* tree) {TreeNode* rootNode = tree->root;preorder_traversal(rootNode);
}// 中序遍历（递归法）
void inorder_traversal(TreeNode* node) {// 终止条件if (node == NULL) {return;}inorder_traversal(node->left); // 前printf(" %d", node->key); // 中inorder_traversal(node->right); // 后
}void bst_inorder(BST* tree) {TreeNode* rootNode = tree->root;inorder_traversal(tree->root);
}// 后序遍历（递归法）
void postorder_traversal(TreeNode* node) {// 终止条件if (node == NULL) {return;}postorder_traversal(node->left); // 前postorder_traversal(node->right); // 后printf(" %d", node->key); // 中
}void bst_postorder(BST* tree) {TreeNode* rootNode = tree->root;postorder_traversal(tree->root);
}/* **************************************** */
/*               广度优先遍历                 */
/* **************************************** */// 实现队列（基于链表）
typedef TreeNode* V;typedef struct que_node{V node;struct que_node* next;
} queNode;typedef struct {queNode* front;queNode* rear;int size;
} Queue;Queue* create_queue() {Queue* que = (Queue*)malloc(sizeof(Queue));que->front = NULL; // 队头que->rear = NULL; // 队尾que->size = 0;return que;
}void push_queue(Queue* q, V val) {queNode* newNode = (queNode*)malloc(sizeof(queNode));newNode->node = val;newNode->next = NULL;if (q->front == NULL) { // 空队列q->front = newNode;q->rear = newNode;q->size++;return;}q->rear->next = newNode;q->rear = newNode;q->size++;
}V pop_queue(Queue* q) {if (q->front == NULL) {return NULL;}queNode* tmpNode = q->front;if (q->size == 1)q->rear = NULL;q->front = tmpNode->next;q->size--;return tmpNode->node;
}V peek_queue(Queue* q) {if (q->front == NULL) {return NULL;}return q->front->node;
}bool is_empty(Queue* q) {return (q->front == NULL);
}/* 层序遍历（迭代法） */
// 层序遍历二叉树
void bst_levelorder(BST* tree) {Queue* que = create_queue();TreeNode* cur = tree->root;if (cur == NULL)return;push_queue(que, cur);while (!(is_empty(que))) {int num = que->size;while (num--) {cur = que->front->node;printf(" %d", que->front->node->key);pop_queue(que);if (cur->left) {push_queue(que, cur->left);}if (cur->right) {push_queue(que, cur->right);}}} 
}

// main.c
#include "BST.h"
#include <stdio.h>int main(void) {BST* bst = bst_create();bst_insert(bst, 1);bst_insert(bst, 2);bst_insert(bst, 5);bst_insert(bst, 7);bst_insert(bst, 5);bst_insert(bst, 9);bst_insert(bst, 4);// bst_search(bst, 5);// bst_search(bst, 100);printf("前序遍历结果：");bst_preorder(bst);printf("\n");printf("中序遍历结果：");bst_inorder(bst);printf("\n");printf("后序遍历结果：");bst_postorder(bst);printf("\n");printf("层序遍历结果：");bst_levelorder(bst);printf("\n");printf("已删除结点2\n");bst_delete(bst, 2);printf("已删除结点5\n");bst_delete(bst, 5);printf("前序遍历结果：");bst_preorder(bst);printf("\n");printf("中序遍历结果：");bst_inorder(bst);printf("\n");printf("后序遍历结果：");bst_postorder(bst);printf("\n");printf("层序遍历结果：");bst_levelorder(bst);printf("\n");bst_destroy(bst);
}

运行结果

分析

BST 增加、删除和查找的效率取决于它的高度 h。

insert：O(h)

search：O(h)

delete：O(h)

有 n 个结点的二叉树，高度最低时 h = log2n (完全二叉树)，高度最高时 h = n (退化成单链表)。但是我们上面实现的 BST 并不能保证树的高度为 O(logn)，更糟糕的是，随着动态的插入和删除元素，整棵树会慢慢地向一边倾斜。

要想保证二叉树增加，查找，删除的时间复杂度为 O(logn)，我们需要在添加结点和删除结点后，做一些调整操作，以保证二叉树的平衡。

常见的平衡二叉树有：AVL树、红黑树、伸展树、树堆等。其中应用最广，名气最大的当属红黑树了。

红黑树

2-3-4树(理论模型)

2-3-4 树有以下两个性质：

• 2-3-4 树，在普通的二叉查找树上进行了扩展，它允许一个结点包含多个 key 值。

  2-结点：一个 key 值，两个孩子。

  3-结点：两个 key 值，三个孩子。

  4-结点：三个 key 值，四个孩子

• 2-3-4树可以动态地保持完美平衡。

  所谓完美平衡，就是从根结点到任意一个叶子结点的路径都是一样长的。

查找

2-3-4 树的查找和普通 BST 的查找方式几乎一致。

插入

2-3-4 树的插入和普通 BST 相比，稍微复杂一点。

• 如果是在2-结点中插入，直接将2-结点转换为3-结点。

  

• 如果是在3-结点中插入，直接将3-结点转换为4-结点。

• 但是，如果是在4-结点中插入，该怎么办呢?

  

这就需要将4-结点进行分裂了。

​

但是，如果父结点也是4-结点，又该怎么办呢?

有两种解决方案：（不变式：当前结点肯定不是4-结点。）

a. 自底向上(Bayer, 1972) 用同样的方法分裂父结点

如果需要，我们会沿着查找路径自底向上依次分裂4-结点

b. 自顶向下(Guibas-Sedgewick, 1978)

在查找插入位置的时候，遇到4-结点就分裂

找到插入位置的时候，就可以直接插入了(当前结点肯定不是4-结点)

2-3-4树生长的例子

性能分析

2-3-4树增加，删除，查找操作的时间复杂度取决于它的高度 h.

• 最坏情况：h = log2N [所有结点都是2-结点]
• 最好情况：h = log4N = (1/2)log2N [所有结点都是4-结点]

2-3-4树的性能是非常优秀的，举个例子

• N = 100万时，2-3-4树的高度在 10 到 20 之间。
• N = 10亿时，2-3-4树的高度在 15 到 30 之间。

实现

那我们如何实现 2-3-4 树呢？如果为2-结点，3-结点，4-结点分别编写不同的结点类型，则处理起来会非常麻烦，我们不得不处理各个结点类型之间得转换。那 2-3-4 树有没有一种更好得实现方式呢？

有的，答案就是红黑树！

红黑树(实际实现)

我们可以用普通的 BST 来表示 2-3-4 树。可是，我们该如何表示3-结点和4-结点呢？

红黑树给出了一个很好的解决方案，我们可以用"红色"的边来表示3-结点和4-结点。如下图所示：

3-结点有两种表示形式，而4-结点只有一种表示形式。

可是"边"是不存在的呀，它只是逻辑上的一个结构，我们又该如何表示边的颜色呢？

孩子结点到父亲结点的边是唯一的，所以我们可以用孩子结点的颜色，来表示孩子结点到父亲结点的边的颜色。

typedef struct treenode_s {int val;struct treenode_s* left;struct treenode_s* right;bool color;
}

这就是红黑树！

我们来看一看经典教科书(算法导论)对红黑树的定义：

一棵红黑树是满足下面红黑性质的二叉搜索树：
1. 每个结点或者是红色的，或者是黑色的
2. 根结点是黑色的
3. 叶子结点 (Nil) 是黑色的 (注：在算法导论中，叶子结点指得是 NULL 结点)
4. 如果一个结点是红色的，则它的两个子结点都是黑色的 （4-node 只有一种编码方式）
5. 对每个结点，从该结点到其所有后代叶子结点的路径上，包含相同数目的黑色结点。(黑高平衡， 2-3-4树是一个完美平衡的树)

2-3-4 树和红黑树之间是有一张对应关系的，不过这种对应关系不是 1-1 的 (3-结点可以倾向任意一边)。