# 二分搜索树实现

## 1.类封装与节点定义

★节点定义 ”

```class BST {
/**
* 封装到私有,让外界不知道具体实现
*/
private:
struct Node {
Key key;
Value value;
Node *left;
Node *right;

Node(Key key, Value value) {
this->key = key;
this->value = value;
this->left = this->right = NULL;
}

Node(Node *node) {
this->key = node->key;
this->value = node->value;
this->left = node->left;
this->right = node->right;
}
};

Node *root;
int count;
}
```

★构造与析构 ”

```public:
BST() {
root = NULL;
count = 0;
}
```

```public:
~BST() {
destroy(root);
}
```

```private:
void destroy(Node *node) {
// 节点不为空
if (node) {
// 先释放左右孩子，再释放自身，所以下面先对左右孩子递归处理。
destroy(node->left);
destroy(node->right);
// 最后释放自己
delete node;
count--;
}
}
```

## 2.BST内部具体函数实现

### 2.1 获取节点个数与是否是空的BST树

```public:
int size() {
return count;
}
bool isEmpty() {
return count == 0;
}
```

### 2.2 插入节点

```public:
void insert(Key key, Value value) {
root = insert(root, key, value);
}
```

#### 2.2.1 递归插入

★思路 ”

• 插入节点key与当前递归处的key相等，更新value
• 插入节点key大于当前递归处的key，递归右子树
• 插入节点key小于当前递归处的key，递归左子树
```private:
Node *insert(Node *node, Key key, Value value) {
if (node == NULL) {
count++;
return new Node(key, value);
}

if (key == node->key)
node->value = value;
else if (key < node->key)
node->left = insert(node->left, key, value);
else
node->right = insert(node->right, key, value);
return node;
}
```

#### 2.2.2 非递归插入

★思路 ”

```private:
Node *Non_Recursion_InsertNode(Node *node, Key key, Value value) {
if (node == NULL) {
node = new Node(key, value);
count++;
return node;
}
Node *pre = node;
Node *cur = node;

while (cur) {
pre = cur;
if (key == pre->key) {
pre->value = value;
return node;
} else if (key < pre->key)
cur = cur->left;
else
cur = cur->right;
}
if (key < pre->key)
pre->left = new Node(key, value);
else
pre->right = new Node(key, value);
count++;
return node;
}

```

### 2.3 查找key是否存在

```public:
bool contain(Key key) {
return contain(root, key);
}
```

#### 2.3.1 递归查找

```private:
bool contain(Node *node, Key key) {
if (node == NULL) return false;
if (key == node->key) return true;
else if (key < node->key)
return contain(node->left, key);
else
return contain(node->right, key);
}
```

#### 2.3.4 非递归查找

```private:
bool Non_Recursion_Contain(Node *node, Key key) {
if(node==NULL) return false;

Mode* cur=node;
while (cur) {
if (key == node->key) {
return true;
} else if (key < node->key)
cur = cur->left;
else
cur = cur->right;
}
return false;
}
```

### 2.4 查询key对应的value或节点

```public:
Value *search(Key key) {
return search(root, key);
}
private:
Value *search(Node *node, Key key) {
if (node == NULL) return NULL;

if (key == node->key) return &node->value;
else if (key < node->key)
return search(node->left, key);
else
return search(node->right, key);
}

Node* Search(Node *node, Key key) {
if (node == NULL) return NULL;

if (key == node->key) return node;
else if (key < node->key)
return Search(node->left, key);
else
return Search(node->right, key);
}
```

### 2.5 删除节点

```public:
void remove(Key key) {
root = remove(root, key);
}
```

