这篇文章主要为大家详细介绍了java二叉查找树的实现代码，具有一定的参考价值，感兴趣的小伙伴们可以参考一下
本文实例为大家分享了java二叉查找树的具体代码，供大家参考，具体内容如下
package 查找; import edu.princeton.cs.algs4.Queue; import edu.princeton.cs.algs4.StdOut; public class BST, Value> { private class Node { private Key key; // 键 private Value value;// 值 private Node left, right; // 指向子树的链接 private int n; // 以该节点为根的子树中的节点总数 public Node(Key key, Value val, int n) { this.key = key; this.value = val; this.n = n; } } private Node root; public int size() { return size(root); } private int size(Node x) { if (x == null) return 0; else return x.n; } /** * 如果树是空的，则查找未命中 如果被查找的键小于根节点，则在左子树中继续查找 如果被查找的键大于根节点，则在右子树中继续查找 * 如果被查找的键和根节点的键相等，查找命中 * * @param key * @return */ public Value get(Key key) { return get(root, key); } private Value get(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp < 0) return get(x.left, key); else if (cmp > 0) return get(x.right, key); else return x.value; } /** * 二叉查找树的一个很重要的特性就是插入的实现难度和查找差不多。 当查找到一个不存在与树中的节点（null）时，new 新节点，并将上一路径指向该节点 * * @param key * @param val */ public void put(Key key, Value val) { root = put(root, key, val); } private Node put(Node x, Key key, Value val) { if (x == null) return new Node(key, val, 1); int cmp = key.compareTo(x.key); if (cmp < 0) x.left = put(x.left, key, val); else if (cmp > 0) x.right = put(x.right, key, val); else x.value = val; x.n = size(x.left) + size(x.right); // 要及时更新节点的子树数量 return x; } public Key min() { return min(root).key; } private Node min(Node x) { if (x.left == null) return x; return min(x.left); } public Key max() { return max(root).key; } private Node max(Node x) { if (x.right == null) return x; return min(x.right); } /** * 向下取整：找出小于等于该键的最大键 * * @param key * @return */ public Key floor(Key key) { Node x = floor(root, key); if (x == null) return null; else return x.key; } /** * 如果给定的键key小于二叉查找树的根节点的键，那么小于等于key的最大键一定出现在根节点的左子树中 * 如果给定的键key大于二叉查找树的根节点，那么只有当根节点右子树中存在大于等于key的节点时， * 小于等于key的最大键才会出现在右子树中，否则根节点就是小于等于key的最大键 * * @param x * @param key * @return */ private Node floor(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp == 0) return x; else if (cmp < 0) return floor(x.left, key); else { Node t = floor(x.right, key); if (t == null) return x; else return t; } } /** * 向上取整：找出大于等于该键的最小键 * * @param key * @return */ public Key ceiling(Key key) { Node x = ceiling(root, key); if (x == null) return null; else return x.key; } /** * 如果给定的键key大于二叉查找树的根节点的键，那么大于等于key的最小键一定出现在根节点的右子树中 * 如果给定的键key小于二叉查找树的根节点，那么只有当根节点左子树中存在大于等于key的节点时， * 大于等于key的最小键才会出现在左子树中，否则根节点就是大于等于key的最小键 * * @param x * @param key * @return */ private Node ceiling(Node x, Key key) { if (x == null) return null; int cmp = key.compareTo(x.key); if (cmp == 0) return x; else if (cmp > 0) { return ceiling(x.right, key); } else { Node t = floor(x.left, key); if (t == null) return x; else return t; } } /** * 选择排名为k的节点 * * @param k * @return */ public Key select(int k) { return select(root, k).key; } private Node select(Node x, int k) { if (x == null) return null; int t = size(x.left); if (t > k) return select(x.left, k); else if (t < k) return select(x.right, k - t - 1);// 根节点也要排除掉 else return x; } /** * 查找给定键值的排名 * * @param key * @return */ public int rank(Key key) { return rank(key, root); } private int rank(Key key, Node x) { if (x == null) return 0; int cmp = key.compareTo(x.key); if (cmp < 0) return rank(key, x.left); else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right); else return size(x.left); } /** * 删除最小键值对 */ public void deleteMin(){ root = deleteMin(root); } /** * 不断深入根节点的左子树直到遇见一个空链接，然后将指向该节点的链接指向该结点的右子树 * 此时已经没有任何链接指向要被删除的结点，因此它会被垃圾收集器清理掉 * @param x * @return */ private Node deleteMin(Node x){ if(x.left == null) return x.right; x.left = deleteMin(x.left); x.n = size(x.left)+size(x.right) + 1; return x; } public void deleteMax(){ root = deleteMax(root); } private Node deleteMax(Node x){ if(x.right == null ) return x.left; x.right = deleteMax(x.right); x.n = size(x.left)+size(x.right) + 1; return x; } public void delete(Key key){ root = delete(root,key); } private Node delete(Node x, Key key){ if(x == null) return null; int cmp = key.compareTo(x.key); if(cmp < 0) x.left = delete(x.left,key); else if(cmp > 0) x.right = delete(x.right,key); else{ if(x.right == null) return x.left; if(x.left == null ) return x.right; /** * 如果被删除节点有两个子树，将被删除节点暂记为t * 从t的右子树中选取最小的节点x，将这个节点x的左子树设为t的左子树 * 这个节点x的右子树设为t的右子树中删除了最小节点的子树，这样就成功替换了t的位置 */ Node t = x; x = min(t.right); x.left = t.left; x.right = deleteMin(t.right); } x.n = size(x.left) + size(x.right) +1; return x; } public void print(){ print(root); } private void print(Node x){ if(x == null ) return; print(x.left); StdOut.println(x.key); print(x.right); } public Iterable keys(){ return keys(min(),max()); } public Iterable keys(Key lo, Key hi){ Queue queue = new Queue (); keys(root, queue, lo, hi); return queue; } private void keys(Node x, Queue queue, Key lo, Key hi){ if(x == null) return; int cmplo = lo.compareTo(x.key); int cmphi = lo.compareTo(x.key); if(cmplo < 0 ) keys(x.left,queue,lo,hi); if(cmplo <= 0 && cmphi >= 0) queue.enqueue(x.key); if(cmphi > 0 ) keys(x.right,queue,lo,hi); } }
