首页 > 代码库 > 二叉查找树

二叉查找树

二叉查找(搜索)树(Binary Search Tree)又称二叉排序树(Binary Sort Tree),是基于二叉树,BST具有下列性质:
1、若左子树不空,则其左子树上的所有结点的值均小于根结点的值;
2、若右子树不空,则其右子树上的所有结点的值均大于根结点的值;
3、左、右子树也分别为二叉查找树。

                技术分享

结点类

 public class BinaryNode {  
    Integer data;  
    BinaryNode leftChild;  
    BinaryNode rightChild;  
  
    public BinaryNode() {  
    }  
  
    public BinaryNode(int data) {  
        leftChild = null;  
        rightChild = null;  
        this.data = data;  
    }  
  
    public BinaryNode(Integer data, BinaryNode leftChild, BinaryNode rightChild) {  
        this.data = data;  
        this.leftChild = leftChild;  
        this.rightChild = rightChild;  
    }  
二叉查找树实现类
 public class BinarySearchTree {  
    private BinaryNode root;  
    List<BinaryNode> nodeList = new LinkedList<BinaryNode>();  
  
    //相关方法 。。。。  

1、插入操作

 /** 
 * 非递归插入操作x的过程如下: 
 * 1、若b是空树,则直接将插入的结点作为根结点插入。 
 * 2、x等于b的根结点的数据的值,则直接返回,否则。 
 * 3、若x小于b的根结点的数据的值,则将x要插入的结点的位置改变为b的左子树,否则。 
 * 4、将x要出入的结点的位置改变为b的右子树。 
 */  
public boolean insert(Integer value) {  
    if (root == null) {  
        root = new BinaryNode(value);   //新构造一个二叉查找树  
        nodeList.add(root);  
  
    } else {  
        BinaryNode parent = null;  
        BinaryNode current = root;  
  
        while (current != null) {  
            //compareTo就是比较两个值,如果前者大于后者,返回1,等于返回0,小于返回-1  
            if (value.compareTo(current.data) == -1) {  
                parent = current;  
                current = current.leftChild;  
  
            } else if (value.compareTo(current.data) == 1) {  
                parent = current;  
                current = current.rightChild;  
                  
            } else  
                return false;  
        }  
  
        if (value.compareTo(parent.data) == -1)  
            parent.leftChild = new BinaryNode(value);  
        else  
            parent.rightChild = new BinaryNode(value);  
  
        nodeList.add(parent);  
    }  
    return true;  
}
 
递归插入:
 
 /** 
 * 递归插入: 得到的nodeList的size不是插入数据的大小!!! 
 */  
public BinaryNode recursiveInsert(Integer value) {  
    return recursiveInsert(value, this.root);  
}  
  
private BinaryNode recursiveInsert(Integer value, BinaryNode node) {  
    if (root == null)  
        root = new BinaryNode(value);   //新构造一个二叉查找树  
  
    if (node == null)  //如果是叶节点,则没有孩子  
        return new BinaryNode(value, null, null);  
  
    int result = value.compareTo(node.data);  
  
    /技术分享alue小于node.data返回-1  
    if (result == -1) {  
        node.leftChild = recursiveInsert(value, node.leftChild);  
  
    } else if (result == 1) {  
        node.rightChild = recursiveInsert(value, node.rightChild);  
    }  
  
    nodeList.add(node);  
    return node;  
 
测试:
 @Test  
public void test() {  
    BinarySearchTree tree = new BinarySearchTree();  
    BinarySearchTree tree1 = new BinarySearchTree();  
    int[] keys = new int[] { 8, 3, 10, 1, 6, 14, 4, 7, 13 };  
  
    for (int key:keys){  
        tree.insert(key);  
        tree1.recursiveInsert(key);  
    }  
  
    List<BinaryNode> list = tree.getBinarySearchTree();  
    List<BinaryNode> list1 = tree1.getBinarySearchTree();  
  
    System.out.println("非递归插入节点后,树的大小:"+ list.size());  
    System.out.println("递归插入节点后,树的大小:" + list1.size());  
非递归插入节点后,树的大小:9
递归插入节点后,树的大小:17

2、删除操作

对于二叉查找树的删除操作(这里根据值删除,而非结点)分三种情况:
不过在此之前,我们应该确保根据给定的值找到了要删除的结点,如若没找到该结点不会执行删除操作!这里暂时没有考虑
下面三种情况假设已经找到了要删除的结点。
1、如果结点为叶子结点(没有左、右子树),此时删除该结点不会玻化树的结构直接删除即可,并修改其父结点指向它的引用为null.如下图:
技术分享
2、如果其结点只包含左子树,或者右子树的话,此时直接删除该结点,并将其左子树或者右子树设置为其父结点的左子树或者右子树即可,此操作不会破坏树结构。

技术分享

 3、当结点的左右子树都不空的时候,一般的删除策略是用其右子树的最小数据(容易找到)代替要删除的结点数据并递归删除该结点(此时为null),因为右子树的最小结点不可能有左孩子,所以第二次删除较为容易。z的左子树和右子树均不空。找到z的后继y,因为y一定没有左子树,所以可以删除y,并让y的父亲节点成为y的右子树的父亲节点,并用y的值代替z的值.如图:
技术分享

实现代码:

 public void remove(Integer value) {  
    this.root = remove(value,root);  
}  
  
/** 
 * 递归删除: 
 * 
 * eg:添加的节点顺序为8,3,9.删除根结点,返回值则为3 
 * @return 返回值始终是最新的根节点!!! 
 */  
private BinaryNode remove(Integer value, BinaryNode node) {  
    if (node == null)  
        return null;  
  
    int result = value.compareTo(node.data);  
  
    //result<0:表示需要删除的节点在左子树  
    if (result == -1) {  
        node.leftChild = remove(value, node.leftChild);  
  
    } else if (result == 1) {//在右子树  
        node.rightChild = remove(value, node.rightChild);  
  
    } else if (node.leftChild != null && node.rightChild != null) { //结点的左右子树都不时候  
        //先找到需要删除的节点下,右子树中最小的节点并将它的值赋给需要删除的节点。  
        node.data = findMin(node.rightChild).data;  //找出右子树最小值(因为右子树中的节点的值一定大于根节点)  
        //删除前面找到的最小的节点  
        node.rightChild = remove(node.data, node.rightChild);  
  
    }else {  
        //找到需要删除的节点且节点下有一个子节点(左或者右)  
        node = (node.leftChild != null) ? node.leftChild : node.rightChild;  
    }  
  
    return node;  
 

3、查找

 /** 
 * 在二叉查找树中查找x的过程如下: 
 * 1、若二叉树是空树,则查找失败。 
 * 2、若x等于根结点的数据,则查找成功,否则。 
 * 3、若x小于根结点的数据,则递归查找其左子树,否则。 
 * 4、递归查找其右子树。 
 */  
public boolean find(Integer value) {  
    return contains(value, this.root);  
}  
  
private boolean contains(Integer value, BinaryNode node) {  
    if (node == null)  
        return false;  
  
    int result = value.compareTo(node.data); //-1,0,1  
    if (result == -1) {  
        return contains(value, node.leftChild); //递归查询左子树  
  
    }else if (result == 1) {  
        return contains(value, node.rightChild); //递归查询右子树  
  
    } else {  
        return true;  
    }  
 
4、其它相关方法
 //获取二叉查找树  
public List<BinaryNode> getBinarySearchTree() {  
    return nodeList;  
}  
  
/** 
 * 找出最小的值 
 * @return 返回最小值 
 */  
public Integer findMin() {  
    return findMin(root).data;  
}  
private BinaryNode findMin(BinaryNode node) {  
    if (node == null)  
        return null;  
    else if (node.leftChild == null) //如果左孩子没有,只返回根结点  
        return node;  
  
    return findMin(node.leftChild);  
}  
  
/** 
 * 找出最大的值 
 */  
public Integer findMax() {  
    return findMax(root).data;  
}  
private BinaryNode findMax(BinaryNode node) {  
    if (node ==null)  
        return null;  
    else if (node.rightChild == null)  
        return node;  
    else  
        return findMax(node.rightChild);  
}  
  
  
public void inOrderTraverse() {  
    inOrderTraverse(root);  
}  
  
/** 
 * 递归中序排序: 
 * 二叉查找树中序排序后的二叉查找树是有序的 
 */  
public void inOrderTraverse(BinaryNode node) {  
    if (node != null) {  
        inOrderTraverse(node.leftChild);  
        System.out.print(node.data + " ");  
        inOrderTraverse(node.rightChild);  
    }  

二叉查找树