• 删除节点无左孩子,直接用右孩子代替当前节点，释放内存，节点减1,。
• 删除节点无右孩子，直接用左孩子代替。。。
• 删除节点有左孩子与右孩子，采用右孩子最小节点或左孩子最大节点代替。
```private:
Node *remove(Node *node, Key key) {
if (node == NULL) return NULL;
// 左孩子查找
if (key < node->key) {
node->left = remove(node->left, key);
return node;
// 右孩子查找
} else if (key > node->key) {
node->right = remove(node->right, key);
return node;
// 查找到了key
} else { // key == node->key
// 左孩子为空,就直接以右孩子取缔
if (node->left == NULL) {         // 左孩子为空包含两部分(左孩子为空与左右孩子均为空)
Node *rightNode = node->right;
delete node;
count--;
return rightNode;
}
// 右孩子为空,就直接以左孩子取缔
if (node->right == NULL) {
Node *leftNode = node->left;
delete node;
count--;
return leftNode;
}
// 左右孩子均不为空,取右孩子子树中最小或取左孩子子树中最大
// node->left!=NULL && node->right!=NULL
// 右孩子子树中最小方法
Node *successor = new Node( minimum(node->right));       // 在removeMin中将最小节点删除了,后面再次访问successor会为NULL,所以此时需要重新new 分配内存
count++;
successor->right = removeMin(node->right);
successor->left = node->left;
delete node;
count--;

// 左孩子子树中最大方法
/**
Node *successor = new Node(maximum(node->left));
count++;
successor->left= removeMin(node->left);
successor->right= node->right;
delete node;
count--;
*/
return successor;
}
}
```

★删除最小节点 ”

• 保存当前节点的右孩子。
• 删除当前节点
• 返回右孩子。
```private:
Node *removeMin(Node *node) {
if (node->left == NULL) {
Node *rightNode = node->right;
delete node;
count--;
return rightNode;
}
node->left = removeMin(node->left);
return node;
}
```

```private:
// 非递归 返回curNode->right节点
Node *removeMin1(Node *node) {
Node *root = node;
Node *currentNode = node, *p = node;
Node *parentNode = node;
// 空
if (currentNode == NULL)
return NULL;
// 迭代
while (currentNode->left != NULL) {
parentNode = currentNode;
currentNode = currentNode->left;
}
// 传递进来的左孩子本身就为空
if (currentNode == parentNode) {
Node *tmp = currentNode->right;
delete currentNode; // 此时的currentNode为最大节点
count--;
return tmp;
}
// 传递进来的左孩子本身不为空,而是通过迭代到最小节点
parentNode->left = currentNode->right;
// 删除掉currentNode
delete currentNode; // 此时的currentNode为最小节点
count--;
return p;
}
```

★删除最大节点： ”

```private:
Node *removeMax(Node *node) {
if (node->right == NULL) {
Node *leftNode = node->left;
delete node;
count--;
return leftNode;
}
node->right= removeMax(node->right);
return node;
}
```

```private:
// 非递归
Node *removeMax1(Node *node) {
Node *currentNode = node, *p = node;
Node *parentNode = node;
if (currentNode == NULL)
return currentNode;

while (currentNode->right != NULL) {
parentNode = currentNode;
currentNode = currentNode->right;
}
if (currentNode == parentNode) {
Node *tmp = currentNode->left;
delete currentNode; // 此时的currentNode为最大节点
count--;
return tmp;
}
parentNode->right = currentNode->left;
delete currentNode; // 此时的currentNode为最大节点
count--;
return p;
}
```

```public:
void removeMin() {
if (root)
root = removeMin(root);
}

void removeMax() {
if (root)
root = removeMax(root);
}
```

```public:
// 向左找,为最小
// 向右找,为最大
Key minimum() {
assert(count != 0);
Node *minNode = minimum(root);
return minNode->key;
}

Key maximum() {
assert(count != 0);
Node *maxNode = maximum(root);
return maxNode->key;
}
```

```private:
Node *minimum(Node *node) {
if (node->left == NULL) return node;
return minimum(node->left);
}

// 非递归
Node *minimum1(Node *node) {
Node *currentNode = node;
if (currentNode == NULL)
return NULL;

while (currentNode->left != NULL) {
currentNode = currentNode->left;
}
return currentNode;
}

Node *maximum(Node *node) {
if (node->right == NULL) return node;
return maximum(node->right);
}

// 非递归
Node *maximum1(Node *node) {
Node *currentNode = node;
if (currentNode == NULL)
return NULL;

while (currentNode->right != NULL) {
currentNode = currentNode->right;
}
return currentNode;
}
```

