1. 树形结构

1.1 概念(了解)

树不再是顺序表, 链表, 栈, 队列那样一对一的线性结构. 而树则是一种一对多的数据结构, 由n(n>=0)个互不相交有限节点组层有层次关系的集合.
特点如下:

• 有一个特殊的节点, 称为根节点, 根节点没有前驱节点
• 除根节点外, 其余节点被分成M(M > 0)个互不相交的集合T1, T2, …, Tm，其中每一个集合 <= m) 又是一棵与树类似的子树。每棵子树的根节点有且只有一个前驱，可以有0个或多个后继
• 树是递归定义的[树的定义中用到了树的概念]

错误的二叉树 D和E不应该相交, I节点有两个父节点

正确的树:

1.2 概念(重要)

用的是上图中正确的二叉树来解释概念

1. 节点的度: 一个节点含有的子树的个数称为该节点的度[A的度就是2]

2. 非终端节点或分支节点:度不为0的节点[A, B, C, D, E]
   

3. 树的度: 一棵树中，最大的节点的度称为树的度; 如上图:树的度为3

4. 叶子节点或终端节点: 度为0的节点称为叶节点; 如上图:G、H、I、J节点为叶节点

5. 双亲节点或父节点: 若一个节点含有子节点，则这个节点称为其子节点的父节点; 如上图:A是B的父节点

6. 孩子节点或子节点: 一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点

7. 兄弟节点: 具有相同父节点的节点互称为兄弟节点[B和C, E和F, G, H和I]

8. 堂兄弟节点: 双亲在同一层的节点互称为堂兄弟节点[D和E, D和F]

9. 节点的祖先: 从根到该节点的所有分支经历所有节点[A]

10. 根结点: 一棵树中，没有双亲结点的结点;如上图:A

11. 森林: 由m(m>=0)棵互不相交的树的集合称为森林
    

12. 节点的层次: 从根开始定义起，根为第1层，根的子节点为第2层，以此类推

13. 树的高度或深度: 树中节点的最大层次; 如上图:树的高度为4
    

线性结构	树结构
第一个元素: 无前驱	根节点: 无双亲
最后一个元素: 无后继	叶节点: 无后继, 可多个
中间元素: 一个前驱一个后继	中间节点: 一个双亲, 多个孩子

1.3 树的表示形式

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如:双亲表示法、孩子表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法【在线OJ常考的就是这种表示形式】

class Node {
    int value;// 树中存储的数据
    Node child;// 第一个孩子引用
    Node brother;// 下一个兄弟引用
}

1.4 树的应用

文件系统管理(目录和文件)

2. 二叉树(BinaryTree重点)

2.1 概念

我们从经典的猜数字游戏开始, 由浅入深介绍二叉树.
在100以内猜数字, 最多几次可以猜对呢?答案是:7
下面是根据每次猜的大小来构建二叉树


我们发现利用这个大小关系来查找指定范围内某个数字, 效率不是高的一丁半点. 因此对于这种具有对立关系的情况: 0和1, 真与假, 上与下, 正与反, 对与错都适合用树来建模. 这种特殊的树状结构称为二叉树

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
特点:

1. 每个节点最多有2颗子树, 即不存在度大于2的节点
2. 二叉树有左右子树之分, 次序不能颠倒, 因此二叉树也是一颗有序树

2.2 二叉树的5种基本形态

1. 空二叉树
2. 只有一个根节点
3. 根节点只有左子树
4. 根节点只有右子树
5. 根节点即有左子树又有右子树
   

2.3 两种特殊的二叉树

2.3.1 斜树

顾名思义, 斜树一定要是斜的, 往哪儿斜也是有讲究的.所有的节点都只有左子树叫做左斜树; 所有的节点都只有右子树叫做右斜树
左斜树:

右斜树:

斜树有明显特点: 每一层都只有一个节点, 结点个数和树的深度相同.

有些同学就奇怪了: 这也能叫树吗, 这不是我们熟悉的线性表吗?
解释: 对的, 线性表结构可以理解为树的一种极其特殊的表现形式

2.3.2 满二叉树

在一棵二叉树中, 如果所有分支结点都存在左子树和右子树, 并且所有叶子节点都在同一层上, 这样的二叉树称为满二叉树

它的样子看得很美, 很匀称

满二叉树特点:

1. 叶子结点只能出现在最下一层, 出现在其它层就不可能达到平衡
2. 非叶子结点的度一定是2, 否贼就是"缺胳膊少腿"
3. 在同样深度的二叉树中, 满二叉树结点个数最多, 叶子结点最多

2.3.3 完全二叉树

把一颗具有 n 个节点的二叉树按层序编号, 编号i(<1=i<=n)的节点与同样深度的满二叉树中编号为i的节点在二叉树中所在位置完全相同

这是一种有些难以理解的特殊二叉树
首先从字面上理解区分, "满"和"完全"的差异: 满二叉树一定是一颗完全二叉树, 但是完全二叉树不一定是一颗满二叉树
什么是按层序编号?
上图中就是按照从上到下, 从左到右一次按照1, 2, 3, …, n的序号

完全二叉树特点:

1. 叶子结点只能出现在最下两层
2. 最下层的叶子结点一定集中在左部连续位置
3. 倒数第二层, 如果有叶子结点, 一定都在右部连续位置
4. 如果结点的度为1, 则该节点只有左孩子, 即不存在只有右子树的情况
5. 同样结点数的二叉树, 完全二叉树的深度最小

从上面的列子中, 也给了我们一个判断某二叉树是否为完全二叉树的办法: 看着二叉树的示意图, 心中默默给每个节点按照满二叉树的结构逐层顺序编号, 如果编号出现了空档, 就说明不是完全二叉树否则就是完全二叉树

2.4 二叉树的性质

2.4.1 第i层结点个数

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1)(i>0)个结点

2.4.2 树的所有最大点个数

若规定根节点的层数为1，则深度为K的二叉树最大节点数是 2^k-1(k>0)个结点

2.4.3 叶子结点和非叶子结点数量关系

对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0=n2+1[最下一层的叶子结点个数=上面的所有非叶子结点个数+1]

2.4.4 根据结点求树深度

具有n个节点的二叉树的深度K为log2^(n+1)向上取整

2.4.5 父子结点编号关系

对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i 的结点有:

• 若i>0，双亲序号:(i-1)/2;
• 若i=0，i为根节点编号，无双亲节点
• 若2i+1<n，左孩子序号:2i+1，否则无左孩子
• 若2i+2<n，右孩子序号:2i+2，否则无右孩子
  这个规律很重要, 涉及到堆排, 二叉搜索树需要用到这个规律

2.4.6 小练兵

设一棵完全二叉树中总共有1000个节点, 则该二叉树中 500 个叶子节点, 500个非叶子节点, 1个节点只有左孩子, 0个只有右孩子.

500个叶子结点计算步骤

