二叉树， 二叉查找树，二分查找算法

二叉树

二叉树跟树有区别，最大的一点就是：树的度没有限制，而二叉树最多则不能超过２个度

基础

二叉树由结点组成，结点包含的链接可以为空( null)或者指向其他结点，在二叉树中，每个结点只能有一个父结点(只有根节点例外)，　而且每个结点都只有左右两个链接，分别指向他们自己的左子节点和右子节点。

类型

  • 完全二叉树：若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
  • 满二叉树：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
  • 平衡二叉树：平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉排序树

二叉排序树又称为二叉查找树，它的一个显著特点是：它的每个结点都含有一个Comparable的键(以及相关联的值）。如果根节点存在左右节点，那么根节点的值一定比右节点小，比左节点大。
在二分查找树中，每个结点还包含了一个键和一个值。
从这里我们也可以看出二叉排序树的一个很好的优点就是它能够保持键的有序性，因此它可以作为实现有序符号表中众多方法的基础。
而根据它的这个特性，就可以归纳出一个二叉查找树的查找方法：二分查找树。
接下来，就先归纳二分查找法，之后再平缓过度到二分查找树的查找中。

二分查找

二分查找是一种查找效率较高的方法，但是对于被查找的数据有一定的先决条件：被查找的数据需要是有序的，即从从小到大或从大到小排列。

不足：查询快，但是插入和删除信息较慢

二分查找（Binary Search）思路
先确定待查记录所在的区间，然后逐步缩小区间直到找到或找不到该记录为止。

具体过程

  1. 先将关键字与 mid 指向的元素比较，如果相等则返回mid。
  2. 关键字小于 mid 指向的元素关键字，mid –, 在 [ low, mid ]区间中继续进行二分查找。
  3. 关键字大于mid 指向的元素关键字，mid ++, 在[ mid, high] 区间中继续进行二分查找。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//二分查找返回待查元素的数组下标  
public int search_Binary(STable st, KeyType key){  
    int low = 0;  
    int high = st.length - 1;  
    while(low <= high){  
        int mid = (low + high)/2;  
        if( key == st.elem[mid].key) {
            return mid;  
        } else if(key < st.elem[mid].key) { 
            high = mid - 1;  
        } else { 
	        low = mid + 1;
	    }  
    }  
    return -1;  
}

二叉查找树的使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public Value get(Key key){
        return get(root, key);
    }

    private Value get(Node x,Key key) {
        // 在以x为根结点的子树中查找并返回key所对应的值
        //　如果找不到则返回null
        if (x == null) {
            return null;
        }

        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            return get(x.left, key);
        } else if (cmp > 0) {
            return get(x.right, key);
        } else{
            return x.val;
        }
    }

    public void put(Key key, Value val) {
        // 查找key,找到则更新它的值，否则为他创建一个新的节点
        root = put(root, key, val);
    }

    private Node put(Node x, Key key, Value val) {
        // 如果key存在于以x为根节点的子树中则更新它的值
        //　否则将以key和val为键值对的新节点的新节点插入到该子树中
        if (x == null) {
            return new Node(key, val, 1);
        }

        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            x.left = put(x.left, key, val);
        } else if (cmp > 0) {
            x.right = put(x.right, key, val);
        } else {
            x.val = val;
        }

        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

在Node put()方法中，最后一句有个x.N = size(x.left) + size(x.right) + 1,这一句的作用是：
size()方法会将空链接的值当做0，这样就能够保证一下的公式对于二叉树的人以节点x总是成立。

size(x) = size(x.left) + size(x.right) + 1

插入

二分查找树的一个更重要的特性就是插入的实现难度和查找差不多，当查找一个不存在于书中的结点并结束于一条空链接时，需要做的就是将链接指向一个含有被查找的键的新节点即可。
在上面的代码中，上面代码中的put()方法即是这种功能。

二叉树的遍历

二叉树的遍历分为：

  • 前序遍历：根节点－左子树－右子树
  • 中序遍历：左子树－根节点－右子树
  • 后序遍历：左子树－右子树－根节点
  • 按层遍历：从根节点到下，一层层的从左到右依次遍历

这是我画的一个简单使示例图，照着遍历的方法，结果就为：

前序遍历：　ABCDEFG
中序遍历：　CBDAEGF
后序遍历：　CDBGFEA
按层遍历：　ABECDFG

总结到这里，又想起之前发的一篇文章, Python学习笔记(四) 多重继承及内部算法解析, 里面也总结了一下深度优先算法，广度优先算法及Python在多重继承同名父类方法选择上的C3算法。这里就不做过多的介绍了，传送门在这。