05.树表查找元素

目录介绍

1.基本思想
2.排序过程
3.代码实现
4.如何优化
5.复杂度
6.使用场景

1.基本思想

二叉排序树是最简单的树表查找算法，该算法需要利用待查找的数据，进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，然后再进行查找。
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
- 1>若左子树不空，则左子树上所有结点的键值均小于或等于它的根结点的键值。
- 2>若右子树不空，则右子树上所有结点的键值均大于或等于它的根结点的键值。
- 3>左、右子树也分别为二叉排序树。

2.排序过程

二叉排序树中序遍历
- 二叉排序树有不同的遍历方式，中序遍历的结果比较直观，是一个有序的序列。二叉树示例如下：
- image
- 二叉树上中序遍历的方式是：左节点、当前节点、右节点。该二叉树的遍历结果为：1、3、4、6、7、8、10、13、14。

3.代码实现

首先，要创建一个树的节点，节点中要有该节点储存的值，然后起左右子树。示例代码如下：

class BinaryTree{
    int value;
    BinaryTree left;
    BinaryTree right;
    public BinaryTree(int value){
        this.value = value;
    }
}

接下来就要创建二叉排序树，创建二叉排序树是一个递归的过程，需要将序列中的值一个一个添加到二叉树中。方便起见，可以利用序列中第一个元素作为根节点，再持续添加节点，示例代码如下：
```
int[] array = {35,76,6,22,16,49,49,98,46,9,40};
BinaryTree root = new BinaryTree(array[0]);
for(int i = 1; i < array.length; i++){
    createBST(root, array[i]);
}
```

具体创建树的过程，就是一个不断与根节点比较，然后添加到左侧、右侧或不添加的过程。也许有人会有疑问，为什么会存在不添加的情况？因为在二叉排序树中，不存在重复元素，有相等元素已经在树中时，直接忽略后续相等元素。示例代码如下：

public static void createBST(BinaryTree root, int element){
    BinaryTree newNode = new BinaryTree(element);
    if(element > root.value){
        if(root.right == null)
            root.right = newNode;
        else
            createBST(root.right, element);
    }else if(element < root.value){
        if(root.left == null)
            root.left = newNode;
        else
            createBST(root.left, element);
    }else{
        System.out.println("该节点" + element + "已存在");
        return;
    }
}

查找元素是否在树中的过程，就是一个二分查找的过程，不过查找的对象从左右子序列转换成了左右子树而已。示例代码如下：

public static void searchBST(BinaryTree root, int target, BinaryTree p){
    if(root == null){
        System.out.println("查找"+target+"失败");
    }else if(root.value == target){
        System.out.println("查找"+target+"成功");
    }else if(root.value >= target){
        searchBST(root.left, target, root);
    }else{ 
        searchBST(root.right, target, root);
    }
}

完整代码如下所示

public class Test {

	public static void main(String[] args) {
	   int[] array = {35,76,6,22,16,49,49,98,46,9,40};
        BinaryTree root = new BinaryTree(array[0]);
        for(int i = 1; i < array.length; i++){
            createBST(root, array[i]);
        }
        System.out.println("中序遍历结果：");
        midOrderPrint(root);
        System.out.println();
        searchBST(root, 22, null);
        searchBST(root, 100, null);
	}

	static class BinaryTree{
	    int value;
	    BinaryTree left;
	    BinaryTree right;
	    public BinaryTree(int value){
	        this.value = value;
	    }
	}
	
    /*创建二叉排序树*/
    public static void createBST(BinaryTree root, int element){
        BinaryTree newNode = new BinaryTree(element);
        if(element > root.value){
            if(root.right == null)
                root.right = newNode;
            else
                createBST(root.right, element);
        }else if(element < root.value){
            if(root.left == null)
                root.left = newNode;
            else
                createBST(root.left, element);
        }else{
            System.out.println("该节点" + element + "已存在");
            return;
        }
    }
    
    /*二叉树中查找元素*/
    public static void searchBST(BinaryTree root, int target, BinaryTree p){
        if(root == null){
            System.out.println("查找"+target+"失败");
        }else if(root.value == target){
            System.out.println("查找"+target+"成功");
        }else if(root.value >= target){
            searchBST(root.left, target, root);
        }else{ 
            searchBST(root.right, target, root);
        }
    }
    
    /*二叉树的中序遍历*/
    public static void midOrderPrint(BinaryTree rt){
        if(rt != null){
        	midOrderPrint(rt.left);
            System.out.print(rt.value + " ");
            midOrderPrint(rt.right);	
        }
    }
	
}

测试结果如下所示

该节点49已存在
中序遍历结果：
6 9 16 22 35 40 46 49 76 98 
查找22成功
查找100失败

4.如何优化

5.复杂度

普通二叉树
- 它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡。

6.使用场景

关于其他内容介绍

01.关于博客汇总链接

02.关于我的博客

我的个人站点：
github：https://github.com/yangchong211
知乎：https://www.zhihu.com/people/yang-chong-69-24/pins/posts
简书：http://www.jianshu.com/u/b7b2c6ed9284
csdn：http://my.csdn.net/m0_37700275
喜马拉雅听书：http://www.ximalaya.com/zhubo/71989305/
开源中国：https://my.oschina.net/zbj1618/blog
泡在网上的日子：http://www.jcodecraeer.com/member/content_list.php?channelid=1
邮箱：yangchong211@163.com
阿里云博客：https://yq.aliyun.com/users/article?spm=5176.100- 239.headeruserinfo.3.dT4bcV
segmentfault头条：https://segmentfault.com/u/xiangjianyu/articles