数据结构——二叉树

1.二分查找和判定树：

二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树(Decision Tree)或比较树(Comparison Tree)。时间复杂度为O(logN)。

java实现代码：

    public static int commonBinarySearch(int[] arr,int key){
        int low = 0;
        int high = arr.length - 1;
        int middle = 0;         //定义middle
        
        if(key < arr[low] || key > arr[high] || low > high){
            return -1;              
        }
        
        while(low <= high){
            middle = (low + high) / 2;
            if(arr[middle] > key){
                //比关键字大则关键字在左区域
                high = middle - 1;
            }else if(arr[middle] < key){
                //比关键字小则关键字在右区域
                low = middle + 1;
            }else{
                return middle;
            }
        }
        
        return -1;      //最后仍然没有找到，则返回-1
    }

2.二叉树

2.1 特殊的二叉树

• 1.斜树：所有的结点都只有左子树（左斜树），或者只有右子树（右斜树）。
• 2.满二叉树：所有的分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上，这样就是满二叉树
• 3.完全二叉树：对一棵具有n个结点的二叉树按层序排号，如果编号为i的结点与同样深度的满二叉树编号为i结点在二叉树中位置完全相同，就是完全二叉树。
  特点：
  （1）叶子结点只能出现在最下一层（满二叉树继承而来）
  （2）最下层叶子结点一定集中在左 部连续位置。
  （2）倒数第二层，如有叶子节点，一定出现在右部连续位置。
  （4）同样结点树的二叉树，完全二叉树的深度最小（满二叉树也是对的）。
  image.png

2.2普通二叉树的性质

重点：对于任何一棵非空的二叉树,如果叶节点个数为n0，度数为2的节点个数为n2，则有: n0 = n2 + 1

2.3 二叉树遍历

二叉树的核心是把二维结构变成一维序列。

• 前序遍历基本思想：
  1.先访问根结点
  2.再先序遍历左子树
  3.最后再先序遍历右子树

image.png

如上图：前序遍历的结果是：12457836

java实现的方式：

// 前序遍历的递归实现
    public void preOrderTraverse(TreeNode node) {
        if (node == null)
            return;
        // 先根节点
        System.out.println(node.val);
        // 再左孩子
        preOrderTraverse(node.left);
        // 后右孩子
        preOrderTraverse(node.right);
    }

• 中序遍历
  1.先中序遍历左子树
  2.然后再访问根结点
  3.最后再中序遍历右子树

  
  image.png

// 中序遍历的递归实现
    public void midOrderTraverse(TreeNode node) {
        if (node == null)
            return;
        // 先左孩子
        midOrderTraverse(node.left);
        // 再根节点
        System.out.println(node.val);
        // 后右孩子
        midOrderTraverse(node.right);
    }

• 后序遍历
  1.先后序遍历左子树
  2.然后再后序遍历右子树
  3.最后再访问根结点

  
  image.png

// 后序遍历的递归实现
    public void endOrderTraverse(TreeNode node) {
        if (node == null)
            return;
        // 先左孩子
        endOrderTraverse(node.left);
        // 再右孩子
        endOrderTraverse(node.right);
       // 后根节点
        System.out.println(node.val);
    }

2.3 平衡二叉树(AVL树)

2.3.1 定义

平衡二叉树(AVL树)是一种二叉排序树，其中每个结点的左子树和右子树的高度差至多等于1

2.3.2 二叉树平衡树插入。

插入分为四种情况：
（1） 在结点X的左孩子结点的左子树中插入元素

图片.png

（2）在结点X的左孩子结点的右子树中插入元素

图片.png

（3）在结点X的右孩子结点的左子树中插入元素

图片.png

（4） 在结点X的右孩子结点的右子树中插入元素

图片.png

参考文档:java数据结构与算法之平衡二叉树(AVL树)的设计与实现

3.Huffman树（最优二叉树）

3.2 Huffman树的定义：

Huffman树是一种特殊结构的二叉树，由Huffman树设计的二进制前缀编码。
要介绍Huffman树，首先我们需要知道什么是树的带权路径长度，它指的是所有叶子节点的带权路径长度之和。

有了如上的概念，对于Huffman树，其定义为：

给定n权值作为n个叶子节点，构造一棵二叉树，若这棵二叉树的带权路径长度达到最小，则称这样的二叉树为最优二叉树，也称为Huffman树。

3.2 Huffman树的构造：

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，哈夫曼树的构造规则为：

1. 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
2. 在森林中选出根结点的权值最小的两棵树进行合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
3. 从森林中删除选取的两棵树，并将新树加入森林；
4. 重复(02)、(03)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

3.3 Huffman树Java实现：

public Huffman(int a[]) {
    HuffmanNode parent = null;
    MinHeap heap;

    // 建立数组a对应的最小堆
    heap = new MinHeap(a);

    for(int i=0; i<a.length-1; i++) {   
        HuffmanNode left = heap.dumpFromMinimum();  // 最小节点是左孩子
        HuffmanNode right = heap.dumpFromMinimum(); // 其次才是右孩子

        // 新建parent节点，左右孩子分别是left/right；
        // parent的大小是左右孩子之和
        parent = new HuffmanNode(left.key+right.key, left, right, null);
        left.parent = parent;
        right.parent = parent;

        // 将parent节点数据拷贝到"最小堆"中
        heap.insert(parent);
    }

    mRoot = parent;

    // 销毁最小堆
    heap.destroy();
}

首先创建最小堆，然后进入for循环。
每次循环时：
(1) 首先，将最小堆中的最小节点拷贝一份并赋值给left，然后重塑最小堆(将最小节点和后面的节点交换位置，接着将"交换位置后的最小节点"之前的全部元素重新构造成最小堆)；
(2) 接着，再将最小堆中的最小节点拷贝一份并将其赋值right，然后再次重塑最小堆；
(3) 然后，新建节点parent，并将它作为left和right的父节点；
(4) 接着，将parent的数据复制给最小堆中的指定节点。