1. 叶子结点总个数=第10层叶子结点个数+第9层叶子结点个数
   有同学会想: 为何第9层会有叶子结点呢?
   解释: 因为我们发现此树共有 1000 个结点, 而满二叉树的话会有 2^10-1 个结点, 所以说明 第10层没满, 第9层一定有叶子结点

有了这个理解后再做进一步的计算

2. 第10层全是叶子结点个数: 树的总结点个数 - 9层及以上所有结点个数
   因为是一颗完全二叉树, 所以可以保证第9层一定是满二叉树
   算式: 1000-(2^9-1)–>1000-511=489

现在我们还差第9层的叶子结点个数

3. 第9层叶子结点个数: 第9层结点个数 - 第10层父节点个数
   算式: 2^(9-1)-第10层父节点个数

最后的问题就是求第10层父节点个数

4. 第10层父节点个数求法
   如果结点个数n是偶数, 则其父结点个数为 n/2
   如果结点个数n是奇数, 则其父结点个数n/2+1
   在第一步中我们求得了第10层父节点个数, 求第10层父节点个数就是: 489/2 + 1–>245
5. 现在可以计算第 3 步得出第9层叶子结点个数:
   2^(9-1)-245–>256-245=11
6. 现在可以计算第 1 步中的所有整棵树的叶子结点;
   第 10 层结点数 + 第 9 叶子结点数: 489+11 = 500
7. 有了叶子结点个数, 很容易知道非叶子节点
   总结点个数-叶子结点个数: 1000-500
8. 由于完全二叉树第10层结点个数为489, 为奇数, 所以一定有1个节点只有左孩子, 有 0 个节点只有右子树

将一颗有 100 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根节点编号为 1 ，则编号为 98 的节点的父节点编号为: (98-1)/2 = 48

设非空二叉树的所有子树中，其左子树上的结点值均小于根结点值，而右子树上的结点值均不小于根结点值，则称该二叉树为排序二叉树。对排序二叉树的遍历结果为有序序列的是: 中序遍历

将一棵二叉树的根结点放入队列，然后递归的执行如下操作，将出队结点所有子结点加入队。以上操作可以实现层序遍历.

n个节点的完全二叉树，最多可以有多少层: log(n+1)上取整

2.5 二叉树的存储

2.5.1 顺序存储

二叉树的顺序存储就使用一维数组存储二叉树中的节点并且存储的位置应该要能体现节点之间的逻辑关系, 比如孩子双亲, 左右兄弟节点

2.5.1.1 完全二叉树的形式存储

将这颗二叉树存储数组中, 相应的下标对应其相等的位置

这下看出完全二叉树的优越性了吧, 由于它定义的严格, 所以顺序结构也能表现出二叉树的结构来

2.5.1.2 一般树的形式存储

对于一般二叉树而言, 层序编号不能反映逻辑关系, 但是可以按照完全二叉树编号, 只不过把不存在的结点设施为 ‘^’ 而已.浅色节点代表不存在

考虑一下极端情况: 又斜树【左斜树】

一颗深度为 k 的右斜树, 只有 k 个节点, 却需要分配 2^k-1 个存储单元, 这显然是对存储空间的浪费. 所以顺序存储只适用于完全二叉树

2.5.2 链式存储

既然顺序存储适应性不强, 我们就要考虑链式存储结构. 二叉树每个节点最多有两个孩子, 所以设计一个数据域和两个指针域比较理想. 这就是二叉链表
孩子表示法

class Node {
    int val;// 数据域
    Node left;// 左孩子的引用，常常代表左孩子为根的整棵左子树
    Node right;// 右孩子的引用，常常代表右孩子为根的整棵右子树
}

孩子双亲表示法主要用在在平衡树，本文采用孩子表示法来构建二叉树, 大多数的在线OJ题目也都采用的这种方法来构建二叉树.

3. 二叉树由浅入深解析

3.1 遍历二叉树

3.1.1 二叉树遍历原理

导言: 假设有20张100元的和2000张1元的奖券, 同时撒向了空中, 大家比赛看谁最中间的最多.

相信同学都会说: 先捡100元的. 道理非常简单, 因为捡1张100元的等于捡100张1元的, 效率好的不是一点点🤏.

所以得出这样的结论: 同样是捡奖券, 在有限时间内, 要达到最高效率, 次序非常重要. 对于二叉树的遍历来讲, 次序同样显得也很重要.

二叉树的遍历(traversing binary tree): 是指从根结点出发, 按照某种次序依次访问二叉树中的所有节点, 使得每一个节点被访问一次且仅仅被访问一次

这里有两个关键词: 依次和访问. 不同于线性结构, 最多也就是从头至尾, 循环, 双向等简单的遍历方式. 树的节点之间不存在唯一的前驱和后继关系, 在访问一个节点后, 下一个被访问的节点面临着不同的选择. 就像你人生的道路上, 高考填报志愿要面临哪个城市, 哪所大学, 具体专业等. 选择方式不同, 遍历的次序就完全不同

3.1.2 二叉树遍历方法

3.1.2.1 前序遍历

1. 若二叉树为空, 则返回空操作
2. 否则先访问根节点, 然后前序遍历左子树再前序遍历右子树
3. 最终访问的结果就是: ABDGHCEIF
   如下图就是 根左右 的顺序访问二叉树示意图
   

3.1.2.2 中序遍历

1. 树空, 则返回空操作
2. 否则就从根结点开始(注意并不是先访问根节点)
3. 中序遍历根节点的左子树
4. 然后访问根节点
5. 最后中序遍历右子树
6. 最终访问结果就是: GDHBAEICF
   如下图就是 左根右 的顺序访问二叉树示意图
   

3.1.2.3 后序遍历

1. 树空, 则返回空操作
2. 否先从左到右线叶子结点后节点的方式遍历访问左右子树, 最后访问根节点
3. 最终访问结果是: GHDBIEFCA
   如下图就是 左右根 的顺序访问二叉树示意图
   

3.1.2.4 层序遍历

1. 若树为空, 返回空操作
2. 否则从树的第一层, 也就是根节点开始访问
3. 从上而下逐层遍历
4. 在同一层中, 按左到右的顺序对节点逐个访问
5. 最终访问结果就是: ABCDEFGHI
   

3.1.3 二叉树遍历算法

假设我们有以下一颗二叉树T, 用链表结构存储

3.1.3.1 前序遍历算法根左右

OJ题目链接
递归前序遍历

