首页 > 代码库 > java二叉树
java二叉树
网上有关于二叉数的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 = http://www.mamicode.com/value;>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。