二叉树 | Wafer's Note

1. 二叉树的定义

二叉树是一种每个节点最多只能有两个子节点的树

树是一种没有环的连通图

在最顶层的节点叫做根节点
没有子节点的节点叫叶节点，有子节点的节点叫做内部节点

2. 二叉树的类型

2.1 满二叉树

国内定义：除了最后一层没有子节点以外，其他每一层的节点都有两个子节点

节点数和深度满足如下关系：

N_{leaf} = 2^{h} - 1

国外定义 : 只有叶节点和度为 2 的节点的树就叫满二叉树

（在国内一般用国内定义（笑））

2.2 完全二叉树

至多只有最下面的两层上的节点的度数可以小于 2，并且最下层的节点都在最左边的若干位置上。

满二叉树：

完全二叉树:

3. 实现

3.1 数组实现

这种实现方法就是按照完全二叉树的形式将节点置于相应的数组单元之中。
所以，如果一个节点的索引是 $k$ ，那么，
它的父亲的索引是 $\lfloor k \rfloor$ ；
它的左子结点的索引是 $2k$ ，右子结点的索引是 $2k + 1$

这种实现方式最适合于完全二叉树，如果一个不完全的二叉树使用这种方法实现，会浪费许多的空间。

3.2 链表实现

相对于数组来说，使用链表实现能节省更多的空间。它的节点由三部分组成：
数据域，左子结点指针，和右子结点指针

Node:

leftChild

data

rightChild

4. 遍历算法

一般来说，有三种方法可以遍历一个二叉树，它们是：

先序遍历（ $DLR$ ）
中序遍历（ $LDR$ ）
后序遍历（ $LRD$ ）

它们都属于深度优先遍历方法
注意，只有三种方法的前提是左子结点比右子结点大，如果抛弃这个前提，则有至多六种方法

4.1 深度优先遍历

所谓的深度优先，指的是，优先搜索子孙节点，而不是优先搜索兄弟节点

4.1.1 先序遍历

访问根节点
递归访问左子节点
递归访问右子结点

4.1.2 中序遍历

递归访问左子结点
访问根节点
递归访问右子结点

4.1.3 后序遍历

递归访问左子结点
递归访问右子结点
访问根节点

4.2 广度优先

所谓的广度优先，就是优先访问兄弟节点，而不是子孙节点
直到当前层访问完成前，都不进入下一层进行遍历

一般使用队列来实现这种访问策略


interface Visitable<Item> {
    void onVisit(Item item);
}

class BreadthFirst {
    Visitable<Node> visiter;
    ....
    void breadFirstTraversal(Node root) {
        Queue q = new Queue();
        q.enQueue(root);
        while (!q.isEmpty()) {
            Node node = q.deQueue();
            visiter.onVisit(node);
            if(node.lChild != null) {
                q.enQueue(node.lChild);
            }
            if(node.rChild != null) {
                q.enQueue(node.rChild);
            }
        }
    }
}

5. 线索二叉树

线索二叉树指的是，当我们使用链表来实现一个二叉树时，
使用一些节点的空的指针域来储存相应遍历策略的前一个或者后一个节点。

从而起到方便遍历和提高空间利用率的作用。

需要注意的是，一个线索二叉树是和它采用的访问策略相关的，同一个二叉树采用不同的访问策略，其对应的线索二叉树也会不同。

具体来说，对于两个子节点都为空的情况下，二叉树的左子树指向其遍历的前驱，右子树指向其遍历的后继。

5.0 调整数据结构

为了建立一个线索二叉树，我们需要对节点的数据域进行一些调整。

增加了两个指示是否是子节点的 flag

The Threaded Binary Tree Node:

boolean leftFlag

leftChild

Data

rightChild

boolean rightFlag

5.1 二叉树的中序线索化

二叉树的线索化，实际上就是在遍历过程中，修改空链接的过程。

所以二叉树的线索化是和其遍历策略相关的。

对于中序遍历而言，就是在中序遍历过程中，将它的空链接给修改的过程。

public class ThreadedBinaryTree {
    Data data;
    ThreadedBinaryTree leftChild;
    boolean leftFlag;
    ThreadedBinaryTree rightChild;
    boolean rightFlag;
}

// 使用全局变量存储前驱
ThreadedBinaryTree pre;

public void threadingBinaryTree(ThreadedBinaryTree root) {
    if (root == null)
        return;

    threadingBinaryTree(root.leftChild);

    if (root.leftChild == null) {
        root.leftFlag = true;
        root.leftChild = pre;
    }

    if (pre.rightChild == null) {
        pre.rightFlag = true;
        pre.rightChild = root; // 指向后继，即当前节点
    }

    pre = root;

    threadingBinaryTree(root.rightChild);
}

上面对于右子节点处理的时候要用 pre 的原因是：右子节点指向后继，而后继是需要访问到下一个节点才能获取得到的；

所以对右子节点的处理才会使用 pre，是因为当前节点就是 pre 的后继。

6. 二叉树和森林

6.1 森林的定义

森林是由多个独立的二叉树组成的数据结构

我们可以通过连接他们的根节点来构造一棵大型的树

6.2 森林的表示法

为了能在物理上表示一个森林，我们首先会将其变成一棵大型的树，仅仅将它们的根节点连接起来即可。

6.2.1 孩子兄弟表示法

首先这个适用于链表实现的树。
森林的节点由三部分组成：

数据域
左子结点指针
右边的兄弟节点指针

Node:

leftChild

Data

brother

既然，这个节点含有的域和一个二叉树的节点含有的域的数目和类型都是相同的。

那么我们就可以在物理结构上将其认为是一个二叉树；

这为我们提供了很大的便利性，由于森林可以转换为树，而任何的树都可以通过孩子兄弟表示法来转换为二叉树。

所以我们可以使用二叉树的遍历方法来对任何的树形结构进行遍历。

7. 哈夫曼树

哈夫曼树，也被叫做最优二叉树，是一种最小边权的加权二叉树

7.1 特点

相同权重的哈夫曼树不是唯一的
哈夫曼树的子树可以随意调换，这个调换并不会影响到它的长度
具有权重的节点都是叶节点，其余节点的权重都是通过叶节点的权重相加得到的
拥有最大权重的节点，最靠近根节点
哈夫曼树没有度为 1 的节点
一个拥有 $N$ 个叶节点的哈夫曼树，拥有 $2N - 1$ 个节点

7.2 构造

将给出的加权节点置于一个集合中
从中选出 2 个最小权重的节点，将他们的权重相加，得到一个新的节点作为它们的根节点。
将这两个节点从集合中去除，同时将那个根节点加入到集合中
重复步骤 2 和 3，直到这个集合为空

例如，假如我们有 5 个加权的节点

根据上面的步骤，我们可以得到如下的树：

或者如下的树：

注意，具有相同权重的哈夫曼树不是唯一的。

7.3 应用：哈弗曼编码

哈夫曼编码是基于字词的使用频率对其赋予权重，使用哈弗曼树来减少编码大小的一种技术。

由于哈夫曼树的权重最大（频率最为频繁）的节点最靠近根节点，所以它能显著减少编码所需要的体积

综上所述，我们定义左斜的边为 $0$ ，右斜的边为 $1$ ，
那么，上面的哈夫曼树对应的编码为：

5 = ‘11’
4 = ‘10’
3 = ‘00’
2 = ‘011’
1 = ‘010’

注意，这样的定义是为了不出现识别冲突