private static void preOrderTraversal(BinaryTreeNode root) {
    if (root == null) {
        return;
    } else {
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
}

private static List<String> preOrderTraversal(BinaryTreeNode root) {
    List<String> result = new ArrayList<>();
    if (root == null) {
        return result;
    } else {
        result.add(root.val);
        result.addAll(preOrderTraversal(root.left));
        result.addAll(preOrderTraversal(root.right));
        return result;
    }
}

A B D H K E C F I G J

演示递归前序遍历步骤

1. 调用 preOrderTraversal(BinaryTreeNode root), root 根节点不为空, 所以执行 System.out.print(root.val + " "); 打印字母 A
   
2. 调用 preOrderTraversal(root.left), 访问了A 节点的左孩子, 不为 null, 执行 System.out.print(root.val + " "); 打印字母 B
   
3. 再次递归调用 preOrderTraversal(root.left), 访问了B 节点的左孩子, 不为 null, 执行 System.out.print(root.val + " "); 打印字母 D
   
4. 再次递归调用 preOrderTraversal(root.left), 访问了D 节点的左孩子, 不为 null, 执行 System.out.print(root.val + " "); 打印字母 H
   
5. 再次递归调用 preOrderTraversal(root.left), 访问H 节点的左孩子, 此时因为 H 节点无左孩子, 所以 root == null 返回此函, 此时递归调用 preOrderTraversal(root.right); 访问了 H 节点的右孩子, 执行 System.out.print(root.val + " "); 打印字母 K
   
6. 再次递归调用 preOrderTraversal(root.left), 访问 K 节点的左孩子, 返回
   调用 preOrderTraversal(root.right), 访问了 K 节点的右孩子, 也是 null, 返回.于是函数执行完毕.
   返回到上一级递归的函数(即打印 H 节点时的函数), 也执行完毕.[根左右都已经遍历完, 所以执行完毕]
   返回打印 D 节点时的函数, 调用 preOrderTraversal(root.ri ght)访问 D 节点的右孩子, 不存在
   返回到 B 节点, 调用 preOrderTraversal(root.right), 访问 B 节点的右孩子, 打印字母 E
   
   
7. 由于节点 E 没有左右孩子, 返回打印节点 B 时的递归函数, 递归执行完毕. 返回到最初的 preOrderTraversal(root), 调用 preOrderTraversal(root.right), 访问 A 节点的右孩子, 打印字母 C
   
8. 之后类似前面的递归调用, 一次继续打印F, I, G, j

知道了递归的代码如何运行, 那我们再看看非递归实现前序遍历

/*
非递归
1.先创建一个栈
2.根节点放进栈里
3.循环取栈顶元素
4.出栈并访问这个元素值域
5.把当前元素的右子树入栈, 再左子树入栈【因为先打印左子树后打印右子树所以对于栈而言应该先入右子树再入左子树】
*/
private static void preOrderTraversalNo(BinaryTreeNode root) {
    if (root == null) {
        return;
    } else {
        Stack<BinaryTreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()) {
            BinaryTreeNode top = stack.pop();
            System.out.print(top.val + " ");
            if (top.right != null) {
                stack.push(top.right);
            }
            if (top.left != null) {
                stack.push(top.left);
            }
        }
    }
}

A B D H K E C F I G J

演示迭代前序遍历步骤

非递归思路很巧妙的利用了栈的先进后出特性进行前序遍历

3.1.3.2 中序遍历算法左根右

OJ题目链接
递归中序遍历

private static void inOrderTraversal(BinaryTreeNode root) {
    if (root == null) {
        return;
    } else {
        preOrder(root.left);
        System.out.print(root.val + " ");
        preOrder(root.right);
    }
}
H K D B E A I F C G J 

演示递归中序遍历步骤

1. 调用 inOrderTraversal(BinaryTreeNode root), root 的根节点 A 不为 null, 于是调用 inOrderTraversal(root.left), 访问节点 B; B 不为空, 继续调用inOrderTraversal(root.left), 访问节点 D; D 不为空, 继续调用inOrderTraversal(root.left), 访问节点 H; H 不为空, 继续调用 inOrderTraversal(root.left), 访问节点 H的左孩子; 为空, 返回. 打印当前节点 H
   
2. 然后调用inOrderTraversal(root.right), 访问 H 节点的右节点 K.因为 K 无左孩子, 所以打印 K
   
3. 因为 K 没有右节点, 所以返回. 打印 H 节点的函数执行完毕, 返回. 打印字母 D
   
4. 节点 D 没有右孩子, 所以返回. 打印 B
   
5. 调用inOrderTraversal(root.right), 访问 B 节点的右节点 E, 因为 E 没有左孩子, 所以打印 E
   
6. 节点 E 无右孩子, 返沪. 打印 B 的函数执行完毕, 返回到了我们最初执行 inOrderTraversal(root) 的地方, 打印字母 A
   
7. 调用inOrderTraversal(root.right), 访问 A 节点的右孩子C,再递归访问 C 的左孩子 F, F 的左孩子 I, 因为 I 无右孩子, 所以打印 I. 之后分别打印 F, C, G, J

迭代中序遍历

/*
1.先创建一个栈
2.根节点入栈
3.循环取栈顶元素
4.左子树 集体入栈后再入右子树
5.最外层 while 循环判断需要留意.因为 cur= cur.right 会导致 cur == nulll, 因此在加入一个 !stack.empty() 的判断
*/
private static void inOrderTraversalNo(BinaryTreeNode root) {
    if (root == null) {
        return;
    } else {
        Stack<BinaryTreeNode> stack = new Stack<>();
        BinaryTreeNode cur = root;
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            System.out.print(cur.val + " ");
            cur = cur.right;
        }
    }
}

H K D B E A I F C G J 

演示迭代中序遍历步骤

3.1.3.2 后序遍历算法左右根]

OJ题目链接
递归后序遍历

/*
OJ: 通过
*/
class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null){
            return list;
        }else{
            postorderTraversal(root.left);
            postorderTraversal(root.right);
            list.add(root.val);
            return list;
        }
    }
}

private static void postOrderTraversal(BinaryTreeNode root) {
    if (root == null) {
        return;
    } else {
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val + " ");
    }
}

演示递归后序遍历步骤

1. 后序遍历先递归左子树, 由根节点 A->B->D->H, 节点 H 无左孩子, 再查看 H 的右孩子 K, 因为节点 K 无左右孩子, 所以打印 K.
2. K打印执行完之后返回到执行打印 H 的程序 System.out.print(root.val + " ");, 打印 H 节点
3. 后续的分析步骤和都是看返回的节点有无左右子树是否遍历完了: 遍历完了就输出根节点, 否则就继续遍历

迭代后序遍历

/*
和中序遍历类似
1.外层循环依旧需要加上 !stack.empty()来带动循环
2.被打印完的节点置为 null, 并且判断该节点是否被打印过
3.判断
超时
*/
private static void postOrderTraversalNo(BinaryTreeNode root) {
    if (root == null) {
        return;
    } else {
        Stack<BinaryTreeNode> stack = new Stack<>();
        BinaryTreeNode cur = root;
        BinaryTreeNode prev = null;
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.peek();
            if (cur.right == null || cur.right == prev) {
                stack.pop();
                System.out.print(cur.val + " ");
                prev = cur;
                cur = null;
            } else {
                cur = cur.right;
            }
        }
    }
}

K H D E B I F J G C A

演示迭代后序遍历步骤

3.1.3.2 层序遍历算法上至下, 左至右

