二分搜索树-------2 查询与遍历

二分搜索树查询数据是否在当前树中，因为左右节点还是二分搜索树，我们可以使用递归来进行查询。

 
    public boolean contains(T entry){
        return contains(root, entry);
    }

    

    private boolean contains(Node node, T entry){
        
        if(node == null){
            return false;
        }

        if(entry.compareTo(node.entry) == 0){
            return true;
        }else if(entry.compareTo(node.entry) < 0){
            return contains(node.left, entry);
        }else{
            return contains(node.right, entry);
        }
    }

我们现在打印下二分搜索树中的内容

 @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        generateBSTString(root, 0, stringBuilder);
        return stringBuilder.toString();
    }

    private void generateBSTString(Node node, int depth, StringBuilder res){
        if(node == null){
            res.append(generateDepthString(depth) + " nulln");
            return;
        }
        res.append(generateDepthString(depth) +  node.entry + "n");
        generateBSTString(node.left, depth + 1, res);
        generateBSTString(node.right, depth + 1, res);
    }

    private String generateDepthString(int depth){
        StringBuilder stringBuilder = new StringBuilder();
        for(int i = 0; i < depth; i++){
            stringBuilder.append("-");
        }
        return stringBuilder.toString();
    }

有下面几点需要注意

• 先遍历根节点，再遍历左子树，再遍历右子树
• 使用了StringBuilder  

java高质量编程中介绍

String使用“+”连接字符串，会新生成一个字符串，那么效率就会很低。

StringBuilder和StringBuffer，会在原来的地址上进行扩展。所以效率要高于使用”+“。

StringBuilder用在单线程中，线程不安全

StringBuffer用在多线程当中，线程安全

前序遍历

 


    

    public void preOrder(){
        preOrder(root);
    }

    private void preOrder(Node node){
        if(node == null){
            return;
        }
        System.out.println(node.entry);
        preOrder(node.left);
        preOrder(node.right);
    }

中序遍历

    public void middleOrder(){
        middleOrder(root);
    }

    private void middleOrder(Node node){
        if(node == null){
            return;
        }
        middleOrder(node.left);
        System.out.println(node.entry);
        middleOrder(node.right);
    }

中序遍历出来的数据是由序的

后序遍历

 
    public void postOrder(){
        postOrder(root);
    }

    private void postOrder(Node node){
        if(node == null){
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.entry);
    }

gitee地址DateStructure: 数据接口demo