Java实现-二叉查找树（BST）的操作

编程技术  /  houtizong 发布于 3年前   79

see also:http://blog.csdn.net/jiqiren007/article/details/6534810

import java.util.LinkedList;import ljn.help.*;public class OperationsOnBinarySearchTree {/** * It shows the operations on Binary Search Tree. * see also: http://blog.csdn.net/jiqiren007/article/details/6534810 */private Node root;public static void main(String[] args) {int[] data={12,5,18,2,9,15,19,0,0,8,0,0,17,};  /*    12                                                                /   \                                                              5     18                                                           /   \   / \       2     9 15  19            /    \           8      17       */OperationsOnBinarySearchTree bst=new OperationsOnBinarySearchTree(data);bst.levelTraverse();bst.insert(13);bst.levelTraverse();bst.delete(13);bst.levelTraverse();bst.delete(12);bst.levelTraverse();bst.inOrder(bst.root);}public OperationsOnBinarySearchTree(int[] data){root=Helper.createTree(data);}public void delete(int dataDelete){if(root==null){return;}Node curNode=root;NodePair pair=findNodeAndParent(curNode,dataDelete);Node nodeDelete=pair.son;Node parent=pair.parent;if(nodeDelete==null){return;}if(isLeaf(nodeDelete)){if(parent.getLeft()==nodeDelete){parent.setLeft(null);}if(parent.getRight()==nodeDelete){parent.setRight(null);}}else{if( hasLeftOnly(nodeDelete)){if(parent.getLeft()==nodeDelete){parent.setLeft(nodeDelete.getLeft());}if(parent.getRight()==nodeDelete){parent.setRight(nodeDelete.getLeft());}}else if( hasRightOnly(nodeDelete)){if(parent.getLeft()==nodeDelete){parent.setLeft(nodeDelete.getRight());}if(parent.getRight()==nodeDelete){parent.setRight(nodeDelete.getRight());}}else{//has both left child and right child.Successor is in the min(curNode.getRight())NodePair tmpPair=min(nodeDelete.getRight());Node successor=tmpPair.son;Node sParent=tmpPair.parent;nodeDelete.setData(successor.getData());if(null==sParent){nodeDelete.setRight(null);}else{sParent.setLeft(successor.getRight());}}}}public NodePair findNodeAndParent(Node curNode,int data){if(curNode==null){return null;}Node parent=null;Node son=null;NodePair pair=null;while(curNode!=null){int curData=curNode.getData();if(curData==data){son=curNode;//when curNode.getData()==data,'parent' is null.Is it OK?break;}if(data<curData){parent=curNode;curNode=curNode.getLeft();}if(data>curData){parent=curNode;curNode=curNode.getRight();}}pair=new NodePair(son,parent);return pair;}public boolean hasLeftOnly(Node node){return node!=null&&node.getLeft()!=null&&node.getRight()==null;}public boolean hasRightOnly(Node node){return node!=null&&node.getRight()!=null&&node.getLeft()==null;}public boolean isLeaf(Node node){return node!=null&&node.getLeft()==null&&node.getRight()==null;}public NodePair min(Node curNode){if(curNode==null){return null;}Node parent=null;while(curNode.getLeft()!=null){//when 'curNode' has no left child,'curNode' is min,and its parent is null(ok?)parent=curNode;curNode=curNode.getLeft();}return new NodePair(curNode,parent);}//we don't get 'max''s parent node like 'min'public Node max(Node curNode){if(curNode==null){return null;}while(curNode.getRight()!=null){curNode=curNode.getRight();}return curNode;}public Node find(int target){if(root==null){//empty treereturn null;}else{return findHelp(root,target);}}public Node findHelp(Node curNode,int target){Node result=null;int curData=curNode.getData();if(target==curData){result=curNode;}if(target<curData){findHelp(curNode.getLeft(),target);}if(target>curData){findHelp(curNode.getRight(),target);}return result;}public void insert(int dataInsert){if(root==null){//the tree is emptyroot=new Node(dataInsert);}else{insertHelp(root,dataInsert);}}public void insertHelp(Node curNode,int dataInsert){Node nodeToInsert=new Node(dataInsert);int curData=curNode.getData();if(dataInsert<=curData){//insert into left treeNode left=curNode.getLeft();if(left==null){curNode.setLeft(nodeToInsert);}else{insertHelp(left,dataInsert);}}if(dataInsert>curData){//insert into right treeNode right=curNode.getRight();if(right==null){curNode.setRight(nodeToInsert);}else{insertHelp(right,dataInsert);}}}public void levelTraverse(){if(root==null){return;}Node node=root;LinkedList<Node> queue=new LinkedList<Node>();queue.addLast(node);while(!queue.isEmpty()){node=queue.removeFirst();System.out.print(node.getData()+" ");if(node.getLeft()!=null){queue.addLast(node.getLeft());}if(node.getRight()!=null){queue.addLast(node.getRight());}}System.out.println();}public void inOrder(Node curNode){if(curNode==null){return;}inOrder(curNode.getLeft());System.out.print(curNode.getData()+" ");inOrder(curNode.getRight());}//when deleting a node,we need the node and its parent.private static class NodePair{Node son;Node parent;NodePair(Node son,Node parent){this.son=son;this.parent=parent;}}}