1. 定义

对于一颗二叉树，如果树中每个结点的值都大于左子树中所有结点的值并且小于右子树中所有结点的值，对于这种树我们将它叫做二叉查找树(Binary Search Tree)

2. 算法

  1. //如果二叉查找树中不存在该值，则创建一个含有该值的结点插入到二叉树中
  2. TreeNode* put(TreeNode* root, int val){
  3.     if (!root) return new TreeNode(val);
  4.     if (val < root->val) root->left = put(root->left, val);
  5.     else if (val > root->val) root->right = put(root->right, val);
  6.     return root;
  7. }
  1. bool find(TreeNode* root, int val){
  2.     if (!root) return false;
  3.     if (val == root->val) return true;
  4.     else if (val > root->val) return find(root->right, val);
  5.     else return find(root->left, val);
  6. }
  1. TreeNode* max(TreeNode* root){
  2.     if (root->right) return max(root->right);
  3.     return root;
  4. }
  6. TreeNode* min(TreeNode* root){
  7.     if (root->left) return min(root->left);
  8.     return root;
  9. }
  1. //要删除二叉查找树上的一个结点，有两种情况
  2. //1.该结点有一颗子树为空(或者两颗都空)，将父结点指向该节点的指针改为指向该节点的另一颗子树
  3. //2.两颗子树都不为空，将右子树中最小的结点删除，使用其替换当前结点(也可以使用左子树最大结点)
  5. TreeNode* deleteMin(TreeNode* root){
  6.     if (!root->left) return root->right;
  7.     root->left = deleteMin(root->left);
  8.     return root;
  9. }
  11. TreeNode* delete(TreeNode* root, int val){
  12.     if (!root) return nullptr;
  14.     if (root->val < val) root->right = delete(root->right, val);
  15.     else if (root->val > val) root->left = delete(root->left, val);
  16.     else{
  17.         if (!root->left) return root->right;
  18.         if (!root->right) return root->left;
  19.         TreeNode* leftMinNode = min(root->left);
  20.         leftMinNode->right = deleteMin(root->right);
  21.         leftMinNode->left = root->left;
  22.         root = leftMinNode;
  23.     }
  24.     return root;
  25. }