二叉搜索树定义
- 二叉搜索树首先其是一个二叉树；并且每个结点的键值都大于左孩子，且小于右孩子。以左右孩子为根结点的子树仍为二叉搜索树。 注意：二叉搜索树不一定是完全二叉树。堆肯定是一棵完全二叉树，所以可以用数组表示。
- 所以对于二叉搜索树。根结点大于左子树所有结点的值，小于右子树所有结点的值。
二叉搜索树示例.png
二叉搜索树优势
- 二分搜索树常用来实现字典、集合等数据结构，比如STL中的Map，Set类的实现。二分搜索树在查找、删除、插入一个元素的时间复杂度都为O(logn)；使用二叉搜索树能够很容易找到：最大值max、最小值min、排序位置rank等操作。
二分搜索树时间复杂度.png
二叉搜索树劣势
- 如果建立二叉搜索树，输入的是一个排序好的数组。此时二叉搜索树退化成为了链表。所以二叉搜索树应该建成一个平衡二叉树。比如常见的红黑树。
二叉搜索树相关操作
- 插入元素、删除元素（最难）；
- 查找元素、是否包含元素；
- 先序、中序、后续遍历二叉搜索树；注意，对于二叉搜索树中序遍历结果是一个递增的序列；
- max, min, floor, ceil, rank, select等；
#ifndef WORKSPACE_BINARY_SEARCH_TREE_H
#define WORKSPACE_BINARY_SEARCH_TREE_H
#include <iostream>
#include <queue>
#include <cassert>
using namespace std;
/*
* 二叉搜索树实现；
* */
template<typename Key, typename Value>
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;
private:
//以node为根的二叉搜索树中，插入结点（key, value）
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;
}
//以node为根的二叉搜索树中是否包含键值为key的结点；
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);
}
//以node为根的二叉搜索树中，查找key所对应的value
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);
}
//前序遍历
void preOrder(Node* node){
if(node != NULL){
cout << node->key << endl;
preOrder(node->left);
preOrder(node->right);
}
}
//中序遍历
void inOrder(Node* node){
if(node != NULL){
inOrder(node->left);
cout << node->key << endl;
inOrder(node->right);
}
}
//后序遍历
void postOrder(Node* node){
if(node != NULL){
postOrder(node->left);
postOrder(node->right);
cout << node->key << endl;
}
}
void destory(Node *node){
if(node != NULL){
destory(node->left);
destory(node->right);
delete node;
count--;
}
}
Node* minimum(Node* node){
if(node->left == NULL)
return node;
return minimum(node->left);
}
Node* maximum(Node* node){
if(node->right == NULL)
return node;
return maximum(node->right);
}
Node* removeMin(Node* node){
if(node->left == NULL){
Node* rightNode = node->right;
delete node;
count--;
return rightNode;
}
node->left = removeMin(node->left);
return node;
}
Node* removeMax(Node* node){
if(node->right == NULL){
Node* leftNode = node->left;
delete node;
count--;
return leftNode;
}
node->right = removeMax(node->left);
return node;
}
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;
}else{
//key == node->key
if(node->left == NULL){ //（1）左孩子为空；
Node *rightNode = node->right;
delete node;
count--;
return rightNode;
}
if(node->right == NULL){ //（2）右孩子为空；
Node *leftNode = node->left;
delete node;
count--;
return leftNode;
}
//（3）左、右孩子都不为空的情况；
Node *successor = new Node(minimum(node->right));
count++;
successor->right = removeMin(node->right);
successor->left = node->left;
delete node;
count--;
return successor;
}
}
public:
BST(){
this->root = NULL;
count = 0;
}
~BST(){
// TODO: 析构函数
destory(root);
}
//返回树的大小；
int size(){
return count;
}
//判断树是否为空；
bool isEmpty(){
return count == 0;
}
//插入一个新的结点；
void insert(Key key, Value value){
root = insert(root, key, value);
}
//是否包含key
bool contain(Key key){
return contain(root, key);
}
//查找元素
Value* search(Key key){
return search(root, key);
}
//前序遍历
void preOrder(){
preOrder(root);
}
//中序遍历
void inOrder(){
inOrder(root);
}
//后序遍历
void postOrder(){
postOrder(root);
}
//层序遍历
void levelOrder(){
queue<Node*> q;
q.push(root);
while(!q.empty()){
Node *node = q.front();
q.pop();
cout << node->key << endl;
if(node->left)
q.push(node->left);
if(node->right)
q.push(node->right);
}
}
//最小值
Key minimum(){
assert(count != 0);
Node *minNode = minimum(root);
return minNode->key;
}
//最大值
Key maximum(){
assert(count != 0);
Node *maxNode = maximum(root);
return maxNode->key;
}
//删除最小值
void removeMin(){
if(root) root = removeMin(root);
}
//删除最大值
void removeMax(){
if(root) root = removeMax(root);
}
//删除某一个元素
void remove(Key key){
root = remove(root, key);
}
};
#endif //WORKSPACE_BINARY_SEARCH_TREE_H
/**
* C++ 语言: 二叉搜索树
*/
#include <iostream>
#include <vector>
#include "binary_search_tree.h"
using namespace std;
int main(){
vector<int> nums = {28,16,13,22,30,29,42};
//创建二叉搜索树；
BST<int, int> bst;
for(int i = 0; i < nums.size(); i++){
bst.insert(nums[i], nums[i]);
}
//先序遍历二叉搜索树；
bst.preOrder();
//最大，最小值；
cout << "max value:" << bst.maximum() << endl;
cout << "min value:" << bst.minimum() << endl;
cout << "contain value:" << bst.contain(12) << endl;
cout << "search value:" << *bst.search(29) << endl;
//删除元素；
bst.remove(30);
bst.preOrder();
return 0;
}
参考资料
网友评论