【数据结构与算法】手撕二叉查找树

二叉查找树

定义

• 二叉查找树（亦称二叉搜索树、二叉排序树）是一棵二叉树，且各结点关键词互异，其中根序列按其关键词递增排列。

• 等价描述：二叉查找树中任一结点 P，其左子树中结点的关键词都小于 P 的关键词，右子树中结点的关键词都大于 P 的关键词，且结点 P 的左右子树也都是二叉查找树

节点结构

1?? key：关键字的值
2?? value：关键字的存储信息
3?? left：左节点的引用
4?? right：右节点的引用

class BSTNode<K extends Comparable<K>,V>{    public K key;    public V value;    public BSTNode<K,V> left;    public BSTNode<K,V> right;}

为了代码简洁，本文不考虑属性的封装，一律设为 public

查找算法

思想：利用二叉查找树的特性，左子树值小于根节点值，右子树值大于根节点值，从根节点开始搜索

• 如果目标值等于某节点值，返回该节点
• 如果目标值小于某节点值，搜索该节点的左子树
• 如果目标值大于某节点值，搜索该节点的右子树

1?? 递归版本

    public BSTNode<K, V> searchByRecursion(K key) {        return searchByRecursion(root, key);    }    private BSTNode<K, V> searchByRecursion(BSTNode<K, V> t, K key) {        if (t == null || t.key == key) return t;        else if (key.compareTo(t.key) < 0) return searchByRecursion(t.left, key);        else return searchByRecursion(t.right, key);    }

2?? 迭代版本

    public BSTNode<K,V> searchByIteration(K key) {        BSTNode<K,V> p = this.root;        while(p != null) {            if(key.compareTo(p.key) < 0) p = p.left;            else if(key.compareTo(p.key) > 0) p = p.right;            else return p;        }        return null;    }

插入算法

• 在以 t 为根的二叉查找树中插入关键词为 key 的结点
• 在 t 中查找 key，在查找失败处插入

1?? 递归版本

