二叉排序树算法

什么是二叉排序树

二叉排序树是二叉树的基础上多出来一些性质而已。
性质：
<1>若它的左子树不空，则左子树上的所有关键字的值都小于根关键字的值。
<2>若它的右子树不空，则右子树上的所有关键字的值都大于根关键字的值。
<3>左右子树又各是一棵二叉排序树。

基于二叉排序树的性质我们可以得到的一点是，如果我们输出二叉排序树的中序遍历序列，则这个序列的值是依次递增的顺序。

二叉树存储结构

class BSTNode{  
    private Integer data=;  
    private BSTNode lchild=;  
    private BSTNode rchild=;  
    public BSTNode() {}  
    public BSTNode(Integer data) {  
        this.data = data;  
    }  
    public Integer getData() {  
        return data;  
    }  
    public void setData(Integer data) {  
        this.data = data;  
    }  
    public BSTNode getLchild() {  
        return lchild;  
    }  
    public void setLchild(BSTNode lchild) {  
        this.lchild = lchild;  
    }  
    public BSTNode getRchild() {  
        return rchild;  
    }  
    public void setRchild(BSTNode rchild) {  
        this.rchild = rchild;  
    }  
}  

二叉排序树构造

    /*构造二叉排序树  
     * bstNode:插入的点    root:二叉排序树的定点  
     * */  
    public static Integer sortBSTNode(BSTNode bstNode,BSTNode root){  
        if(bstNode ==null){  
            bstNode =new BSTNode();  
            bstNode.setLchild(null);  
            bstNode.setRchild(null);  
            return 9999;  
        }else if(root.getData()>bstNode.getData()){  
            if(root.getLchild()==null){  
                root.setLchild(bstNode);  
            }else{  
                return sortBSTNode(bstNode,root.getLchild());  
            }  
              
        }else{  
            if(root.getRchild() ==null){  
                root.setRchild(bstNode);  
            }else{  
                return sortBSTNode(bstNode,root.getRchild());  
            }  
        }  
        return 9999;  
    }  

解释：采用递归的方式，逐点插入。如果当前插入的点为空，或者插入的操作失败，那么返回值为9999。如果当前插入的点小于根节点，那么就将其放入左边的位置。如果其左边还有值就递归，找到合适的位置插入。右边同理。

排序二叉树结构图：

20170528124423353.jpg

前序遍历的方式遍历二叉树的值（和前序遍历二叉树一样）

    /*递归方式遍历二叉排序树  
     * 前序方式  
     * */  
    public static void queryBSTNodeByPre(BSTNode bstNode){  
        if(bstNode !=null){  
            System.out.println("值："+bstNode.getData());  
            queryBSTNodeByPre(bstNode.getLchild());  
            queryBSTNodeByPre(bstNode.getRchild());  
        }else{  
            return;  
        }  
    }  

中序遍历的方式遍历二叉树的值（和中序遍历二叉树一样）

    /*递归方式遍历二叉排序树  
     * bstNod:为遍历二叉排序树的开始节点  
     * 中序方式  
     * */  
    public static void queryBSTNodeByOrder(BSTNode bstNode) {  
        if(bstNode !=null){  
            queryBSTNodeByOrder(bstNode.getLchild());  
            System.out.println("值："+bstNode.getData());  
            queryBSTNodeByOrder(bstNode.getRchild());  
        }else{  
            return;  
        }  
    }  

结果：如下图，验证了之前得出的结论，二叉排序树的中序遍历可以实现序列的依次递增。

20170527175213531.png

二叉排序树查找值

    /*二叉排序树查找值  
     * bstNode:查找根节点  
     * key:要查找的值  
     * */  
    public static BSTNode queryBSTkey(BSTNode bstNode,Integer key){  
        if(key ==null){  
            return null;  
        }  
        while(bstNode !=null){  
            if(bstNode.getData() ==key){  
                return bstNode;  
            }else if(bstNode.getData() >key){  
                bstNode =bstNode.getLchild();  
            }else{  
                bstNode =bstNode.getRchild();  
            }  
        }  
        return null;  
    }  

二叉排序树测试

public static void main(String[] args) {  
        Integer[] arr ={8,1,6,7,9,2,5,3};  
    List<BSTNode> list =new ArrayList<BSTNode>();  
    for(int i=0;i<arr.length;i++){  
        list.add(new BSTNode(arr[i]));  
    }  
    BSTNode root =list.get(0);  
    for(int i=1;i<list.size();i++){  
        sortBSTNode(list.get(i),root);  
    }  
    //queryBSTNodeByOrder(root);  
    //queryBSTNodeByPre(root);  
    System.out.println(queryBSTkey(root,5).getLchild().getData());  
}