如何实现【数据结构与算法】中的二叉查找树操作？

本文共计2282个文字，预计阅读时间需要10分钟。

二叉查找树定义：二叉查找树（又称二叉搜索树、二叉排序树）是一棵二叉树，其中每个节点都有以下特性：所有左子节点的关键字值小于该节点的关键字值，所有右子节点的关键字值大于该节点的关键字值。根节点为空时，该树为空树。

等价描述：二叉查找树中，任意节点的左子树只包含关键字小于该节点的节点，右子树只包含关键字大于该节点的节点。

二叉查找树 定义

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

• 等价描述：二叉查找树中任一结点 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 和后继（前驱）节点的值，然后删除后继节点（后继/前驱节点只有一棵子树，转化为第二种情况）。
    后继结点是当前结点的右子树的最左结点，如果右子树没有左子树，则后继节点就是右子树的根节点。
    前驱结点时当前节点的左子树的最右结点，如果左子树没有右子树，则前驱结点就是左子树的根节点。
    
    

    

1️⃣ 写法一

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; }

2️⃣ 写法二

情况三也进行递归处理，写法更简单（考虑的前驱结点）

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 { else if (t.right == null) return t.left; else { BSTNode<K, V> pre = t.left; while (pre.right != null) { pre = pre.right; } t.key = pre.key; t.value = pre.value; t.left = removeByRecursion(t.left, t.key); } } 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 = root; int cmp = key.compareTo(p.key); while (p != null) { if (cmp < 0) p = p.left; else if (cmp > 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); } int cmp = key.compareTo(t.key); if (cmp < 0) t.left = insertByRecursion(t.left, key, value); else if (cmp > 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; int cmp = key.compareTo(p.key); if (cmp < 0) p = p.left; else if (cmp > 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; if (t.left == null) return t.right; else if (t.right == null) return t.left; else { BSTNode<K, V> pre = t.left; while (pre.right != null) { pre = pre.right; } t.key = pre.key; t.value = pre.value; t.left = removeByRecursion(t.left, t.key); } } return t; } }