二叉树

package muke.binarytree; /** * Created by jc6a on 2017/8/31. */ public class Node<T extends Comparable> implements Comparable<Node<T>>{ private T data; private Node leftNode; private Node righNode; public Node( T t ){ this(t,null,null); } public Node(T t,Node<T> leftNode,Node<T> rightNode){ this.data = t; this.leftNode = leftNode; this.righNode = rightNode; } @Override public int compareTo(Node<T> o) { return data.compareTo(o.data); } public T getData() { return data; } public void setData(T data) { this.data = data; } public Node getLeftNode() { return leftNode; } public void setLeftNode(Node leftNode) { this.leftNode = leftNode; } public Node getRighNode() { return righNode; } public void setRighNode(Node righNode) { this.righNode = righNode; } @Override public String toString() { return "Node{" + "data=" + data + ", leftNode=" + leftNode + ", righNode=" + righNode + '}'; } }

package muke.binarytree; /** * Created by jc6a on 2017/8/31. */ public class Tree { public Node root; public <T> Node search(T key){ if(null == root) return null; Node node = root; while(null!= node){ int compareResult = node.getData().compareTo(key); if(compareResult>0){ node = node.getRighNode(); }else if(compareResult<0){ node = node.getLeftNode(); }else{ break; } } return node; } public <T extends Comparable> void insert(T key){ Node node = new Node(key); if(root == null){ root = node; }else{ Node currentNode = root; boolean isLeftNode = true; while(currentNode != null){ int compareResult = currentNode.compareTo(node); if(compareResult>0){ isLeftNode = true; if(currentNode.getLeftNode()==null) break; currentNode = currentNode.getLeftNode(); }else if(compareResult<0){ isLeftNode = false; if(currentNode.getRighNode()==null) break; currentNode = currentNode.getRighNode(); }else{ return; } } if(isLeftNode){ currentNode.setLeftNode(node); }else{ currentNode.setRighNode(node); } } } public <T extends Comparable> boolean delete(T key){ Node currentNode = root; Node parent = root; Node node = new Node(key); int compareResult; boolean isLeftNode = true; while(null!=currentNode&&(compareResult = currentNode.compareTo(node))!=0){ parent = currentNode; if(compareResult>0){ currentNode = currentNode.getLeftNode(); }else{ isLeftNode = false; currentNode = currentNode.getRighNode(); } } if(null == currentNode) return false; //要删除的节点没有子节点 if(currentNode.getLeftNode() == null && currentNode.getRighNode() == null){ if(currentNode == root){ root = null; }else if(isLeftNode){ parent.setLeftNode(null); }else{ parent.setRighNode(null); } } //要删除的节点只有右节点 else if(currentNode.getLeftNode() == null){ if(currentNode == root){ root = currentNode.getRighNode(); }else if(isLeftNode){ parent.setLeftNode(currentNode.getRighNode()); }else{ parent.setRighNode(currentNode.getRighNode()); } } //要删除的节点只有左节点 else if(currentNode.getRighNode() == null){ if(currentNode == root){ root = currentNode.getLeftNode(); }else if(isLeftNode){ parent.setLeftNode(currentNode.getLeftNode()); }else{ parent.setRighNode(currentNode.getLeftNode()); } } //要删除的节点有两个节点 else{ Node successor = findSuccessor(currentNode); if(currentNode == root){ root = successor; }else if(isLeftNode){ parent.setLeftNode(successor); }else { parent.setRighNode(successor); } successor.setLeftNode(currentNode.getLeftNode()); } return true; } public Node findSuccessor(Node node){ Node parent = node; Node successsor = node; Node current = node.getRighNode(); while(current!=null){ parent = successsor; successsor = current; current = current.getLeftNode(); } if(successsor != node.getRighNode()){ parent.setLeftNode(successsor.getRighNode()); successsor.setRighNode(node.getRighNode()); } return successsor; } public static void main(String[] args) { Tree tree = new Tree(); tree.insert(6); tree.insert(2); tree.insert(4); tree.insert(3); tree.insert(1); tree.insert(5); tree.insert(8); System.out.println(tree.root); tree.delete(2); System.out.println(tree.root); // 6 // / \ // 2 8 // / \ // 1 4 // / \ // 3 5 } }