二叉搜索树的增删查

数据结构与算法
二叉搜索树
Catalogue
  1. 1. 介绍
  2. 2. 二叉树的插入
  3. 3. 二叉树的查询
  4. 4. 二叉树的删除
    1. 4.1. 1.要删除的节点是一片树叶
    2. 4.2. 2.要删除的节点有一个儿子
    3. 4.3. 3. 要删除的节点有两个儿子
    4. 4.4. 删除代码
  5. 5. 参考资料

介绍

二叉树搜索树(BST)是二叉树的一种特殊表示形式，主要有以下特性:

  • 每个节点的值必须大于存储在左侧子树的任何值
  • 每个节点的值必须小于存储在右侧子树的任何值
  • 任意节点的左右子树也分别为二叉查找树

例子:

bstbst

下面就介绍关于二叉搜索树的「增删查」

二叉树的插入

节点类

1
2
3
4
5
6
7
8
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
  * 插入操作
  *
  * @param root
  * @param val
  * @return
  */
 public TreeNode insert(TreeNode root, int val) {
     if (root == null) {
         return new TreeNode(val);
     }
     if (root.val > val) {
         root.left = insert(root.left, val);
     } else if (root.val < val) {
         root.right = insert(root.right, val);
     } 
     return root;
 }

二叉树的查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * 查找二叉树是否包含某个元素
 *
 * @param root
 * @param val
 * @return
 */
public boolean contains(TreeNode root,int val) {
    //二叉树为空时，返回false
    if (root == null) {
        return false;
    }
    if (root.val > val) {
        return contains(root.left, val);
    } else if (root.val < val) {
        return contains(root.right, val);
    } else {
        return true;
    }
}

二叉树的删除

二叉树的删除比查询，插入麻烦一点，需要考虑几种情况。

1.要删除的节点是一片树叶

这种情况就可以直接删除

tree1tree1

2.要删除的节点有一个儿子

可以将儿子的值调整到父节点
t2t2

3. 要删除的节点有两个儿子

这种情况就比较复杂，一般的删除策略是用其右子树的最小数据去代替该节点的数据，然后再将最小数据所在的节点删除掉
t3t3

删除代码

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
    * 删除元素
    *
    * @param val
    */
   public void remove(int val) {
       remove(root, val);
   }
   /**
    * 删除元素
    *
    * @param root
    * @param val
    * @return
    */
   public TreeNode remove(TreeNode root, int val) {
       if (root == null) {
           return root;
       }
       if (root.val > val) {
           root.left = remove(root.left, val);
       } else if (root.val < val) {
           root.right = remove(root.right, val);
       } else {
           //节点只有一个儿子，或者说没有儿子
           if (root.left == null) {
               return root.right;
           } else if (root.right == null) {
               return root.left;
           }
           //当节点有两个儿子时,一般的策略是用其右子树的最小的数据来代替父节点的位置
           root.val = finaMin(root.right);
           //然后再删除掉最小数据所在的节点
           root.right = remove(root.right, root.val);
       }
       return root;
   }

   /**
    * 找出右子树最小值
    *
    * @param right
    * @return
    */
   private int finaMin(TreeNode right) {
       if (right.left == null) {
           return right.val;
       } else {
           return finaMin(right.left);
       }
   }

参考资料

Bagikan Komentar