一、二叉搜索树
1.1 什么是二叉搜索树
算法导论中对二叉搜索树（Binary Search Tree, 简称BST）的定义：
设x是二叉搜索树中的一个节点，如果y是x左子树中的一个节点，那么y.key<=x.key。如果y是x右子树中的一个节点，那么y.key>=x.key。
以下两棵树就是二叉搜索树：
其中a是一个包含6个节点，高度为2的二叉搜索树。b是一个包含相同关键字、高度为4的低效二叉树。
注意：树中包含了两个相同的节点5，在实际用途中，很少把相同的关键字放到二叉搜索树中。
二叉搜索树主要的操作：
SEARCH：查找某个节点在树中的位置MINIMUM：求以指定节点为根的树中的最小元素MAXIMUM：求以指定节点为根的树中的最大元素PREDECESSOR：求指定节点的前驱节点SUCCESSOR：求指定节点的后继节点INSERT：在树中插入节点DELETE：删除节点
定理：二叉搜索树中的以上各个操作都是在O(h)时间内完成。
1.2 树节点定义
二叉搜索树的节点需要包含以下元素：
- 节点的键值，也就是key
- 父节点和左右子节点的指针
假设key值类型为int，那么树节点的结构应该为：
|
1 2 3 4 5 6 |
struct bst_tree_node_st { int key; struct bst_tree_node_st *lchild; struct bst_tree_node_st *rchild; struct bst_tree_node_st *parent; }; |
二、二叉树操作
2.1 查找操作( SEARCH)
通过二叉搜索树的性质很容易得到查找算法：从树根开始查找，沿着树的路径一直向下。对每个遇到的节点x，比较关键字k和x.key，如果两个关键字相等，查找终止。如果k小于x.key，在x的左子树中继续查找。否则就在x的右子树中继续查找。
伪代码如下（来自《算法导论》)：
|
1 2 3 4 5 6 |
TREE-SEARCH(x, k) if x == NIL or k == x.key return x if k < x.key return TREE-SEARCH(x.left, k) else return TREE-SEARCH(x.right, k) |
上面采用了递归的方法来进行查找，递归最明显的特点就是简单，代码量小。但是在树高度很高时候，递归就会产生巨大的内存消耗和更多的CPU消耗，因为要频繁对函数及参数压栈，并且函数中栈是有大小限制的，不能无限递归。
大部分时候建议使用非递归查找，非递归查找的伪代码实现为：
|
1 2 3 4 5 6 |
ITERATIVE-TREE-SEARCH(x, k) while x ≠ NIL and k ≠ x.key if k < x.key x = x.left else x = x.right return x |
非递归对应的C语言描述：
|
1 2 3 4 5 6 7 8 9 10 |
struct bst_tree_node_st *bst_tree_search(struct bst_tree_st *t, int key) { struct bst_tree_node_st *p = t->root; while (p != NULL && key != p->key) { if (key < p->key) p = p->lchild; else p = p->rchild; } return p; } |
2.2 求最大元素(MAXIMUM)和最小元素(MINIMUM)
根据二叉树的性质可知：最小的节点一定是最左边的节点，最大的节点一定是最右边的节点。
例如对下面这个二叉树而言，最小的元素是2，最大的元素是20。
找最小的元素只要一直在左子节点中查找，直到节点的左节点是NULL为止。相反，找最大的元素，只要在节点的右节点中查找，直到右节点是NULL为止。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
/* * 得到某个子树中的最小元素节点 * @root 待查找的子树根节点 * @return 返回最小元素节点的指针，如果最小元素就是node，那么返回node */ struct bst_tree_node_st *bst_tree_minimum(struct bst_tree_node_st *root) { struct bst_tree_node_st *p = root; while (p != NULL && p->lchild != NULL) p = p->lchild; return p; } /* * 得到某个子树中的最大元素节点 * @root 待查找的子树根节点 * @return 返回最大元素节点的指针，如果最大的元素就是node，那么返回node */ struct bst_tree_node_st *bst_tree_maximum(struct bst_tree_node_st *root) { struct bst_tree_node_st *p = root; while (p != NULL && p->rchild != NULL) p = p->rchild; return p; } |
2.3 求前驱(PREDECESSOR)和后继(SUCCESSOR)
节点x的前驱节点是指中序遍历中顺序在x之前的元素，节点x的后继节点指中序遍历中顺序在x之后的元素。
以2.3节中的二叉树为例，其中序遍历的结果为：2 3 4 6 7 9 13 15 17 18 20。对于元素6而言，它的前驱节点是4，后继节点是7。
求前驱节点的过程：
- 如果节点有左子节点，那么前驱节点一定是左子树中的最大元素。例如
6的前驱是4，15的前驱是13 - 如果节点没有左子节点，那么它的前驱就是以它或者以它任一祖先为右儿子的节点，例如上图中节点
9的前驱是7，节点7的前驱是6
求后继节点的过程：
- 如果节点有右子节点，那么后继节点一定是右子树中最小的元素。例如
15的后继节点是17，18的后继节点是20 - 如果节点没有右子节点，那么它的后继就是以它或者以它任一祖先为左儿子的节点，例如上图中的
13的后继节点是15，17的后继节点是18
可以得到的一个结论：树中最小的元素没有前驱节点，树中最大的元素没有后继节点。
求前驱节点和后继节点的C语言描述：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
/* * 求树中某个节点的后继节点 * @node 当前节点，如果没有后继节点，返回NULL */ struct bst_tree_node_st *bst_tree_successor(struct bst_tree_node_st *node) { struct bst_tree_node_st *x = node, *p; if (x->rchild) return bst_tree_minimum(x->rchild); p = x->parent; while (p != NULL && p->rchild == x) { x = p; p = x->parent; } return p; } /* * 求树中某个节点的前驱节点 * @node 当前节点，如果没有前驱节点，返回NULL */ struct bst_tree_node_st *bst_tree_predecessor(struct bst_tree_node_st *node) { struct bst_tree_node_st *x = node, *p; if (x->lchild) return bst_tree_maximum(x->lchild); p = x->parent; while (p != NULL && p->lchild == x) { x = p; p = p->parent; } return p; } |
2.4 插入节点(INSERT)
插入节点和搜索节点的工作方式一样，先根据元素大小找到合适的位置，然后作为子节点插入，每次插入的节点必定是叶子节点。
例如在下面的树中插入元素13，首先要找到它的父节点15，然后作为它的左子节点插入：
C语言实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
/* * 在树中插入节点 * @t 树 * @node 新节点 */ void bst_tree_insert(struct bst_tree_st *t, struct bst_tree_node_st *node) { struct bst_tree_node_st *x, *y; y = NULL; x = t->root; // 找到合适的插入位置 while (x != NULL) { y = x; if (node->key < x->key) x = x->lchild; else x = x->rchild; } node->parent = y; if (y == NULL) t->root = node; else if (node->key < y->key) y->lchild = node; else y->rchild = node; } |
2.5 删除节点(DELETE)
2.5.1 删除节点的基本操作
相对来说，删除节点要比插入节点复杂许多，它有三种不同的情况：
- 如果待删除节点z没有孩子节点，那么直接把它删除，修改父节点指针即可完成。
- 如果待删除节点z只有一个孩子，那么将这个孩子替换到z的位置，修改z的父节点指针，指向z的子节点。
- 如果待删除节点z有两个孩子，找到z的后继节点y，让y占据z的位置，同时还要让y的右子节点（如果有的话）占据y的位置。
前面两种情况相对简单，甚至可以被合并成一种情况。而第三种情况最为复杂，它还能继续向下分解：
- z的后继节点y就是z的右子节点
- z的后继节点y不是z的右子节点，这种情况下可以推断出y一定不含左子节点，但此时y的右子节点x又有两种情况：
- x为空
- x不为空
下面分别对以上几种情况进行讨论：
2.5.2 删除节点只有一个儿子
只有左子节点的情况
只有右子节点的情况
不管是左儿子，还是右儿子，直接替换原删除节点即可。
2.5.3 删除节点有两个儿子且后继节点是右儿子
对应情况：
只需要把z的位置替换成y就可以了。
2.5.4 删除节点有两个儿子且后继节点不是右儿子
后继节点y不是z的右儿子，那么y必定没有左儿子（如果y有左儿子的话，那么z的后继节点肯定就是y的左儿子而不会是y）。
情况对应下图：
此时要做的两步操作：
- 将
y的右儿子（不管是否为NULL）替换成y - 将
y替换成z
2.5.4 删除节点的代码
添加一个辅助操作TRANSPLANT，英文意思是移植，表示把一个节点用另一个节点代替：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
static void transplant(struct bst_tree_st *t, struct bst_tree_node_st *old_node, struct bst_tree_node_st *new_node) { if (old_node->parent == NULL) t->root = new_node; else if (old_node == old_node->parent->lchild) old_node->parent->lchild = new_node; else old_node->parent->rchild = new_node; // 如果替换新节点不是NULL，设置新节点的父指针指向 if (new_node != NULL) new_node->parent = old_node->parent; |
然后在TREE_DELETE操作中调用TRANSPLANT完成删除操作：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
/* * 删除节点 * @t 树 * @node 待删除的节点 */ void bst_tree_delete(struct bst_tree_st *t, struct bst_tree_node_st *node) { struct bst_tree_node_st *y; if (node->lchild == NULL || node->rchild == NULL) // 至少有一个子节点为空，直接用子节点替换 _transplant(t, node, node->lchild ? node->lchild : node->rchild); else { // 得到右子树中的最小节点，即节点在右子树中的后继节点 y = bst_tree_minimum(node->rchild); if (y->parent != node) { // y不是删除节点的子节点，用y的右节点替换y _transplant(t, y, y->rchild); y->rchild = node->rchild; y->rchild->parent = y; } // 用y替换删除节点 _transplant(t, node, y); y->lchild = node->lchild; y->lchild->parent = y; } } |
![[leetcode]226-翻转二叉树](https://www.dyxmq.cn/wp-content/themes/begin/prune.php?src=https://www.dyxmq.cn/wp-content/uploads/2020/02/cff55-image8d13f59af4ceb4d0.png&w=280&h=210&a=&zc=1)
![[leetcode]145-二叉树的后序遍历](https://www.dyxmq.cn/wp-content/themes/begin/prune.php?src=https://www.dyxmq.cn/wp-content/uploads/2020/02/ce5a3-image6343ae7c83fc33ae.png&w=280&h=210&a=&zc=1)
评论