```private:
// 以左侧最大取代非递归删除
Node *deleteNode(Node *root, Key key) {
if (root == NULL) return NULL;
Node *currentNode = root;
Node *parentNode = root;

//定位到要删除的key 的父节点,以及当前元素
while (currentNode != NULL && currentNode->val != key) {
parentNode = currentNode;
if (currentNode->key > key) {
currentNode = currentNode->left;
} else {
currentNode = currentNode->right;
}

}
// 表示没找到key,直接返回结果
if (currentNode == NULL) return root;
// 表示与key相等的是根节点,根节点直接处理,不需要保存父节点
if (parentNode == currentNode) {
// 左分支为空,以右分支取缔
if (currentNode->left == NULL) {
Node *tmp = currentNode->right;
delete currentNode;
count--;
return tmp;
}
// 右分支为空,以左分支取缔
if (currentNode->right == NULL) {
Node *tmp = currentNode->left;
delete currentNode;
count--;
return tmp;
}
// 取左分支最大节点取代当前节点,并删除当前节点
Node *delnode = new Node(maximum1(currentNode->left)->val);
delnode->left = removeMax1(currentNode->left);
delnode->right = currentNode->right;
delete currentNode;
count--;
return delnode;
}
// key不是根节点,需要判断父节点与当前节点的关系,有可能是右分支,也可能是左分支

// 左分支关系
if (parentNode->left == currentNode) {
if (currentNode->left == NULL) {
parentNode->left = currentNode->right;
delete currentNode;
count--;
return root;
}
if (currentNode->right == NULL) {
parentNode->left = currentNode->left;
delete currentNode;
count--;
return root;
}
Node *delnode = new Node(maximum1(currentNode->left)->val);
count++;
delnode->left = deleteMax(currentNode->left);
delnode->right = currentNode->right;
// 父节点左孩子更新为左边最大的节点
parentNode->left = delnode;
delete currentNode;
count--;
return root;
}
// 右分支关系
if (parentNode->right == currentNode) {
if (currentNode->left == NULL) {
parentNode->right = currentNode->right;
delete currentNode;
count--;
return root;
}
if (currentNode->right == NULL) {
parentNode->right = currentNode->left;
delete currentNode;
count--;
return root;
}
Node *delnode = new Node(maximum1(currentNode->left)->val);
count++;
delnode->left = removeMax1(currentNode->left);
delnode->right = currentNode->right;
// 父节点右孩子更新为左边最大的节点
parentNode->right = delnode;
delete currentNode;
count--;
return root;
}
return root;
}
```

### 2.6 BST遍历

#### 2.6.1 前中后遍历

```public:
vector<pair<Key, Value>> preOrder() {
vector<pair<Key, Value>> res;
preOrder(root, res);
return res;
}
private:
void preOrder(Node *node, vector<pair<Key, Value>> &res) {
if (node) {
res.push_back(make_pair(node->key, node->value));
preOrder(node->left, res);
preOrder(node->right, res);
}
}

```

```private:
enum Tag {
visit, print
};

struct Command {
Tag tag;
Node *node;

Command(Tag t, Node *n) : tag(t), node(n) {}
};

public:
vector<pair<Key, Value>> _preOrder() {
vector<pair<Key, Value>> res;
if (root == NULL) return res;
stack<Command> stack;
stack.push(Command(visit, root));
while (!stack.empty()) {
Command command = stack.top();
stack.pop();
if (command.tag == print)
res.push_back(make_pair(command.node->key, command.node->value));
else {
if (command.node->right)
stack.push(Command(visit, command.node->right));
if (command.node->left)
stack.push(Command(visit, command.node->left));
stack.push(Command(print, command.node));
}
}
return res;
}
```

#### 2.6.1 层次遍历

```public:
vector<pair<Key, Value>> levelOrder() {
vector<pair<Key, Value>> res;
queue<Node *> q;
q.push(root);
while (!q.empty()) {
Node *node = q.front();
q.pop();
res.push_back(make_pair(node->key, node->value));
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
return res;
}
```

### 2.7 前驱与后继

#### 2.7.1 获取对应key的前驱

```public:
Node *predecessor(Key key) {
return predecessor(root, key);
}
```

