二叉搜索树

二叉搜索树（BST，Binary Search Tree），也称二叉排序树或二叉查找树。
二叉搜索树：一棵二叉树，可以为空；如果不为空，满足以下性质：
非空左子树的所有键值小于其根结点的键值。
非空右子树的所有键值大于其根结点的键值。
左、右子树都是二叉搜索树。
性能分析：
最好情况满二叉树时间复杂度是 O(log2n) ，如果二叉搜索树完全不平衡则其深度可达到n，查找效率为O(n)，退化为顺序查找。
平衡二叉搜索树可以让时间复杂度更稳定。

代码

头文件

#include <cstddef>
#include <iostream>
#include <vector>
using namespace std;

template <class T> class TreeNode {
public:
  T elem;
  TreeNode<T> *left, *right, *father;
  TreeNode(T elem) {
    this->elem = elem;
    left = NULL;
    right = NULL;
    father = NULL;
  }
};

template <class T> class BST {
private:
  TreeNode<T> *root = NULL;
  vector<T> vec;
  int nodeCount = 0;
  // 搜索某个节点是否存在
  TreeNode<T> *FindNode(T x) {
    TreeNode<T> *obj = root;
    while (obj) {
      if (obj->elem > x) {
        obj = obj->left;
      } else if (obj->elem < x) {
        obj = obj->right;
      } else {
        return obj;
        break;
      }
    }
    return obj; // 如果树为空，返回false，没找到，不为空返回地址。
  }
  // 删除节点
  void DelNode(TreeNode<T> *node) {
    TreeNode<T> *temp;
    if (NULL == node->right) { // 如果右子节点为空
      if (node->left != NULL) {
        node->father->left = node->left;
        node->left->father = node->father;
      } else
        node->father->left = NULL;
      delete (node);
    } else { // 如果右子节点不空
      temp = node->right;
      while (NULL != temp->left) {
        temp = temp->left;
      }
      temp->father = node->father;
      temp->father->left = NULL;
      if (node == node->father->left)
        node->father->left = temp;
      else
        node->father->right = temp;
      if (node->left != NULL) {
        temp->right = node->right;
        node->left->father = temp;
      }
      if (node->right != NULL) {
        temp->left = node->left;
        node->right->father = temp;
      }
      delete (node);
    }
    nodeCount--;
  }
  void getBST(TreeNode<T> *node) //       先序遍历二叉树
  {
    if (node == NULL) //    递归中遇到NULL，返回上一层节点
    {
      return;
    }
    getBST(node->left); //   递归遍历左子树
    vec.push_back(node->elem);
    getBST(node->right); //  递归遍历右子树
  }

public:
  BST(){};
  void Insert_Node(T val) {
    if (root == NULL)
      root = new TreeNode<T>(val);
    else {
      TreeNode<T> *temp = root;
      while (true) {
        if (temp->elem < val) {
          if (temp->right == NULL) {
            TreeNode<T> *node = new TreeNode<T>(val);
            temp->right = node;
            node->father = temp;
            break;
          }
          temp = temp->right;
        } else if (temp->elem > val) {
          if (temp->left == NULL) {
            TreeNode<T> *node = new TreeNode<T>(val);
            temp->left = node;
            node->father = temp;
            break;
          }
          temp = temp->left;
        }
      }
    }
    nodeCount++;
  }
  void Create_SearchTree(vector<T> &vec) {
    int sz = vec.size();
    for (int i = 0; i < sz; i++) {
      Insert_Node(vec[i]);
    }
  }
  T getMaxValue() {
    TreeNode<T> *temp = root;
    while (temp->right) {
      temp = temp->right;
    }
    return temp->elem;
  }
  T getMinValue() {
    TreeNode<T> *temp = root;
    while (temp->left) {
      temp = temp->left;
    }
    return temp->elem;
  }
  bool deleteNode(T val) {
    TreeNode<T> *temp = FindNode(val);
    if (NULL == temp) {
      return false;
    }
    DelNode(temp);
    return true;
  }
  bool isExist(T val) {
    if (FindNode(val) == NULL)
      return false;
    return true;
  }
  T getRootValue() { return root->elem; }
  int getNodeCount() { return nodeCount; }
  vector<T> getArr() {
    getBST(root);
    return vec;
  }
};

测试

新建数组，之后bst构建二叉搜索树，查看节点存在，添加、删除。

#include "BST.h"
int main(){
    BST<int> bst;
    vector<int> vector;
    vector.push_back(5);
    vector.push_back(6);
    vector.push_back(7);
    vector.push_back(8);
    vector.push_back(1);
    vector.push_back(2);
    vector.push_back(3);
    vector.push_back(4);
    bst.Create_SearchTree(vector);
    bst.Insert_Node(98);
    cout<<bst.isExist(2)<<endl;
    cout<<bst.getMaxValue()<<endl;
    cout<<bst.deleteNode(3)<<endl;
    cout<<"3:"<<bst.isExist(3)<<endl;
    ::vector<int> vec=bst.getArr();
    int count=bst.getNodeCount();
    cout<<endl<<"vec:";
    for(int i=0;i<count;i++){
        cout<<vec[i]<<" ";
    }
    cout<<endl;
    return 0;
}

测试结果

1
98
1
3:0

vec:1 2 4 5 6 7 8 98