OJ题目链接

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
      	// 1.返回空盒子
        List<List<Integer>> list = new ArrayList<>();
        if(root == null){
            return list;
        }else{
          	// 2.队列村粗
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                int size = queue.size();
                List<Integer> tmp = new ArrayList<>();
                while(size-- > 0){
                    TreeNode top = queue.poll();
                    tmp.add(top.val);
                    if(top.left != null){
                        queue.offer(top.left);
                    }
                    if(top.right != null){
                        queue.offer(top.right);
                    }
                }
                list.add(tmp);
            }
            return list;
        }
    }
}
[[A], [B, C], [D, E, F, G], [H, I, J], [K]]

演示OJ练习题中的代码执行步骤

正常的层序输出

/*
1.先创建一个队列
2.把根节点放在队列
3.循环取队列元素全部
4.内部 list 添加 当前元素
4.再把当前元素的左子树入队列， 再入右子树
5.大的 ret 添加每次新添元素后的 list
*/
private static void levelOrder(BinaryTreeNode root) {
    if (root == null) {
        return;
    } else {
        Queue<BinaryTreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            BinaryTreeNode top = queue.poll();
            System.out.print(top.val + " ");
            if (top.left != null) {
                queue.offer(top.left);
            }
            if (top.right != null) {
                queue.offer(top.right);
            }
        }
    }
}
A B C D E F G H I J K 

3.2 二叉树建立问题

3.2.1 前序中序构建二叉树

OJ题目链接

class Solution {
    private int findInorderIndex(int[] inorder, int inbegin, int inend, int key){
        for(int i=inbegin; i<=inend; ++i){
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }

    private TreeNode buildTreeChild(int[] preorder, int[] inorder, int inbegin, int inend){
        if(inbegin > inend){
            return null;
        }else{
            TreeNode root = new TreeNode(preorder[preIndex++]);
            int rootIndex = findInorderIndex(inorder, inbegin, inend, root.val);
            root.left = buildTreeChild(preorder, inorder, inbegin, rootIndex-1);
            root.right = buildTreeChild(preorder, inorder, rootIndex+1, inend);
            return root;
        }
    }

    private int preIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null){
            return null;
        }else{
            return buildTreeChild(preorder, inorder, 0, inorder.length-1);
        }
    }
}

其时建立二叉树也是利用了递归的原理. 只不过在当初打印节点的代码换成了生成节点, 给节点赋值的操作而已.
前序遍历的第一个节点一定是 根节点, 所以我们在中序遍历中划分根节点的左右子树, 然后递归找根节点再划分左右子树, 递归的终止条件是 区间的左一定要大于区间的右
代码思路:

1. 判断前序或中序是否有一个为 null【特殊情况处理】
2. 利用 buildTreeChild 函数返回根节点
3. 先构造根节点, 再递归构建左子树和右子树
4. 所有递归完之后返回最后的 root 就是树的根节点

演示图

1. 第一查找的是 preorder[preIndex] 的根节点【preIndex值为0】
   
2. 由于第二次划分的时候, 新的 inend 是 rootIndex-1 所以导致的 if(inbegin>inend) return; 程序返回执行 root.right = buildTreeChild(preorder, inorder, rootIndex+1, inend);
3. 第三次划分
   
4. 综合
   

3.2.2 中序后序构建二叉树

OJ题目链接

class Solution {
    private int postIndex = 0;

    private int findInorderIndex(int[] inorder, int inbegin, int inend, int key){
        for(int i=inbegin; i<=inend; ++i){
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }

    private TreeNode buildTreeChild(int[] inorder, int[] postorder, int inbegin, int inend){
        if(inbegin > inend){
            return null;
        }else{
            TreeNode root = new TreeNode(postorder[postIndex--]);
            int rootIndex = findInorderIndex(inorder, inbegin, inend, root.val);
            root.right = buildTreeChild(inorder, postorder, rootIndex+1, inend);
            root.left = buildTreeChild(inorder, postorder, inbegin, rootIndex-1);
            return root;
        }
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder == null || postorder == null){
            return null;
        }else{
            postIndex = postorder.length-1;
            return buildTreeChild(inorder, postorder, 0, postIndex);
        }
    }
}

后序遍历和前序变一样想法一样, 但是应该注意顺序【后序遍历最后一是根, 而前序遍历第一个就是根】

演示图
因为从后往前看的话, 根节点过来就是右节点, 所以先构建右子树在构建左子树. 遍历递归思路和上述一样, 这里就不多述

总结出一个二叉树的性质

1. 已知前序遍历和中序遍历, 可以确定唯一的一颗二叉树
2. 已知中序遍历和后序遍历, 可以确定唯一的一颗二叉树

思考: 已知前序遍历和后序遍历能否构建唯一的一颗二叉树

不能, 原因很简单. 比如一棵二叉树前序遍历是ABC 后序遍历是 CBA 我们可以确定根节点是 A 但不能确定 A 的左右子树. 这棵树就有如下的四种可能

3.2.3 根据二叉树创建字符串

OJ题目链接

解法1

1. 先处理左子树, 再处理右子树
2. 按照题目要求进行一个一个添加括号

class Solution {
    private void tree2strChild(TreeNode root, StringBuffer stringBuffer){
        if(root == null){
            return;
        }else{
            stringBuffer.append(root.val);
            // 1.处理左子树
            if(root.left == null){
                if(root.right == null){
                    return;
                }else{
                    stringBuffer.append("()");
                }
            }else{
                stringBuffer.append("(");
                tree2strChild(root.left, stringBuffer);
                stringBuffer.append(")");
            }
            // 2.处理右子树
            if(root.right == null){
                return;
            }else{
                stringBuffer.append("(");
                tree2strChild(root.right, stringBuffer);
                stringBuffer.append(")");
            }
        }
    }

    public String tree2str(TreeNode root) {
        if(root == null){
            return "";
        }else{
            StringBuffer stringBuffer = new StringBuffer();
            tree2strChild(root, stringBuffer);
            return  stringBuffer.toString();
        }
    }
}

解法2
代码少, 容易理解, 但运行效率低

1. 递归前序遍历的形式添加括号
2. 添加完毕之后再删除第一个和最后一个括号即可

class Solution {
    private StringBuffer stringBuffer = null;
    private void tree2strChild(TreeNode root){
        if(root == null){
            return;
        }else{
            stringBuffer.append("("+root.val);
            tree2strChild(root.left);
            if(root.left == null && root.right != null){
                stringBuffer.append("()");
            }
            tree2strChild(root.right);
            stringBuffer.append(")");
        }
    }
    public String tree2str(TreeNode root) {
        if(root == null){
            return "";
        }else{
            stringBuffer = new StringBuffer();
            tree2strChild(root);
            stringBuffer.deleteCharAt(0);
            stringBuffer.deleteCharAt(stringBuffer.length()-1);
            return stringBuffer.toString();
        }
    }
}

3.2.4 前序遍历字符串构建二叉树

OJ题目链接

import java.util.Scanner;
import java.util.Stack;

class TreeNode{
    char val;
    TreeNode left;
    TreeNode right;
    TreeNode(char val){
        this.val = val;
    }
}

public class Main{

