二叉搜索树原理及操作

刺骨的言语ヽ痛彻心扉 2022-11-17 13:44 171阅读 0赞

### 二叉搜索树 ###

*  原理
 *  构建二叉搜索树
 *   *  查找
     *  插入
     *  删除

# 原理 #

二叉搜索树（Binary Search Tree BST）  
又称为二叉排序树，它是一颗空树或者具有以下性质：

*  它的左子树不为空，则左子树上所有节点的值都小于根节点的值
 *  它的右子树不为空，则右子树上所有节点的值都大于根节点的值
 *  它的左右子树也是二叉搜索树

简单来说：  
每个结点， 节点左子树中所有的key值，都小于节点的key值； 节点右子树中所有的key值，都大于节点的key值  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]  
所以：二叉搜索树的中序遍历，一定有序

# 构建二叉搜索树 #

节点：

public class Node { 
        public int key;
        public Node left;
        public Node right;
    
        public Node(int key) { 
            this.key = key;
        }
    
        @Override
        public String toString() { 
            return "Node{" +
                    "val=" + key +
                    '}';
        }
    }

二叉搜索树

public class BSTree { 
        public Node root;
    
        public BSTree() { 
            this.root = null;
        }
    }

## 查找 ##

查找，过程从root进入，当root为空时候，返回false，当root不为空时，key的值比root.key大，则朝右走，否则则往左走。一直走到叶子结束。

//查找
        public boolean find(int key) { 
            if (root == null) { 
                return false;
            }
            Node cur = root;
            while (cur != null) { 
                if (cur.key == key) { 
                    return true;
                } else if (cur.key < key) { 
                    cur = cur.right;
                } else { 
                    cur = cur.left;
                }
            }
            return false;
        }

## 插入 ##

先判断是否是空树，如果是，则直接将root=node；在进行查找，和上面查找过程相似，需要找到适合插入的位置，结点中不能重复，所以当cur.key=key时候，抛出异常，找到合适的位置，将结点插入

//插入
        public void insert(int key) { 
            Node node = new Node(key);
            if (root == null) { 
                root = node;
                return;
            }
            Node cur = root;
            Node parent = null;
            while (cur != null) { 
                if (cur.key == key) { 
                    throw new RuntimeException("");
                } else if (cur.key > key) { 
                    parent = cur;
                    cur = cur.left;
                } else { 
                    parent = cur;
                    cur = cur.right;
                }
            }
    
            if (parent.key < key) { 
                parent.right = node;
            } else { 
                parent.left = node;
            }
        }

## 删除 ##

当要删除一个二叉搜索树的时候，那么我们该如何操作呢？  
当然我们不能直接删除，我们需要删除完成后，还要保证二叉搜索的性质。

思路：

1.  如果不存在，不删除
2.  存在  
    1、叶子结点，直接删除  
    2、只有一个孩子结点，让孩子继承地位  
    3、有两个孩子，替换删除  
    找到key的后继（比key大的最后一个goat）  
    goat最后一定没有左孩子  
    替换，删除goat。

即：

一、找到待删除结点
    1、node.left = null
    包含node.right == null 和 node.right != null
        (1) node没有父节点  ——> root = node.right
        (2) node是父节点左孩子——> parent.left = node.right
        (3) node是右孩子 ——>parent.right = node.right
    2、node.right == null && node.left != null
         和1一样，镜像处理
    3、left 和 right 都 != null 
        (1) 找到node.key的后继  goat
    	    node.right 然后一直向左走，直到 left == null 停下
        (2) node.key = goat.key (替换)
        (3) 删除 goat结点
    goat 一定没有左孩子，一定有parent
        if(goat 的parent == node）{ 
    	    goat的parent.right = goat.right;
        }else{ 
    	    goat的parent.left == goat.right;
        }

实现：

//删除
        public boolean remove(int key) { 
            Node cur = root;
            Node parent = null;
            while (cur != null) { 
                if (cur.key == key) { 
                    //删除
                    removeNode(parent, cur);
                    return true;
                } else if (key < cur.key) { 
                    parent = cur;
                    cur = cur.left;
                } else { 
                    parent = cur;
                    cur = cur.right;
                }
            }
            return false;
        }
    
        //删除操作
        private void removeNode(Node parent, Node cur) { 
            if (cur.left == null) { 
                if (cur == root) { 
                    root = cur.right;
                } else if (parent.left == cur) { 
                    parent.left = cur.right;
                } else { 
                    parent.right = cur.right;
                }
            } else if (cur.right == null) { 
                if (cur == root) { 
                    root = cur.left;
                } else if (parent.left == cur) { 
                    parent.left = cur.left;
                } else { 
                    parent.right = cur.left;
                }
            } else { 
                Node goat = cur.right;
                Node goatParent = cur;
                while (goat.left != null) { 
                    goatParent = goat;
                    goat = goat.left;
                }
                //替换
                cur.key = goat.key;
                //删除
                if (goatParent == cur) { 
                    goatParent.right = goat.right;
                } else { 
                    goatParent.left = goat.right;
                }
            }
        }

测试：

public class Test { 
        private static void inorder(Node node) { 
            if (node != null) { 
                inorder(node.left);
                System.out.print(node.key + " ");
                inorder(node.right);
            }
        }
    
        public static void main(String[] args) { 
            BSTree tree1 = new BSTree();
            int[] keys1 = { 5, 3, 7, 2, 4, 6, 8, 1, 9};
            for (int key : keys1) { 
                tree1.insert(key);
            }
            inorder(tree1.root);
            tree1.remove(7);
            //preorder(tree1.root);
            System.out.println();
            inorder(tree1.root);
            System.out.println();
            System.out.println(tree1.find(3));
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]: /images/20221022/fbed00b85d214b9ebd3e1ae2a766ebcc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]: /images/20221022/e718d8eda5db4f748ea82458b4b0927e.png