• 左孩子不为空，前驱就是左孩子的最大节点
• 左孩子为空，自底向上递归查找距离当前节点最近的左拐节点
```private:
Node *predecessor(Node *root, Key key) {

Node *node = Search(root, key);
// 如果key所在的节点不存在, 则key没有前驱, 返回NULL
if (node == NULL)
return NULL;

// 如果key所在的节点左子树不为空,则其左子树的最大值为key的前驱
if (node->left != NULL)
return maximum(node->left);

// 否则, key的前驱在从根节点到key的路径上, 在这个路径上寻找到比key小的最大值, 即为key的前驱
Node *preNode = predecessorFromAncestor(root, key);
return preNode == NULL ? NULL : preNode;
}
```

```1
\
2
\
3
```

```private:
Node *predecessorFromAncestor(Node *node, Key key) {
if (node->key == key)
return NULL;
if (key < node->key) {     // 我们目标是找比key小的最大key,如果比node的key小就应该在它的左子树中查找
return predecessorFromAncestor(node->left, key);
} else {      // 此时的key小于node的key在右子树中查找
assert(key > node->key);
/**
* 如果当前节点小于key,则当前节点有可能是比key小的最大值
* 向右继续搜索,将结果存储到tmpNode中
*/
Node *tmpNode = predecessorFromAncestor(node->right, key);
if (tmpNode)
return tmpNode;
else
// 如果tmpNode为空,则当前节点即为结果
return node;
}
}
```

```private:
Node *_predecessorFromAncestor(Node *node, Key key) {
Node *firstRParent = NULL;
while (node) {
if (node->key == key) {
return firstRParent;
}
if (node->key > key) {
node = node->left;
} else if (node->key < key) {
firstRParent = node;        //出现右拐点
node = node->right;
}
}
return firstRParent;
}

```

#### 2.7.2 获取对应key的后继

```public:
Node *successor(Key key) {
return successor(root, key);
}
```

• 当前节点右孩子不为空，查找右孩子最小节点
• 当前节点右孩子为空，网上查找第一个左拐节点。
```private:
// 查找key的后继, 递归算法
// 如果不存在key的后继(key不存在, 或者key是整棵二叉树中的最大值), 则返回NULL
Node *successor(Node *root, Key key) {

Node *node = Search(root, key);
// 如果key所在的节点不存在, 则key没有前驱, 返回NULL
if (node == NULL)
return NULL;

// 如果key所在的节点右子树不为空,则其右子树的最小值为key的后继
if (node->right != NULL)
return minimum(node->right);

// 否则, key的后继在从根节点到key的路径上, 在这个路径上寻找到比key大的最小值, 即为key的后继
Node *sucNode = successorFromAncestor(root, key);
return sucNode == NULL ? NULL : sucNode;
}
```

```private:
/**
* 在node为根的二叉搜索树中,寻找key的祖先中,比key大的最小值所在节点.递归算法
* 算法调用前已保证key存在在以node为根的二叉树中
* @param node
* @param key
* @return
*/
Node *successorFromAncestor(Node *node, Key key) {
if (node->key == key)
return NULL;
if (key > node->key) {     // 我们目标是找比key大的最小key,如果比node的key大就应该在它的右子树中查找
return successorFromAncestor(node->right, key);
} else {      // 此时的key小于node的key在左子书中查找
assert(key < node->key);
/**
* 如果当前节点大于key,则当前节点有可能是比key大的最小值
* 向左继续搜索,将结果存储到tmpNode中
*/
Node *tmpNode = successorFromAncestor(node->left, key);
if (tmpNode)
return tmpNode;
else
// 如果tmpNode为空,则当前节点即为结果
return node;
}
}
```

```private:
Node *_successorFromAncestor(Node *node, Key key) {
Node *firstLParent = NULL;
while (node) {
if (node->key == key) {
return firstLParent;
}
if (node->key < key) {
node = node->right;
} else if (node->key > key) {
firstLParent = node;        //出现右拐点
node = node->left;
}
}
return firstLParent;
}
```

### 2.8 floor与ceil实现

#### 2.8.1 floor实现

```    Node *floor(Key key) {
// 空树或给定的key超过树中最大的key
if (count == 0 || key < minimum()) return NULL;
return floor(root, key);
}
```