	// 1.采用的是迭代的方式进行中序遍历
    private static void inOrderTraversal(TreeNode root){
        if(root == null){
            return;
        }else{
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            while(cur != null || !stack.empty()){
            	// 2. 左子树集体入栈
                while(cur != null){
                    stack.push(cur);
                    cur = cur.left;
                }
                cur = stack.pop();
                System.out.print(cur.val + " ");
                cur = cur.right;
            }
        }
    }
    
    private static int index = 0;// 记录打印的字符串下标, 因为是递归, 所以应该使用全局变量而不是局部变量
    private static  TreeNode createTree(String str){
        if(str == null){
            return null;
        }else{
            TreeNode root = null;
            // 1.越过空节点
            if(str.charAt(index) == '#'){
                ++index;
            }else{
                // 2. 按照前序根左右的形式递归构建二叉树
                root = new TreeNode(str.charAt(index++));
                root.left = createTree(str);
                root.right = createTree(str);
            }
            return root;
        }
    }
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            String str = scanner.next();
            TreeNode root = createTree(str);
            inOrderTraversal(root);
            System.out.println();
        }
    }
}

3.2.5 合并二叉树

OJ题目练习

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    	// 1.如果某个节点为null, 则返回另一个节点
        if(root1 == null){
            return root2;
        }else if(root2 == null){
            return root1;
        }else{
        	// 2.如果两个节点都不为null, 则开始合并二叉树
            TreeNode root = new TreeNode(root1.val+root2.val);
            root.left = mergeTrees(root1.left, root2.left);
            root.right = mergeTrees(root1.right, root2.right);
            return root;
        }
    }
}

3.2.6 递增二叉树

OJ练习题目

class Solution {
    private TreeNode cur = null;

    private void inOrderTraversal(TreeNode root){
        if(root == null){
            return;
        }else{
            //1.左
            inOrderTraversal(root.left);
            // 2.根
            cur.right = root;
            root.left =
            // 3.右
            inOrderTraversal(root.right);
        }
    }

    public TreeNode increasingBST(TreeNode root) {
        if(root == null){
            return null;
        }else{
            // 1.傀儡节点用来保存cur节点的位置用于返回
            TreeNode newRoot = new TreeNode(-1);
            // 2.移动节点
            cur = newRoot;
            inOrderTraversal(root);
            return newRoot.right;
        }
    }
}

3.3 经典题目解析

3.3.1 结点个数

/*
求结点个数
遍历思路: 递归每次遍历就自增 1[在线 OJ 可能会翻车: 先拿一个小树调用 gerSize1 方法, 然后再拿一个大的树来调用 getSize1]
子问题思路: return 1+func()...自带返回值
 */
private static int size = 0;

private static void getSize1(BinaryTreeNode root) {
    if (root == null) {
        return;
    } else {
        ++size;
        getSize1(root.left);
        getSize1(root.right);
    }
}


private static int getSize2(BinaryTreeNode root) {
    if (root == null) {
        return 0;
    } else {
        return 1 + getSize2(root.left) + getSize2(root.right);
    }
}

3.3.2 叶子结点个数

/*
求叶子结点个数
遍历思路: 递归遍历
子问题思路: return 1+func()...
 */
private static int leaftSize = 0;

private static void getLeafSize1(BinaryTreeNode root) {
    if (root == null) {
        return;
    } else {
        if (root.left == null && root.right == null) {
            ++leaftSize;
        } else {
            getLeafSize1(root.left);
            getLeafSize1(root.right);
        }
    }
}

private static int getLeafSize2(BinaryTreeNode root) {
    if (root == null) {
        return 0;
    } else {
        if (root.left == null && root.right == null) {
            return 1;
        } else {
            return getLeafSize2(root.left) + getLeafSize2(root.right);
        }
    }
}

3.3.3 第k层结点个数

private static int getKLevelSize(BinaryTreeNode root, int k) {
    if (root == null || k < 1) {
        return 0;
    } else {
        if (k == 1) {
            return 1;
        } else {
            return getKLevelSize(root.left, k - 1) + getKLevelSize(root.right, k - 1);
        }
    }
}

3.3.4 查找 val 所在结点

private static BinaryTreeNode find(BinaryTreeNode root, String val) {
    if (root == null) {
        return null;
    } else {
        if (root.val.equals(val)) {
            return root;
        } else {
            BinaryTreeNode ret = find(root.left, val);
            if (ret != null && ret.val.equals(val)) {
                return ret;
            }
            ret = find(root.right, val);
            if (ret != null && ret.val.equals(val)) {
                return ret;
            }
            return null;
        }
    }
}

3.3.5 相同的树

OJ题目练习

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 1.都为null： 说明之前的节点和节点值相等, 所以相等; 或者两个空节点也是相等的
        if(p == null && q == null){
            return true;
        // 2.某个节点遍历完了但另一个节点不为null, 所以是false    
        }else if(p == null || q == null){
            return false;
        }else{
            // 3节点值不相等就 false
            if(p.val != q.val){
                return false;
            }else{
                // 4. 递归进行下一次比较
                return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
            }
        }
    
}

3.3.6 另一棵树子树

OJ题目练习

class Solution {
      public boolean isSameTree(TreeNode p, TreeNode q) {
        // 1.都为null： 说明之前的节点和节点值相等, 所以相等; 或者两个空节点也是相等的
        if(p == null && q == null){
            return true;
        // 2.某个节点遍历完了但另一个节点不为null, 所以是false    
        }else if(p == null || q == null){
            return false;
        }else{
            // 3节点值不相等就 false
            if(p.val != q.val){
                return false;
            }else{
                // 4. 递归进行下一次比较
                return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
            }
        }
    }

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // 1.两个 nullnull 则是子树; 遍历到了叶子结点的子树【虽然不存在】, 说明之前遍历的都是相等的
        if(root == null && subRoot == null){
            return true;
        }else if(root == null && subRoot != null || root != null && subRoot == null){
            return false;
        }else{
            // 1.如果两个节点不为空, 且相等, 则是子树
            if(isSameTree(root, subRoot)){
                return true;
            // 2.递归判断是否为子树
            }else if(isSubtree(root.left, subRoot)){
                return true;
            }else if(isSubtree(root.right, subRoot)){
                return true;
            }else{
                return false;
            }
        }
    }
}

3.3.7 二叉树最大深度

OJ练习题目

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }else{
        	// 1.计算左子树的高度
            int left = maxDepth(root.left)+1;
            // 2.计算右子树的高度
            int right = maxDepth(root.right)+1;
            if(left>right){
                return left;
            }else{
                return right;
            }
        }
    }
}

3.3.8 平衡二叉树

OJ练习题目

class Solution {
    private int maxDepth(TreeNode root){
        if(root == null){
            return 0;
        }else{
            int left = 1+maxDepth(root.left);
            int right = 1+maxDepth(root.right);
            return left>right?left:right;
        }
    }

    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }else{
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
            if(Math.abs(left-right)>1){
                return false;
            }else{
                return isBalanced(root.left) && isBalanced(root.right);
            }
        }
    }
}

