网上有关于二叉数的java实现http://blog.csdn.net/skylinesky/article/details/6611442
多数案例都没有键值,有键值的也全是整型。我用java实现了一个可以任何对象为键的二叉数
package Tree; import java.io.IOException; public class Tree<I extends Comparable<I> ,V> { @SuppressWarnings("rawtypes") private Node root; @SuppressWarnings("unchecked") public Node<I, V> getRoot() { return root; } public void setRoot(Node<I, V> root) { this.root = root; } //向树添加节点 @SuppressWarnings({ "unchecked" }) public void add(I index,V value){ if(root == null){ root = new Node<I, V>(index,value); System.out.println(root); }else{ Node<I, V> current = root; Node<I, V> parent = null; while(true){ parent = current; int result = index.compareTo(current.getIndex()); if(result < 0){ current = current.getLeft(); if(current == null){ current = new Node<I, V>(index,value); parent.setLeft(current); return ; } }else{ current = current.getRight(); if(current == null){ current = new Node<I, V>(index,value); parent.setRight(current); return ; } } } } } //查找 @SuppressWarnings("unchecked") public Node<I, V> find(I index){ Node<I, V> current = root; int result = index.compareTo(current.getIndex()); while(result != 0){ if(result < 0){ current = current.getLeft(); }else { current = current.getRight(); } if(current == null){ return null; } result = index.compareTo(current.getIndex()); } return current; } //中序遍历 public void centerTraversal(Node<I, V> node){ if(node != null){ centerTraversal(node.getLeft()); System.out.println(node); centerTraversal(node.getRight()); } } //前序遍历 public void leftTraversal(Node<I, V> node){ if(node != null){ System.out.println(node); centerTraversal(node.getLeft()); centerTraversal(node.getRight()); } } //后序遍历 public void rightTraversal(Node<I, V> node){ if(node != null){ System.out.println(node); centerTraversal(node.getLeft()); centerTraversal(node.getRight()); } } @SuppressWarnings("unchecked") public void delete(I index){ Node<I, V> current = root; boolean isLeft = true; Node<I, V> parent = null; int result = index.compareTo(current.getIndex()); //找到要删除的结点 while(result != 0){ parent = current; System.out.println(current.getIndex()); if(result < 0){ current = current.getLeft(); isLeft = true; }else { current = current.getRight(); isLeft = false; } if(current == null){ throw new RuntimeException(" \"" + index + "\" 没有这个节点"); } result = index.compareTo(current.getIndex()); } //这个要删除的节点没有子结点 if(current.getLeft() == null && current.getRight() == null){ if(current == root){ root = null; }else{ if(isLeft){ parent.setLeft(null); }else{ parent.setLeft(null); } } }else if(current.getRight() == null){ //只有左子结点 if(current == root){ root = root.getLeft(); }else{ if(isLeft){ parent.setLeft(current.getLeft()); }else{ parent.setRight(current.getLeft()); } } //只有右子结点 }else if(current.getLeft() == null){ if(current == root){ root = root.getRight(); }else{ if(isLeft){ parent.setLeft(current.getRight()); }else{ parent.setRight(current.getRight()); } } }else{ //左右子节点都有的情况下, Node<I,V> follow = current; Node<I,V> followParent = follow; Node<I,V> followCurrent = follow.getRight(); if(followCurrent.getLeft() == null){ if(isLeft){ parent.setLeft(current.getRight()); }else{ parent.setRight(current.getRight()); } current.getRight().setLeft(current.getLeft()); }else{ while(followCurrent != null){ followParent = follow; follow = followCurrent; followCurrent = followCurrent.getLeft(); } followParent.setLeft(follow.getRight()); if(isLeft){ parent.setLeft(follow); }else{ parent.setRight(follow); } follow.setLeft(current.getLeft()); follow.setRight(current.getRight()); } } } public static void main(String[] args) throws IOException{ Tree<Integer,Double> tree = new Tree<Integer,Double>(); tree.add(50, 1.5); tree.add(25, 1.2); tree.add(75, 1.7); tree.add(12, 1.5); tree.add(37, 1.2); tree.add(43, 1.7); tree.add(30, 1.5); tree.add(33, 1.2); tree.add(87, 1.7); tree.add(93, 1.5); tree.add(97, 1.5); tree.leftTraversal(tree.getRoot()); System.out.println(); tree.delete(30); tree.centerTraversal(tree.getRoot()); System.out.println(); tree.rightTraversal(tree.getRoot()); System.out.println(); } }
package Tree; public class Node<I extends Comparable<I> ,V> { //节点的关键字 private I index; //节点的值 private V value; private Node<I,V> left; private Node<I,V> right; public Node(){ } public Node(I index,V value){ this(index,value,null,null); } public Node(I index,V value,Node<I,V> left,Node<I,V> right){ this.index = index; this.value = value; this.left = left; this.right = right; } public I getIndex() { return index; } public void setIndex(I index) { this.index = index; } public V getValue() { return value; } public void setValue(V value) { this.value = value; } public Node<I, V> getLeft() { return left; } public void setLeft(Node<I, V> left) { this.left = left; } public Node<I, V> getRight() { return right; } public void setRight(Node<I, V> right) { this.right = right; } @Override public String toString() { StringBuffer sb = new StringBuffer(); sb.append(" { left:").append("[index:").append(left!=null?left.index:"null").append(" , value:").append(left!=null?left.value:"null").append("] } ") .append(" { self:").append("[index:").append(index).append(", value:").append(value).append("] } ") .append(" { right:").append("[index:").append(right!=null?right.index:"null").append(", value:").append(right!=null?right.value:"null").append("] } "); return sb.toString(); } public static void main(String args[]){ Node<String,String> root = new Node<String,String>(); root.index = "父节点"; root.value = "啊哈"; Node<String,String> left = new Node<String,String>(); left.index = "左节点"; left.value = "你妹"; Node<String,String> right = new Node<String,String>(); right.index = "右节点"; right.value = "我妹"; //root.left = left; //root.right = right; System.out.println(root); } }