什么是二叉排序樹

二叉排序樹是二叉樹的基礎(chǔ)上多出來一些性質(zhì)而已。
性質(zhì)：
<1>若它的左子樹不空，則左子樹上的所有關(guān)鍵字的值都小于根關(guān)鍵字的值。
<2>若它的右子樹不空，則右子樹上的所有關(guān)鍵字的值都大于根關(guān)鍵字的值。
<3>左右子樹又各是一棵二叉排序樹。

基于二叉排序樹的性質(zhì)我們可以得到的一點是，如果我們輸出二叉排序樹的中序遍歷序列，則這個序列的值是依次遞增的順序。

二叉樹存儲結(jié)構(gòu)

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;  
    }  
}  

二叉排序樹構(gòu)造

    /*構(gòu)造二叉排序樹  
     * 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。如果當前插入的點小于根節(jié)點，那么就將其放入左邊的位置。如果其左邊還有值就遞歸，找到合適的位置插入。右邊同理。

排序二叉樹結(jié)構(gòu)圖：

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:為遍歷二叉排序樹的開始節(jié)點  
     * 中序方式  
     * */  
    public static void queryBSTNodeByOrder(BSTNode bstNode) {  
        if(bstNode !=null){  
            queryBSTNodeByOrder(bstNode.getLchild());  
            System.out.println("值："+bstNode.getData());  
            queryBSTNodeByOrder(bstNode.getRchild());  
        }else{  
            return;  
        }  
    }  

結(jié)果：如下圖，驗證了之前得出的結(jié)論，二叉排序樹的中序遍歷可以實現(xiàn)序列的依次遞增。

20170527175213531.png

二叉排序樹查找值

    /*二叉排序樹查找值  
     * bstNode:查找根節(jié)點  
     * 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());  
}