// 1. 优化后的代码: 边求高度边计算左右子树高度差, 不用递归两次
class Solution {
    private int maxDepth(TreeNode root){
        if(root == null){
            return 0;
        }else{
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
            if(left >= 0 && right >= 0 && Math.abs(left-right)<=1){
                return Math.max(left, right)+1;
            }else{
                return -1;
            }
        }
    }
    public boolean isBalanced(TreeNode root) {
        return maxDepth(root) > -1;
    }
}

3.3.9 对称二叉树

OJ练习题目

class Solution {
    private boolean isSameTree(TreeNode leftTree, TreeNode rightTree) {
        if (leftTree == null && rightTree == null) {
            return true;
        } else if (leftTree != null && rightTree == null || leftTree == null && rightTree != null) {
            return false;
        } else {
            if (leftTree.val != rightTree.val) {
                return false;
            } else {
                /*
                1. 之前的判断步骤和 比较二叉树是否相同 有点类似
                2. 之后应该比较 左树的左 和 右树的右; 左树的右 和 右树的左 是否相同
                */
                return isSameTree(leftTree.left, rightTree.right) && isSameTree(leftTree.right, rightTree.left);
            }
        }
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return isSameTree(root.left, root.right);
        }
    }
}

3.3.10 二叉树的完全性检验

OJ题目练习

利用队列特性进行全部入队列(包含 null 节点)再进行出队列判断

/*
1. 当遇到 null 节点时候说明已经遍历所有完全二叉树就退出
2. 在队列末尾慢慢弹出元素, 如果弹出了不为 null 则说明不是一个完全二叉树
*/
class Solution {
    public boolean isCompleteTree(TreeNode root) {
        if(root == null){
            return true;
        }else{
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            // 1.直到遇到 null 节点就停止入队列
            while(!queue.isEmpty()){
                TreeNode top = queue.poll();
                if(top != null){
                    queue.offer(top.left);// 程序走到叶子结点, 则会把 null 节点也带入队列, 后续的 peekpeek 探测的时候如果遇到了不为 null 的节点的话就代表在遇到 null 节点之后还有其它叶子结点, 此时一定不是完全二叉树
                    queue.offer(top.right);
                }else{
                    break;
                }
            }//程序执行到这儿, 说明队列中已经存储所有的节点
            // 2.节点出队列, peek探测元素是否为 null
            while(!queue.isEmpty()){
                TreeNode top = queue.peek();
                if(top != null){
                    return false;
                }else{
                    queue.poll();//出队列
                }
            }
            return true;
        }
    }
}

优化: 简单高效的通过对比节点数和下标数判断

class Solution {
    private int n=0, p=0;

    private boolean dfs(TreeNode root, int k){
        if(root == null){
            return true;// 1.节点遍历完毕
        }else if(k > 100){
            return false;// 2.题目提示: 树中将会有 1 到 100 个结点
        }else{
            ++n;// 3.每遍历一次, 结点个数就自增一, 记录当前节点下标
            p = Math.max(p, k);// 4.因为有左右子树, 所以每次应该选取最大下标才可
            return dfs(root.left, 2*k) && dfs(root.right, 2*k+1);
        }
    }

    public boolean isCompleteTree(TreeNode root) {
        if(root == null){
            return true;
        }else{
            if(!dfs(root, 1)){
                return false;// 1. 超过 100 节点就返回 false
            }else{
                return n == p;// 2.未超过 100 节点, 判断节点数和最大下标数是否相等
            }
        }
    }
}

3.3.11 二叉树最近公公祖先

OJ题目练习

/*
left == null, right == null: return null
left != null, right != null: return root
left == null, right != null: return right
left != null, right == null: return left
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q){
            return root;
        }else{
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if(left == null && right == null){
                return null;
            }else if(left != null && right == null){
                return left;
            }else if(left == null && right != null){
                return right;
            }else{
                return root;
            }
        }
    }
}

3.3.12 二叉树最大宽度

OJ题目练习

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if(root == null){
            return 0;
        }else{
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            int max_width = 0;
            while(!queue.isEmpty()){
                int cur_width = queue.getLast().val-queue.getFirst().val+1;// 1.利用结点的值域记录当前队列宽度
                // 2.头节点的左右子树入队列, 为下一次宽度计算做准备
                int count = queue.size();// 3.队列大小时刻变化着的, 我们应该保留入队列之前的队列大小
                for(int i=0; i<count; ++i){
                    TreeNode top = queue.poll();// 4.出队列元素且保留, 为后续左右子树入队列做铺垫
                    if(top.left != null){
                        queue.offer(top.left);
                        top.left.val = top.val << 1;// 5.依据的是二叉树的性质5--左孩子:2*i    根:i    右孩子: 2*i+1
                    }
                    if(top.right != null){
                        queue.offer(top.right);
                        top.right.val = (top.val << 1) + 1;
                    }
                }
                if(max_width < cur_width){
                    max_width = cur_width;
                }
            }
            return max_width;
        }
    }
}

其它语言要考虑下方提示: 整形溢出问题

3.4. 特殊的二叉树问题

3.4.1 搜索二叉树

    static class BinaryTreeNode {
        // 键值对的形式存储
        int key;
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;

        public BinaryTreeNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    // root: 表示树的根节点, 空树就是用 null 来表示
    private BinaryTreeNode root = null;

    //查找: 根据 Key 找 Value
    private Integer search(int key) {
        BinaryTreeNode cur = root;
        while (cur != null) {
            if (key < cur.key) {
                cur = cur.left;
            } else if (key > cur.key) {
                cur = cur.right;
            } else {
                return key;
            }
        }
        return null;
    }

    // 插入
    private void insert(int key, int value) {
        if (root == null) {
            root = new BinaryTreeNode(key, value);
        } else {
            BinaryTreeNode cur = root;
            BinaryTreeNode parend = null;
            while (cur != null) {
                parend = cur;
                if (key < cur.key) {
                    cur = cur.left;
                } else if (key > cur.key) {
                    cur = cur.right;
                } else {
                    return;// 二叉搜索树不存在相等, 如果相等也没必要赋值
                }
            }
            // 程序执行到这儿, 说明 parent 已经是 cur 的父节点, 修改父节点即可
            if (key < parend.key) {
                parend.left = new BinaryTreeNode(key, value);
            } else {
                parend.right = new BinaryTreeNode(key, value);
            }
        }
    }

    // 删除: 按照 key 删除
    private void remove(int key) {
        // 1.先查找 key 对应的位置
        BinaryTreeNode cur = root;
        BinaryTreeNode parent = null;
        while (cur != null) {
            parent = cur;
            if (key < cur.key) {
                cur = cur.left;
            } else if (key > cur.key) {
                cur = cur.right;
            } else {
                /*
                 2.核心删除
                    考虑当前 cur.left 为空
                        是否为根节点 root
                            是: 链接右子树
                            否: 接着判断当前删除的子节点 cur 是其父节点 parent 节点的左右子树关系
                    考虑当前 cur.right 为空
                         紧接 cur.left 根节点判断一样的思路
                    考虑当前 cur.right 和 cur.left 都不为空
                        移形换影删除
                 */
                if (cur.left == null) {
                    if (cur == root) {
                        root = cur.right;
                    } else if (cur == parent.left) {
                        parent.left = cur.right;
                    } else if (cur == parent.right) {
                        parent.right = cur.right;
                    }
                } else if (cur.right == null) {
                    if (cur == root) {
                        root = cur.left;
                    } else if (cur == parent.left) {
                        parent.left = cur.left;
                    } else if (cur == parent.right) {
                        parent.right = cur.left;
                    }
                } else {
                    // 具体移形换影步骤
                    // 1.右子树找最小值, 并记录其父节点
                    BinaryTreeNode targetParent = cur;
                    BinaryTreeNode target = cur.right;
                    while (target.left != null) {// 最小值特点是: 左子树为空
                        targetParent = target;
                        target = target.left;
                    }
                    // 2.程序执行到这儿: targetParent 是 target 父节点; target 是右子树中最小值
                    // 3.就把 替罪羊target 节点的值赋值给删除节点
                    cur.key = target.key;
                    cur.value = target.value;
                    // 4.断开末尾 最小值节点 的关系, 建立新的关系
                    if (target == targetParent.left) {
                        targetParent.left = target.right;// 最小值左节点为 null
                    } else if (target == targetParent.right) {
                        targetParent.right = target.right;
                    }
                }
            }
        }
    }