• 如果node的key值和要寻找的key值相等，则node 本身就是key的floor节点。
• 如果node的key比要寻找的key大，则要寻找的key的floor节点一定在node的左边子树中。
• 如果node的key小于要寻找的key，则node有可能是key的floor节点,也有可能不是(存在比node->key大但小于key的其余节点)，则要尝试向node的右子树寻找一下。
```private:
Node *floor(Node *root, Key key) {
if (root == NULL) return NULL;

// 如果node的key值和要寻找的key值相等
// 则node 本身就是key的floor节点
if (key == root->key) return root;
// 如果node的key比要寻找的key大
// 则要寻找的key的floor节点一定在node的左边子树中
if (root->key > key) return floor(root->left, key);
// 如果node的key小于要寻找的key
// 则node有可能是key的floor节点,也有可能不是(存在比node->key大但小于key的其余节点)
// 则要尝试向node的右子树寻找一下
Node *tmpNode = floor(root->right, key);
if (tmpNode) return tmpNode;
return root;
}
```

#### 2.8.2 ceil实现

```private:
Node *ceil(Key key) {
// 空树或给定的key超过树中最大的key
if (count == 0 || key > maximum()) return NULL;
return ceil(root, key);
}
```
• 如果node的key值和要寻找的key值相等则node 本身就是key的ceil节点.
• 如果node的key比要寻找的key小,则要寻找的key的ceil节点一定在node的右边子树中。
• 如果node的key大于要寻找的key，则node有可能是key的ceil节点,也有可能不是(存在比node->key小但大于key的其余节点)，则要尝试向node的左子树寻找一下。
```private:
Node *ceil(Node *root, Key key) {
if (root == NULL) return NULL;

// 如果node的key值和要寻找的key值相等
// 则node 本身就是key的ceil节点
if (key == root->key) return root;
// 如果node的key比要寻找的key小
if (root->key < key) return ceil(root->right, key);
// 如果node的key大于要寻找的key
// 则node有可能是key的ceil节点,也有可能不是(存在比node->key小但大于key的其余节点)
// 则要尝试向node的左子树寻找一下
Node *tmpNode = ceil(root->left, key);
if (tmpNode) return tmpNode;
return root;
}
```

0 条评论

• ### STL之set与multiset那些事

set/multiset以rb_tree为底层结构，因此有元素自动排序特性。排序的依据是key，而set/multiset元素的value和key合二为一：va...

• ### 再也不用担心STL的红黑树了。。。

STL中Red-black tree（红黑树）class,用来当做SLT关系式容器（如set,multiset,map, multimap）.里面所用的inse...

• ### 知识图谱系列之Neo4J

上次写了一篇文章提到了一个有关知识图谱的概念，在本公众号中，并未写有关这方面的文章，那么这一节从python与neo4j方向来共同学习知识图谱的一些实战操作，后...

• ### 数据结构之映射Map

1、映射Map，存储键值数据对的数据结构（key，value），可以根据键key快速寻找到值Value，可以使用链表或者二分搜索树实现的。

• ### WebDriver多线程并发

要想多线程并发的运行WebDriver，必须同时满足2个条件，首先你的测试程序是多线程，其次需要用到Selenium Server。下载位置如下图：

• ### 教学大师奖、杰出教学奖和创新创业英才奖在杭州颁发

10月15日，中国首届“教学大师奖、杰出教学奖和创新创业英才奖”在杭州颁发。清华大学姚期智院士获得教学大师奖，北京大学黄如、复旦大学闻玉梅、南京大学卢德馨、浙...

• ### 排序数组转换为二叉查找树

已知一个排序的数组，将该数组转换为一个高度平衡的二叉查找树。 平衡的定义： 二叉查找树中，任意节点的两颗子树高度差不超过1. LeetCode 108

• ### 虚拟CPE和SD-WAN功能逐步走向融合

对服务提供商而言，虚拟客户端设备（vCPE）以及软件定义广域网（SD-WAN）是能够实现业务目标的不同选择，最终目的都是要向用户提供托管服务。因此，服务提供商面...

• ### 补充下3月面试题（好未来、腾讯音乐、小药药）

补充一下落下的3月份的面试题，关于春季面经可以看我的上文 。从出师不利、面面具挂，到拿到阿里2个offer