public void insertByRecursion(K key, V value) {        this.root = insertByRecursion(root, key, value);    }    private BSTNode<K, V> insertByRecursion(BSTNode<K, V> t, K key, V value) {        if (t == null) {            return new BSTNode<>(key, value);        }         else if (key.compareTo(t.key) < 0) t.left = insertByRecursion(t.left, key, value);        else if (key.compareTo(t.key) > 0) t.right = insertByRecursion(t.right, key, value);        else {            t.value = value;  // 如果二叉查找树中已经存在关键字，则替换该结点的值        }        return t;    }

2?? 迭代版本

    public void insertByIteration(K key, V value) {        BSTNode<K, V> p = root;        if (p == null) {            root = new BSTNode<>(key, value);            return;        }        BSTNode<K, V> pre = null;        while (p != null) {            pre = p;            if (key.compareTo(p.key) < 0) p = p.left;            else if (key.compareTo(p.key) > 0) p = p.right;            else {                p.value = value;    // 如果二叉查找树中已经存在关键字，则替换该结点的值                return;            }        }        if(key.compareTo(pre.key) < 0) {            pre.left = new BSTNode<>(key, value);        } else {            pre.right = new BSTNode<>(key, value);        }    }

删除算法

• 在以 t 为根的二叉查找树中删除关键词值为 key 的结点

• 在 t 中找到关键词为 key 的结点，分三种情况删除 key

  • 若 key 是叶子节点，则直接删除
    

  • 若 key 只有一棵子树，则子承父业
    

  • 若 key 既有左子树也有右子树，则找到 key 的后继结点，替换 key 和后继节点的值，然后删除后继节点（后继节点只有一棵子树，转化为第二种情况）。
    后继结点是当前结点的右子树的最左结点，如果右子树没有左子树，则后继节点就是右子树的根节点。
    
    

    public void removeByRecursion(K key) {        this.root = removeByRecursion(root, key);    }    private BSTNode<K, V> removeByRecursion(BSTNode<K, V> t, K key) {        if(t == null) return root;        else if(t.key.compareTo(key) < 0) t.right = removeByRecursion(t.right, key); // key大，递归处理右子树        else if(t.key.compareTo(key) > 0) t.left = removeByRecursion(t.left, key);   // key小，递归处理左子树        else {            if(t.right == null) return t.left;  // 情况一、二一起处理            if(t.left == null) return t.right;  // 情况一、二一起处理            BSTNode<K, V> node = t.right;       // 情况三：右子树没有左子树            if (node.left == null) {                node.left = t.left;            } else {                            // 情况三：右子树有左子树                BSTNode<K, V> pre = null;                while (node.left != null) {                    pre = node;                    node = node.left;                }                t.key = node.key;                t.value = node.value;                pre.left = node.right;            }        }        return t;    }

完整代码

class BSTNode<K extends Comparable<K>, V> {    public K key;    public V value;    public BSTNode<K, V> left;    public BSTNode<K, V> right;    public BSTNode(K key, V value) {        this.key = key;        this.value = value;    }}class BSTree<K extends Comparable<K>, V> {    public BSTNode<K, V> root;    private void inorder(BSTNode<K, V> root) {        if (root != null) {            inorder(root.left);            System.out.print("(key: " + root.key + " , value: " + root.value + ") ");            inorder(root.right);        }    }    private void preorder(BSTNode<K, V> root) {        if (root != null) {            System.out.print("(key: " + root.key + " , value: " + root.value + ") ");            preorder(root.left);            preorder(root.right);        }    }    private void postorder(BSTNode<K, V> root) {        if (root != null) {            postorder(root.left);            postorder(root.right);            System.out.print("(key: " + root.key + " , value: " + root.value + ") ");        }    }    public void postorderTraverse() {        System.out.print("后序遍历：");        postorder(root);        System.out.println();    }    public void preorderTraverse() {        System.out.print("先序遍历：");        preorder(root);        System.out.println();    }    public void inorderTraverse() {        System.out.print("中序遍历：");        inorder(root);        System.out.println();    }    public BSTNode<K, V> searchByRecursion(K key) {        return searchByRecursion(root, key);    }    private BSTNode<K, V> searchByRecursion(BSTNode<K, V> t, K key) {        if (t == null || t.key == key) return t;        else if (key.compareTo(t.key) < 0) return searchByRecursion(t.left, key);        else return searchByRecursion(t.right, key);    }    public BSTNode<K, V> searchByIteration(K key) {        BSTNode<K, V> p = this.root;        while (p != null) {            if (key.compareTo(p.key) < 0) p = p.left;            else if (key.compareTo(p.key) > 0) p = p.right;            else return p;        }        return null;    }    public void insertByRecursion(K key, V value) {        this.root = insertByRecursion(root, key, value);    }    private BSTNode<K, V> insertByRecursion(BSTNode<K, V> t, K key, V value) {        if (t == null) {            return new BSTNode<>(key, value);        } else if (key.compareTo(t.key) < 0) t.left = insertByRecursion(t.left, key, value);        else if (key.compareTo(t.key) > 0) t.right = insertByRecursion(t.right, key, value);        else {            t.value = value;        }        return t;    }    public void insertByIteration(K key, V value) {        BSTNode<K, V> p = root;        if (p == null) {            root = new BSTNode<>(key, value);            return;        }        BSTNode<K, V> pre = null;        while (p != null) {            pre = p;            if (key.compareTo(p.key) < 0) p = p.left;            else if (key.compareTo(p.key) > 0) p = p.right;            else {                p.value = value;    // 如果二叉查找树中已经存在关键字，则替换该结点的值                return;            }        }        if (key.compareTo(pre.key) < 0) {            pre.left = new BSTNode<>(key, value);        } else {            pre.right = new BSTNode<>(key, value);        }    }    public void removeByRecursion(K key) {        this.root = removeByRecursion(root, key);    }    private BSTNode<K, V> removeByRecursion(BSTNode<K, V> t, K key) {        if(t == null) return root;        else if(t.key.compareTo(key) < 0) t.right = removeByRecursion(t.right, key); // key大，递归处理右子树        else if(t.key.compareTo(key) > 0) t.left = removeByRecursion(t.left, key);   // key小，递归处理左子树        else {            if(t.right == null) return t.left;  // 情况一、二一起处理            if(t.left == null) return t.right;  // 情况一、二一起处理            BSTNode<K, V> node = t.right;       // 情况三：右子树没有左子树            if (node.left == null) {                node.left = t.left;            } else {                            // 情况三：右子树有左子树                BSTNode<K, V> pre = null;                while (node.left != null) {                    pre = node;                    node = node.left;                }                t.key = node.key;                t.value = node.value;                pre.left = node.right;            }        }        return t;    }}

?? 方法测试：

public class Main {    public static void main(String[] args) {        BSTree<Integer, Integer> tree = new BSTree<>();//        tree.insertByRecursion(1, 1);//        tree.insertByRecursion(5, 1);//        tree.insertByRecursion(2, 1);//        tree.insertByRecursion(4, 1);//        tree.insertByRecursion(3, 1);//        tree.insertByRecursion(1, 2);        tree.insertByIteration(1, 1);        tree.insertByIteration(5, 1);        tree.insertByIteration(2, 1);        tree.insertByIteration(4, 1);        tree.insertByIteration(3, 1);        tree.insertByIteration(1, 5);        tree.removeByRecursion(4);        tree.inorderTraverse();        tree.postorderTraverse();        tree.preorderTraverse();        BSTNode<Integer, Integer> node = tree.searchByIteration(1);        System.out.println(node.key + " " + node.value);    }}

中序遍历：(key: 1 , value: 5) (key: 2 , value: 1) (key: 3 , value: 1) (key: 5 , value: 1) 后序遍历：(key: 3 , value: 1) (key: 2 , value: 1) (key: 5 , value: 1) (key: 1 , value: 5) 先序遍历：(key: 1 , value: 5) (key: 5 , value: 1) (key: 2 , value: 1) (key: 3 , value: 1) 1 5