3.4.2 赫夫曼树及其应用

3.4.1. 赫夫曼树

什么是哈夫曼树
哈夫曼树的目的是为了字符串的压缩, 我们经常用的 zip, tar, ara…等等压缩都是基于 哈夫曼树的原理

举个中小学通用的评分标准

if (a < 60) {
       b = "不及格";
   } else if (a < 70) {
       b = "及格";
   } else if (a < 80) {
       b = "中等";
   } else if (a < 90) {
       b = "良好";
   } else {
       b = "优秀";
   }

粗看没什么问题, 结果是对的. 一张好的试卷应该让学生成绩大部分处于 中等 或 良好 范围， 优秀 和 不及格 应该很少才对. 而上面的程序, 就需要让所有的成绩判断是否及格, 再逐级而上得到结果. 数据量大的时候, 算法效率很低下

实际生活中学生成绩分布规律如下表

那么 70 分以上大约占总数80%的成绩都需要经过 3 次以上的判断才可以得到结果, 这显然不合理.

仔细观察发现: 中等成绩(70~79)比例最高, 其次是良好成绩, 不及格所占比例最少. 对上述的二叉树重新分配如下(有点像搜索二叉树, 其实并不是的, 仔细往后面的文章看):

3.4.2.赫夫曼树定义与原理

把两颗二叉树简化成叶子结点带权的二叉树【A: 不及格, B: ,及格C: 中等,D:良好, E:优秀】

从树中一个节点到另一个节点之间的分支结构狗曾两个鸡诶但之间的路径, 路径上的分支树木称作路径长度

二叉树a中根节点到D节点路径长度就是4, 二叉树b中根节点到D节点长度就是2
二叉树a总长度: 1+1+2+2+3+3+4+4=20
二叉树b总长度: 1+1+2+2+2+2+3+3=16

如果考虑带权的节点: 该节点到树根之间的路径长度与节点上权的乘积. 树的带权路径长度作为作为树中所有叶子结点的带权路径长度的之和, 用 WPL 来表示. 其中最小的 WPL 的树称为 赫夫曼树.

二叉树a WPL: 5 * 1 + 15 * 2 + 40 * 2 + 30 * 4 + 10 * 4 = = 315
二叉树b WPL: 5 * 3 + 15 * 3 + 40 * 2 + 30 * 2 + 10 * 2 = 220

这样的结果意味着如果有 1_0000 个学生的百分制数据计算五级分制成绩, 二叉树a需要计算31500次比较, 二叉树b需要2200次比较. 差不多少了1/3的量, 性能上提高不是一点点

该如何构建赫夫曼树呢?

1. 先把有权值的叶子结点按照从小到大的顺序排列成一个有序序列[A5, E10, B15, D30, C40]
2. 取头两个最小全值的节点作为一个新节点 N1 的两个字节点, A 是 N1 左子树, E 是 N1 右子树. 注意左右子树大小关系
   
3. 将 N1 替换 A 与 E, 插入有序序列中, 保持从小到大排列[N1 15, B15, D30, C40]
4. 重复步骤2. 将 N1 与 B 作为一个新节点 N2 的两个字节点
   
   重复步骤3的序列替换序列最小值, 再重复步骤2生成新的节点…
   
   最终效果：
   
   WPL=40 * 1 + 30 * 2 + 15 * 3 + 10 * 4 + 5 * 4 = 205, 比搜索二叉树还少了15, 因此这才是最优的赫夫曼树

3.4.3 赫夫曼编码

赫夫曼树更大作用是为解决当年远距离通信(主要是电报)的数据传输的最优化问题.
比如有一段文字内容为 “BADCADFEED” 要网络传输给别人, 显然用二进制的数据(0 和 1)来表示是很自然的想法, 这段文字有 6 个字母ABCDEF.
相应的二进制数据表示就是:

这样真正传输的就是编码后的 “001000011010000011101100100011”, 对方接受可以按照 3 位一分来译码. 如果文章内容很长, 这样的二进制串也很可怕.
此时就应该使用 赫夫曼树.

假设6个字母的频率： A:27, B:8, C:15, D:15, E:30, F:5 合起来正好是100%.
左图构造赫夫曼树的过程权值显示; 右图是将权值左子树改为0, 右子树分制改为1后的赫夫曼树

此时我们对 6 个字母重新编码

原编码: 001000011010000011101100100011[30个字符]
新编码: 1001010010101001000111100[25个字符]
少了5个字符, 也就是大约 17%[5/30=0.167] 的成本.
字符愈多, 这种压缩效果更明显

问题来了: 收到了赫夫曼编码又该如何解析呢?
编码中非0即1, 长短不等的话其实很容易混淆的, 所以要设计长短不等的编码: 任一字符的编码都不是另一个字符编码的前缀, 这种比那吗称为前缀编码[01, 1001, 101, 00, 11, 1000都是不同长短长度, 因此不容易混淆]

这样并不足以, 我们去方便的解码, 因此在解码的时候接收方和发送方都必须要约定好相同的 赫夫曼编码规则

当收到 1001010010101001000111100 时, 约定好的 赫夫曼编码规则 可知 1001 得到第一个字母是 B, 接下来的诶 01 意味着第二个字母 A…

一般地，设需要编码的字符集为{ d1,d2, …, dn },各个字符在电文中出现的次数或频率集合为{ w1,w2, …, wn}, 以d1,d2,…, dn作为叶子结点，以w1,w2, …, wn作为相应叶子结点的权值来构造一棵赫夫曼树。
规定赫夫曼树的左分支代表0,右分支代表1,则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，这就是赫夫曼编码。

3.4.3 线索二叉树

