二叉查找树的特点:
1.若左子树非空，则左子树上所有结点的数据元素值均小于根结点的数据元素值。
2.若右子树非空，则右子树上所有的节点的数据元素值均大于或等于根结点的数据元素的值。
3.左右子树也均为二叉查找树
java 实现的二叉查找树:
BiTreeNode.java
public class BiTreeNodeBiSearchTree.java> { private BiTreeNode leftChild; private BiTreeNode rightChild; private BiTreeNode parent; private T data; public BiTreeNode() { leftChild = null; rightChild = null; } public BiTreeNode(T data){ this.data = data; leftChild = null; rightChild = null; } BiTreeNode(T data,BiTreeNode leftChild,BiTreeNode rightChild){ this.data = data; this.leftChild = leftChild; this.rightChild = rightChild; } public BiTreeNode getLeftChild() { return leftChild; } public void setLeftChild(BiTreeNode leftChild) { this.leftChild = leftChild; } public BiTreeNode getRightChild() { return rightChild; } public void setRightChild(BiTreeNode rightChild) { this.rightChild = rightChild; } public BiTreeNode getParent() { return parent; } public void setParent(BiTreeNode parent) { this.parent = parent; } public T getData() { return data; } public void setData(T data) { this.data = data; }}
public class BiSearchTree> { private BiTreeNode root; //中序遍历 private void inOrder(BiTreeNode t,Visit vs){ if( t != null ){ inOrder(t.getLeftChild(),vs); vs.print(t.getData()); inOrder(t.getRightChild(),vs); } } //前序遍历 private void preOrder(BiTreeNode t, Visit vs){ if(t!=null){ vs.print(t.getData()); preOrder(t.getLeftChild(),vs); preOrder(t.getRightChild(),vs); } } public BiSearchTree() { root = null; } public BiTreeNode getRoot() { return root; } public void setRoot(BiTreeNode root) { this.root = root; } public void inOrder(Visit vs){ inOrder(root,vs); } public void preOrder(Visit vs){ preOrder(root,vs); } //取得左孩子 public BiTreeNode getLeft(BiTreeNode current){ return current != null ?current.getLeftChild():null; } //取得右孩子 public BiTreeNode getRight(BiTreeNode current){ return current != null ? current.getRightChild() : null; } //查找 public BiTreeNode find(T data){ if(root !=null){ BiTreeNode temp = root; while(temp!=null){ if(temp.getData().compareTo(data)==0) return temp; if((temp.getData().compareTo(data))<0){ temp = temp.getRightChild(); } else { temp = temp.getLeftChild(); } } } return null; } public void insert(BiTreeNode ptr,T data){ //如果插入的值小于当前节点的值,就在左子树上面插入 if(data.compareTo(ptr.getData())<0){ //如果左字树为空直接把该结点作为当前节点的左孩子，否则递归到左孩子 if(ptr.getLeftChild() == null){ BiTreeNode temp = new BiTreeNode (data); temp.setParent(ptr); ptr.setLeftChild(temp); }else{ insert(ptr.getLeftChild(),data); } }else if(data.compareTo(ptr.getData())>0){ if(ptr.getRightChild() == null){ BiTreeNode temp = new BiTreeNode (data); temp.setParent(ptr); ptr.setRightChild(temp); }else{ insert(ptr.getRightChild(),data); } } } /** * 分四种情况: * 1.删除节点没有孩子节点 * 2.删除节点只有左边孩子 * 3.删除结点只有右孩子 * 4.删除结点有左右结点 */ public void delete(BiTreeNode ptr,T data){ if(ptr != null){ if(data.compareTo(ptr.getData())<0){ delete(ptr.getLeftChild(),data); }else if(data.compareTo(ptr.getData())>0){ delete(ptr.getRightChild(),data); }else if(ptr.getLeftChild() != null && ptr.getRightChild() !=null){//删除结点有左右结点 BiTreeNode rightMin; //右子树最小的结点 rightMin = ptr.getRightChild(); while(rightMin.getLeftChild()!=null){ rightMin = rightMin.getLeftChild(); } ptr.setData(rightMin.getData()); delete(ptr.getRightChild(),rightMin.getData()); }else{ //左孩子为空，右孩子不为空 if(ptr.getLeftChild() == null &&ptr.getRightChild() !=null){//删除结点只有右孩子 ptr.getParent().setRightChild(ptr.getRightChild()); ptr.getRightChild().setParent(ptr.getParent()); } else if(ptr.getLeftChild() != null && ptr.getRightChild() == null){//删除节点只有左边孩子 ptr.getParent().setLeftChild(ptr.getLeftChild()); ptr.getLeftChild().setParent(ptr.getParent()); }else{//删除节点没有孩子节点 BiTreeNode p = ptr.getParent(); if(p.getLeftChild() == ptr){ p.setLeftChild(null); }else{ p.setRightChild(null); } } } } }}
测试:
public class BiSearchTreeTest { public static void main(String[] args) { BiSearchTree searchTree = new BiSearchTree (); int a[] = {4,5,7,2,1,9,8,11,3}; Visit vs = new Visit(); BiTreeNode root = new BiTreeNode (a[0]); for (int i = 1; i < a.length; i++) { searchTree.insert(root, a[i]); } searchTree.setRoot(root); System.out.println("中序遍历:"); searchTree.inOrder(vs); searchTree.delete(searchTree.getRoot(), 4); System.out.println("删除4后的中序遍历:"); searchTree.inOrder(vs); }} public class Visit { public void print(Object o){ System.out.print(o+" "); }}