二叉search树 – Java实现
我正在编写一个程序，利用二叉search树来存储数据。 在以前的程序（不相关）中，我能够使用Java SE6提供的实现来实现链表。 是否有类似的二叉search树，还是我需要“从头开始”？
你可以使用一个TreeMap 。 TreeMap被实现为红黑树 ，它是一个自平衡二叉search树。
根据集合框架概述，您有两个平衡的树实现：
- TreeSet中
- TreeMap的
这是一个示例实现：
import java.util.*; public class MyBSTree<K,V> implements MyTree<K,V>{ private BSTNode<K,V> _root; private int _size; private Comparator<K> _comparator; private int mod = 0; public MyBSTree(Comparator<K> comparator){ _comparator = comparator; } public Node<K,V> root(){ return _root; } public int size(){ return _size; } public boolean containsKey(K key){ if(_root == null){ return false; } BSTNode<K,V> node = _root; while (node != null){ int comparison = compare(key, node.key()); if(comparison == 0){ return true; }else if(comparison <= 0){ node = node._left; }else { node = node._right; } } return false; } private int compare(K k1, K k2){ if(_comparator != null){ return _comparator.compare(k1,k2); } else { Comparable<K> comparable = (Comparable<K>)k1; return comparable.compareTo(k2); } } public V get(K key){ Node<K,V> node = node(key); return node != null ? node.value() : null; } private BSTNode<K,V> node(K key){ if(_root != null){ BSTNode<K,V> node = _root; while (node != null){ int comparison = compare(key, node.key()); if(comparison == 0){ return node; }else if(comparison <= 0){ node = node._left; }else { node = node._right; } } } return null; } public void add(K key, V value){ if(key == null){ throw new IllegalArgumentException("key"); } if(_root == null){ _root = new BSTNode<K, V>(key, value); } BSTNode<K,V> prev = null, curr = _root; boolean lastChildLeft = false; while(curr != null){ int comparison = compare(key, curr.key()); prev = curr; if(comparison == 0){ curr._value = value; return; }else if(comparison < 0){ curr = curr._left; lastChildLeft = true; } else{ curr = curr._right; lastChildLeft = false; } } mod++; if(lastChildLeft){ prev._left = new BSTNode<K, V>(key, value); }else { prev._right = new BSTNode<K, V>(key, value); } } private void removeNode(BSTNode<K,V> curr){ if(curr.left() == null && curr.right() == null){ if(curr == _root){ _root = null; }else{ if(curr.isLeft()) curr._parent._left = null; else curr._parent._right = null; } } else if(curr._left == null && curr._right != null){ curr._key = curr._right._key; curr._value = curr._right._value; curr._left = curr._right._left; curr._right = curr._right._right; } else if(curr._left != null && curr._right == null){ curr._key = curr._left._key; curr._value = curr._left._value; curr._right = curr._left._right; curr._left = curr._left._left; } else { // both left & right exist BSTNode<K,V> x = curr._left; // find right-most node of left sub-tree while (x._right != null){ x = x._right; } // move that to current curr._key = x._key; curr._value = x._value; // delete duplicate data removeNode(x); } } public V remove(K key){ BSTNode<K,V> curr = _root; V val = null; while(curr != null){ int comparison = compare(key, curr.key()); if(comparison == 0){ val = curr._value; removeNode(curr); mod++; break; }else if(comparison < 0){ curr = curr._left; } else{ curr = curr._right; } } return val; } public Iterator<MyTree.Node<K,V>> iterator(){ return new MyIterator(); } private class MyIterator implements Iterator<Node<K,V>>{ int _startMod; Stack<BSTNode<K,V>> _stack; public MyIterator(){ _startMod = MyBSTree.this.mod; _stack = new Stack<BSTNode<K, V>>(); BSTNode<K,V> node = MyBSTree.this._root; while (node != null){ _stack.push(node); node = node._left; } } public void remove(){ throw new UnsupportedOperationException(); } public boolean hasNext(){ if(MyBSTree.this.mod != _startMod){ throw new ConcurrentModificationException(); } return !_stack.empty(); } public Node<K,V> next(){ if(MyBSTree.this.mod != _startMod){ throw new ConcurrentModificationException(); } if(!hasNext()){ throw new NoSuchElementException(); } BSTNode<K,V> node = _stack.pop(); BSTNode<K,V> x = node._right; while (x != null){ _stack.push(x); x = x._left; } return node; } } @Override public String toString(){ if(_root == null) return "[]"; return _root.toString(); } private static class BSTNode<K,V> implements Node<K,V>{ K _key; V _value; BSTNode<K,V> _left, _right, _parent; public BSTNode(K key, V value){ if(key == null){ throw new IllegalArgumentException("key"); } _key = key; _value = value; } public K key(){ return _key; } public V value(){ return _value; } public Node<K,V> left(){ return _left; } public Node<K,V> right(){ return _right; } public Node<K,V> parent(){ return _parent; } boolean isLeft(){ if(_parent == null) return false; return _parent._left == this; } boolean isRight(){ if(_parent == null) return false; return _parent._right == this; } @Override public boolean equals(Object o){ if(o == null){ return false; } try{ BSTNode<K,V> node = (BSTNode<K,V>)o; return node._key.equals(_key) && ((_value == null && node._value == null) || (_value != null && _value.equals(node._value))); }catch (ClassCastException ex){ return false; } } @Override public int hashCode(){ int hashCode = _key.hashCode(); if(_value != null){ hashCode ^= _value.hashCode(); } return hashCode; } @Override public String toString(){ String leftStr = _left != null ? _left.toString() : ""; String rightStr = _right != null ? _right.toString() : ""; return "["+leftStr+" "+_key+" "+rightStr+"]"; } } }
这是我在Java SE 1.8中简单的二叉查找树实现：
public class BSTNode { int data; BSTNode parent; BSTNode left; BSTNode right; public BSTNode(int data) { this.data = data; this.left = null; this.right = null; this.parent = null; } public BSTNode() { } } public class BSTFunctions { BSTNode ROOT; public BSTFunctions() { this.ROOT = null; } void insertNode(BSTNode node, int data) { if (node == null) { node = new BSTNode(data); ROOT = node; } else if (data < node.data && node.left == null) { node.left = new BSTNode(data); node.left.parent = node; } else if (data >= node.data && node.right == null) { node.right = new BSTNode(data); node.right.parent = node; } else { if (data < node.data) { insertNode(node.left, data); } else { insertNode(node.right, data); } } } public boolean search(BSTNode node, int data) { if (node == null) { return false; } else if (node.data == data) { return true; } else { if (data < node.data) { return search(node.left, data); } else { return search(node.right, data); } } } public void printInOrder(BSTNode node) { if (node != null) { printInOrder(node.left); System.out.print(node.data + " - "); printInOrder(node.right); } } public void printPostOrder(BSTNode node) { if (node != null) { printPostOrder(node.left); printPostOrder(node.right); System.out.print(node.data + " - "); } } public void printPreOrder(BSTNode node) { if (node != null) { System.out.print(node.data + " - "); printPreOrder(node.left); printPreOrder(node.right); } } public static void main(String[] args) { BSTFunctions f = new BSTFunctions(); /** * Insert */ f.insertNode(f.ROOT, 20); f.insertNode(f.ROOT, 5); f.insertNode(f.ROOT, 25); f.insertNode(f.ROOT, 3); f.insertNode(f.ROOT, 7); f.insertNode(f.ROOT, 27); f.insertNode(f.ROOT, 24); /** * Print */ f.printInOrder(f.ROOT); System.out.println(""); f.printPostOrder(f.ROOT); System.out.println(""); f.printPreOrder(f.ROOT); System.out.println(""); /** * Search */ System.out.println(f.search(f.ROOT, 27) ? "Found" : "Not Found"); System.out.println(f.search(f.ROOT, 10) ? "Found" : "Not Found"); } }
输出是：
3 - 5 - 7 - 20 - 24 - 25 - 27 - 3 - 7 - 5 - 24 - 27 - 25 - 20 - 20 - 5 - 3 - 7 - 25 - 24 - 27 - Found Not Found
这个程序有一个function
- 添加节点
- 显示BST（Inorder）
- 查找元素
-
find继任者
class BNode{ int data; BNode left, right; public BNode(int data){ this.data = data; this.left = null; this.right = null; } } public class BST { static BNode root; public int add(int value){ BNode newNode, current; newNode = new BNode(value); if(root == null){ root = newNode; current = root; } else{ current = root; while(current.left != null || current.right != null){ if(newNode.data < current.data){ if(current.left != null) current = current.left; else break; } else{ if(current.right != null) current = current.right; else break; } } if(newNode.data < current.data) current.left = newNode; else current.right = newNode; } return value; } public void inorder(BNode root){ if (root != null) { inorder(root.left); System.out.println(root.data); inorder(root.right); } } public boolean find(int value){ boolean flag = false; BNode current; current = root; while(current!= null){ if(current.data == value){ flag = true; break; } else if(current.data > value) current = current.left; else current = current.right; } System.out.println("Is "+value+" present in tree? : "+flag); return flag; } public void successor(int value){ BNode current; current = root; if(find(value)){ while(current.data != value){ if(value < current.data && current.left != null){ System.out.println("Node is: "+current.data); current = current.left; } else if(value > current.data && current.right != null){ System.out.println("Node is: "+current.data); current = current.right; } } } else System.out.println(value+" Element is not present in tree"); } public static void main(String[] args) { BST b = new BST(); b.add(50); b.add(30); b.add(20); b.add(40); b.add(70); b.add(60); b.add(80); b.add(90); b.inorder(root); b.find(30); b.find(90); b.find(100); b.find(50); b.successor(90); System.out.println(); b.successor(70); } }
这里是二叉search树的完整实现在Java中插入，search，countNodes，遍历，删除，空，最大和最小节点，查找父节点，打印所有叶子节点，获取级别，获得高度，获取深度，打印左视图，镜子视图
import java.util.NoSuchElementException; import java.util.Scanner; import org.junit.experimental.max.MaxCore; class BSTNode { BSTNode left = null; BSTNode rigth = null; int data = 0; public BSTNode() { super(); } public BSTNode(int data) { this.left = null; this.rigth = null; this.data = data; } @Override public String toString() { return "BSTNode [left=" + left + ", rigth=" + rigth + ", data=" + data + "]"; } } class BinarySearchTree { BSTNode root = null; public BinarySearchTree() { } public void insert(int data) { BSTNode node = new BSTNode(data); if (root == null) { root = node; return; } BSTNode currentNode = root; BSTNode parentNode = null; while (true) { parentNode = currentNode; if (currentNode.data == data) throw new IllegalArgumentException("Duplicates nodes note allowed in Binary Search Tree"); if (currentNode.data > data) { currentNode = currentNode.left; if (currentNode == null) { parentNode.left = node; return; } } else { currentNode = currentNode.rigth; if (currentNode == null) { parentNode.rigth = node; return; } } } } public int countNodes() { return countNodes(root); } private int countNodes(BSTNode node) { if (node == null) { return 0; } else { int count = 1; count += countNodes(node.left); count += countNodes(node.rigth); return count; } } public boolean searchNode(int data) { if (empty()) return empty(); return searchNode(data, root); } public boolean searchNode(int data, BSTNode node) { if (node != null) { if (node.data == data) return true; else if (node.data > data) return searchNode(data, node.left); else if (node.data < data) return searchNode(data, node.rigth); } return false; } public boolean delete(int data) { if (empty()) throw new NoSuchElementException("Tree is Empty"); BSTNode currentNode = root; BSTNode parentNode = root; boolean isLeftChild = false; while (currentNode.data != data) { parentNode = currentNode; if (currentNode.data > data) { isLeftChild = true; currentNode = currentNode.left; } else if (currentNode.data < data) { isLeftChild = false; currentNode = currentNode.rigth; } if (currentNode == null) return false; } // CASE 1: node with no child if (currentNode.left == null && currentNode.rigth == null) { if (currentNode == root) root = null; if (isLeftChild) parentNode.left = null; else parentNode.rigth = null; } // CASE 2: if node with only one child else if (currentNode.left != null && currentNode.rigth == null) { if (root == currentNode) { root = currentNode.left; } if (isLeftChild) parentNode.left = currentNode.left; else parentNode.rigth = currentNode.left; } else if (currentNode.rigth != null && currentNode.left == null) { if (root == currentNode) root = currentNode.rigth; if (isLeftChild) parentNode.left = currentNode.rigth; else parentNode.rigth = currentNode.rigth; } // CASE 3: node with two child else if (currentNode.left != null && currentNode.rigth != null) { // Now we have to find minimum element in rigth sub tree // that is called successor BSTNode successor = getSuccessor(currentNode); if (currentNode == root) root = successor; if (isLeftChild) parentNode.left = successor; else parentNode.rigth = successor; successor.left = currentNode.left; } return true; } private BSTNode getSuccessor(BSTNode deleteNode) { BSTNode successor = null; BSTNode parentSuccessor = null; BSTNode currentNode = deleteNode.left; while (currentNode != null) { parentSuccessor = successor; successor = currentNode; currentNode = currentNode.left; } if (successor != deleteNode.rigth) { parentSuccessor.left = successor.left; successor.rigth = deleteNode.rigth; } return successor; } public int nodeWithMinimumValue() { return nodeWithMinimumValue(root); } private int nodeWithMinimumValue(BSTNode node) { if (node.left != null) return nodeWithMinimumValue(node.left); return node.data; } public int nodewithMaximumValue() { return nodewithMaximumValue(root); } private int nodewithMaximumValue(BSTNode node) { if (node.rigth != null) return nodewithMaximumValue(node.rigth); return node.data; } public int parent(int data) { return parent(root, data); } private int parent(BSTNode node, int data) { if (empty()) throw new IllegalArgumentException("Empty"); if (root.data == data) throw new IllegalArgumentException("No Parent node found"); BSTNode parent = null; BSTNode current = node; while (current.data != data) { parent = current; if (current.data > data) current = current.left; else current = current.rigth; if (current == null) throw new IllegalArgumentException(data + " is not a node in tree"); } return parent.data; } public int sibling(int data) { return sibling(root, data); } private int sibling(BSTNode node, int data) { if (empty()) throw new IllegalArgumentException("Empty"); if (root.data == data) throw new IllegalArgumentException("No Parent node found"); BSTNode cureent = node; BSTNode parent = null; boolean isLeft = false; while (cureent.data != data) { parent = cureent; if (cureent.data > data) { cureent = cureent.left; isLeft = true; } else { cureent = cureent.rigth; isLeft = false; } if (cureent == null) throw new IllegalArgumentException("No Parent node found"); } if (isLeft) { if (parent.rigth != null) { return parent.rigth.data; } else throw new IllegalArgumentException("No Sibling is there"); } else { if (parent.left != null) return parent.left.data; else throw new IllegalArgumentException("No Sibling is there"); } } public void leafNodes() { if (empty()) throw new IllegalArgumentException("Empty"); leafNode(root); } private void leafNode(BSTNode node) { if (node == null) return; if (node.rigth == null && node.left == null) System.out.print(node.data + " "); leafNode(node.left); leafNode(node.rigth); } public int level(int data) { if (empty()) throw new IllegalArgumentException("Empty"); return level(root, data, 1); } private int level(BSTNode node, int data, int level) { if (node == null) return 0; if (node.data == data) return level; int result = level(node.left, data, level + 1); if (result != 0) return result; result = level(node.rigth, data, level + 1); return result; } public int depth() { return depth(root); } private int depth(BSTNode node) { if (node == null) return 0; else return 1 + Math.max(depth(node.left), depth(node.rigth)); } public int height() { return height(root); } private int height(BSTNode node) { if (node == null) return 0; else return 1 + Math.max(height(node.left), height(node.rigth)); } public void leftView() { leftView(root); } private void leftView(BSTNode node) { if (node == null) return; int height = height(node); for (int i = 1; i <= height; i++) { printLeftView(node, i); } } private boolean printLeftView(BSTNode node, int level) { if (node == null) return false; if (level == 1) { System.out.print(node.data + " "); return true; } else { boolean left = printLeftView(node.left, level - 1); if (left) return true; else return printLeftView(node.rigth, level - 1); } } public void mirroeView() { BSTNode node = mirroeView(root); preorder(node); System.out.println(); inorder(node); System.out.println(); postorder(node); System.out.println(); } private BSTNode mirroeView(BSTNode node) { if (node == null || (node.left == null && node.rigth == null)) return node; BSTNode temp = node.left; node.left = node.rigth; node.rigth = temp; mirroeView(node.left); mirroeView(node.rigth); return node; } public void preorder() { preorder(root); } private void preorder(BSTNode node) { if (node != null) { System.out.print(node.data + " "); preorder(node.left); preorder(node.rigth); } } public void inorder() { inorder(root); } private void inorder(BSTNode node) { if (node != null) { inorder(node.left); System.out.print(node.data + " "); inorder(node.rigth); } } public void postorder() { postorder(root); } private void postorder(BSTNode node) { if (node != null) { postorder(node.left); postorder(node.rigth); System.out.print(node.data + " "); } } public boolean empty() { return root == null; } } public class BinarySearchTreeTest { public static void main(String[] l) { System.out.println("Weleome to Binary Search Tree"); Scanner scanner = new Scanner(System.in); boolean yes = true; BinarySearchTree tree = new BinarySearchTree(); do { System.out.println("\n1. Insert"); System.out.println("2. Search Node"); System.out.println("3. Count Node"); System.out.println("4. Empty Status"); System.out.println("5. Delete Node"); System.out.println("6. Node with Minimum Value"); System.out.println("7. Node with Maximum Value"); System.out.println("8. Find Parent node"); System.out.println("9. Count no of links"); System.out.println("10. Get the sibling of any node"); System.out.println("11. Print all the leaf node"); System.out.println("12. Get the level of node"); System.out.println("13. Depth of the tree"); System.out.println("14. Height of Binary Tree"); System.out.println("15. Left View"); System.out.println("16. Mirror Image of Binary Tree"); System.out.println("Enter Your Choice :: "); int choice = scanner.nextInt(); switch (choice) { case 1: try { System.out.println("Enter Value"); tree.insert(scanner.nextInt()); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 2: System.out.println("Enter the node"); System.out.println(tree.searchNode(scanner.nextInt())); break; case 3: System.out.println(tree.countNodes()); break; case 4: System.out.println(tree.empty()); break; case 5: try { System.out.println("Enter the node"); System.out.println(tree.delete(scanner.nextInt())); } catch (Exception e) { System.out.println(e.getMessage()); } case 6: try { System.out.println(tree.nodeWithMinimumValue()); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 7: try { System.out.println(tree.nodewithMaximumValue()); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 8: try { System.out.println("Enter the node"); System.out.println(tree.parent(scanner.nextInt())); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 9: try { System.out.println(tree.countNodes() - 1); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 10: try { System.out.println("Enter the node"); System.out.println(tree.sibling(scanner.nextInt())); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 11: try { tree.leafNodes(); } catch (Exception e) { System.out.println(e.getMessage()); } case 12: try { System.out.println("Enter the node"); System.out.println("Level is : " + tree.level(scanner.nextInt())); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 13: try { System.out.println(tree.depth()); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 14: try { System.out.println(tree.height()); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 15: try { tree.leftView(); System.out.println(); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 16: try { tree.mirroeView(); } catch (Exception e) { System.out.println(e.getMessage()); } break; default: break; } tree.preorder(); System.out.println(); tree.inorder(); System.out.println(); tree.postorder(); } while (yes); scanner.close(); } }
这里是二叉search树的实现
public class BST<Key extends Comparable<Key>,Value>{ private Node root; private class Node{ private Key key; private Value val; private Node left, right; private int N; public Node(Key key,Value val,int N) { this.key = key; this.val=val; this.N=N;} } public int size(){ return size(root); } public int size(Node x){ if(x==null) return 0; else return xN; } 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.val; } public Node put(Key key,Value val){ return 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.val=val; xN=size(x.left)+size(x.right)+1; 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;//min() changed to max() } private Node max(Node x){ if(x.right==null) return x; return max(x.right); } public Key select(int k){ return select(root,k).key; } private Node select(Node x,int k) { if(x==null)return null;//conditinoal equals int t=size(x.left); if(t>k) return(x.left,k); else if(t<k) return(x.right,kt-1); else return x; } public int rank(Key key,Node x) { 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); } private Node deleteMin(Node x){ if(x.left==null) return x.right; x.left=deleteMin(x.left); xN =size(x.left)+size(x.right)+1; return x; } public void deleteMax(){ root= deleteMax(root);//recursive call deleteMax() } private Node deleteMax(Node x){ if(x.right==null) return x.left; x.right=deleteMax(x.right); xN =size(x.right)+size(x.left)+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; Node t =x; x=min(t.right); x.right=deleteMin(t.right); x.left=t.left; } xN=size(x.left)+size(x.right)+1; return x; } }