^: 表示空指针, 图中二叉树有许多空指针, 发现这些空间都没有利用. 这其实不是一个好现象, 应该合理利用起来.

首先那我们来看看有多少个多少个空指针呢?
对于一个有 n 个节点的二叉树有 2n 个指针, 而 n 个节点的二叉树一共有 n-1 条分支线数, 也就是说存在 2n-(n-1)=n+1 个空指针域. 对应到题目中就有 11 个空指针的浪费.
另一方面, 我们中序遍历二叉树得出 HDIBJEAFCG, 这样的字符序列, 我们知道 J 的前驱是 B 后继是 E, 也就是说从中序遍历二叉树我们可以知道任意一个节点的前驱和后继

问题: 上边找到的规律是建立在已经遍历过的基础上, 在二叉链表上我们只知道每个左右孩子的地址, 而不知道后继是谁, 后继是谁要想知道必须要再次遍历一次

解决方案

我们在遍历的时候就创建好前驱后继.

我们把这种前驱和后继的指针称为线索, 加上线索的二叉链表称为线索链表, 相应的二叉树称为线索二叉树(Threaded Binary Tree)

我们把这棵二叉树进行中序遍历, 将所有空指针的 rchild, 改为指向它的后续结点. 于是就可以通过指针知道 H 的后继是 D(1⃣️), I 的后继是 B(2⃣️), J 的后继是 E(3⃣️)(E.next = A(4⃣️), F.next = C(5⃣️), G.next = null(6⃣️)). 此时共有 6 个空指针被利用.

再看图, 把这棵二叉树中的所有空指针域中的 lchild, 改为指向当前结点的前驱. 因此 H 的前驱是 NULL(1⃣️), I 的前驱是 D(2⃣️)[J.prev = B(3⃣️), F.prev = A(4⃣️), G.prev = C(5⃣️)].一共有 5 个空指针被利用, 加上上面的 右子树 利用后一共有 11 个空指针被利用

实线空心箭头为前驱 prev, 虚线实心箭头为后继 next

就更容易看出, 线索二叉树, 等于是把一棵二叉树变成了一个双向链表, 这样对于我们的插入删除节点, 查找某个节点都带来了方便. 所以我们对二叉树以某种次序遍历使其变为线索二叉树的过程为线索化

二叉搜索树与双向链表
OJ题目练习

Java: 构建代码

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    private TreeNode prev = null;// 1. 用来记录前驱节点
    private void ConvertChild(TreeNode root){
        if(root == null){
            return;
        }else{
            // 2.根绝二叉搜索树性质: 中序遍历就是有序结果
            ConvertChild(root.left);
            /*
            3.建立前后指向
                节点的左子树是前驱, 右子树是后继
                    对于最左端叶子结点 4 这种没有左右子树的结点要特殊考虑: 保留的前驱节点的右子树指向当前函数调用的节点【4.right = 6】, 但对于这种情况还需要判断它是否为 null, 否则就会 空指针异常
                        4.left = null
                        null.right = 4;空指针异常
                        null = 4;
                        
                        加上 if 判断后:
                        4.left = null;
                        null = 4;
                        程序 return 返回到 6节点函数
                        6.left = 4;
                        4.right = 6;
                        4 = 6;
             */
            root.left = prev;// 第一次递归结束返回到 root 是4这个节点
            if(prev != null){
                prev.right = root;
            }
            prev = root;
            ConvertChild(root.right);
        }
    }
    
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }else{
            ConvertChild(pRootOfTree);
            while(pRootOfTree.left != null){
                pRootOfTree = pRootOfTree.left;
            }
            return pRootOfTree;
        }
    }
}

Java 语言在定义节点类的时候只需要: 数据域val, 左子树left, 右子树right, 在实现双向链表的时候需要额外一个 prev节点来存放当前节点的前驱【左子树】

C: 线索二叉树结构体思路
lchild: 左子树, rchild: 右子树

对于C语言而言, 我们如何知道某一节点的 lchild 是指向它的左孩子还是指向前驱呢? rchild 是指向右孩子还是后继呢?
比如: E 节点的 lchild 是指向它的左子树 J, 而 rchild 却是指向它的后继 A. 显然我们在决定 lchild 是指向左孩子还是前驱, rchild 是指向右孩子还是后继上是需要一个区分标志的. 因此我们给每个节点在增设两个标志域 ltag 和 rtag, 注意 ltag 和 rtag 只是存放 0 和 1的布尔型变量, 其占用的内存空间要小于像 lchild 和 rchild 的指针变量

lchild	ltag	data	rtag	rchild

• ltag == 0时指向该节点的左孩子, 为1时指向该节点的后继
• rtag == 0时指向该节点的右孩子, 为1时指向该节点的后继
  

typedef int DataType;// 数据类型

typedef enum {
    Link,//Link == 0表示只想做还有子树指针
    Thread, //Thread == 1表示只想前驱或后继的线索
} PointerTag;

typedef struct BiThrNode {// 二叉树存储节点结构
    DataType data;// 数据域
    struct BiThrNode *lchild, *rchild;// 左右子树
    PointerTag  LTag;// 左标志
    PointerTag  RTag;// 右标志
}BiThrNode, *BiThrTree;

那么了解了C语言的结构体构造线索二叉树原理后我们该如何实现呢?

参考前边 Java代码的实现, 我们发现可以规律无非是左根右的方式处理数据. 无非是中间那部分 根 的数据如何处理

BiThrNode *prev;// 全局变量, 始终指向刚刚访问过的节点
void InThreading(BiThrNode *pb) {
    if (pb) {
        /*
         * 中序遍历线索化二叉树递归函数
         */
        // 1. 左
        InThreading(pb->lchild);

        /*
         * 2.中间部分建立联系
         *      因为中序遍历之后第一个元素就是 链表的头节点, 所以应该选取左节点为空的节点就是 链表头节点
         *
         * 前驱分析:
         *      if(!pb->lchild): 表示如果某结点的左子树域为空, 因为其前驱节点刚刚访问过
         *      赋值给了 prev, 所以可以把 prev 赋值给 pb->lchild, 并修改 pb->Ltag=Thread.完成了前驱节点的线索化
         * 后继分析:
         *       此时 pb 节点的后继还没有访问到, 只能通过它的前驱节点 prev 的右子树 rchild 来判断:
         *              if(!prev-rchild)为空, 则 pb 就是 prev 的后继, 于是 prev-Thread, prev->rchild = pb 完成后继节点的线索化
         * 完成前驱和后继的判断后把 pb 给 prev, 便于下一次遍历
         */
        if (!pb->lchild) {// 如果没有左孩子
            pb->LTag = Thread;// 前驱线索
            pb->lchild = prev;// 左孩子指针指向前驱
        }
        if (!prev->rchild) {// 如果没有右孩子
            prev->LTag = Thread;// 后继线索
            prev->lchild = pb;// 右孩子指针指向后继
        }
        prev = pb;
        // 3.右
        InThreading(pb->rchild);
    }
}

4. 总结回顾

5. 结束语