Skip to content

Latest commit

 

History

History
396 lines (303 loc) · 19.9 KB

二叉树.md

File metadata and controls

396 lines (303 loc) · 19.9 KB
Raw

专栏原创出处：github-源笔记文件 ，github-源码 ，欢迎 Star，转载请附上原文出处链接和本声明。

[toc]

二叉树

由 $n(n\ge 0)$ 个结点组成的有限集，每一个根结点最多有两棵互不相交的子树，这样的树称为二叉树。
当 $n = 0$ 时称为空树；二叉树中有且只有一个称为根的结点。
除根结点以外的其余结点分为两个互不相交的子集 $T1$ 和 $T2$，$T1$ 称为根的左子树，$T2$ 称为根的右子树，$T1$ 和 $T2$ 又可以看作二叉树。

二叉树的特点：结点的子树有左右之分，其次序不能颠倒；二叉树的度不超过 2。二叉树可以是空集，根也可以有空的左子树或空的右子树。

二叉树不是树的特殊情况：二叉树每个结点最多有两棵子树，而树结点的子树可以有无数棵；二叉树结点的子树要区分左子树或右子树，次序不能任意颠倒；树结点只有一个孩子时，没有左右次序之分。

二叉树的性质：

  • 在二叉树的第i层上最多有 $2^{i-1}$ 个结点，最少有 1 个结点。
  • 深度为 $k$ 的二叉树最多有 $2^i-1$ 个结点( $k\ge 1$ )。
  • 对任何一棵二叉树 $T$，如果其叶子数为 $n_0$，度为 2 的结点数为 $n_2$ 个，则 $n_0 = n_2 + 1$。
    证明如下：
  1. 二叉树结点总数：$n = n_0 + n_1 + n_2$；
  2. 除了根结点外，其余结点都有一个分支进入，设 $B$ 为分支总数，则 $n = B + 1$；
  3. 由于树的分支是由度为 1 或 2 的结点射出，所以 $B = n_1 + 2 * n_2$
  4. 综上所述：${n = n_1 + 2 * n_2 + 1} \Rightarrow n_0 = n_2+1$

满二叉树

一棵深度为 $k$ 且有 $2^k-1$ 个结点( $k\ge 1$ )的二叉树称为满二叉树

满二叉树的特点：从根结点开始，自上而下、自左而右，每一层上的结点数都是最大结点数，并且叶子结点全部在最底层。

完全二叉树

深度为 $k$ 的具有 $n$ 个结点的二叉树，当且仅当其每一个结点都与深度为 $k$ 的满二叉树的编号 $1\to n$ 的结点一一对应的二叉树称为完全二叉树。
简而言之，在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完成二叉树.

完全二叉树的特点：叶子只能分布在层次较大的两层上；对任一结点，如果其右子树的最大层次为 $l$，则左子树的最大层次必为 $l$ 或 $l+1$。

完全二叉树的性质：

  • 具有 $n$ 个结点的完全二叉树的深度为 $\lfloor log_{2n} \rfloor +1$。
  • 如果对一棵有 $n$个 结点的完全二叉树的结点按层次编号，则对任一结点：
    • 若 $i=1$，则该结点便是二叉树的根；
    • 若 $i>1$，则其双亲的结点编号为 $i/2$；
    • 若 $2i>n$，则该结点无左孩子，即该节点为叶子结点；否则其左孩子结点为 $2i$；
    • 若 $2i+1>n$，则该结点无右孩子；否则其左孩子结点为 $2i+1$。

二叉树存储

二叉树顺序存储

按满二叉树的结点层次编号，依次存放二叉树中的数据元素，将编号为 $i$ 的结点元素存储在下标为 $i-1$ 的数组位置，这样的存储结构称为二叉树顺序存储。

二叉树顺序存储的特点：每个结点与完全二叉树的结点相对照，不存在的结点用 0 表示。

二叉树顺序存储的缺点： 若深度为 $k$ 且只有 $k$个结点的二叉树，存储长度为 $2^k-1$，会造成存储空间的浪费；顺序存储只适合存储满二叉树或完全二叉树。

二叉树链式存储

每个结点由数值域、左子树指针域、右子树指针域构成的链式存储称为二叉树链式存储。

二叉树链式存储的特点：根据结点的指针域可以找到每个结点的所有孩子结点，不能找到其父节点；若二叉链表中存在 $n$ 个结点，则有 $n+1$ 个空指针域。

二叉树遍历

顺着某一条搜索路径寻访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次，称为遍历二叉树。

遍历二叉树的方法：依次遍历二叉树中的根节点、左子树、右子树三个组成，便完成了整个二叉树的遍历。
根据限定的先左后右的方式，可以分为：先序遍历、中序遍历、后序遍历。

先序遍历

二叉树先序遍历的步骤：

  1. 若二叉树为空，则空操作；
  2. 否则，先访问根结点；
  3. 先序遍历左子树；
  4. 先序遍历右子树；
  5. 直至所有结点都访问一遍。

下图中的树进行先序遍历结果为：$ABDGHCEIF$

先序遍历递归算法：

void preOrderTraverse(BiTree T){
if(T==null) return ;// 空二叉树
else {
    visit(T);// 访问根结点
    preOrderTraverse(T.lchild);//递归遍历左子树
    preOrderTraverse(T.rchild);//递归遍历右子树
    }
}

中序遍历

二叉树的中序遍历步骤：

  1. 若二叉树为空，则空操作
  2. 中序遍历左子树
  3. 访问根结点
  4. 中序遍历右子树
  5. 直至所有结点都访问一遍

对下图中的树进行中序遍历结果为：$GDHBAEICF$

中序遍历递归算法：

void inOrderTraverse(BiTree T){
if(T==null) return ;// 空二叉树
else {
    inOrderTraverse(T->lchild);//递归遍历左子树
    visit(T);// 访问根结点
    inOrderTraverse(T->rchild);//递归遍历右子树
    }
}

中序遍历非递归算法的基本思想：建立一个栈，根结点进栈，遍历左子树，根结点出栈，输出根结点，遍历右子树。

后序遍历

二叉树的中序遍历步骤：

  1. 若二叉树为空，则空操作
  2. 后序遍历左子树
  3. 后序遍历右子树
  4. 访问根结点
  5. 直至所有结点都访问一遍

对下图中的树进行后序遍历结果为：$GHDBIEFCA$

后序遍历递归算法：

void inOrderTraverse(BiTree T){
if(T==null) return ;// 空二叉树
else {
    inOrderTraverse(T->lchild);//递归遍历左子树
    inOrderTraverse(T->rchild);//递归遍历右子树
    visit(T);// 访问根结点
    }
}

先序/中序/后序遍历应用

1.数值表达式的前缀/中缀/后缀表达式
对下图中的树进行遍历结果为：先序(波兰式)：$- * a b c$；中序：$a * b - c$；后序(逆波兰式)：$a b * c -$

2.由遍历序列确定唯一二叉树

2.1.已知先序和中序序列求二叉树。
先序序列：$ABCDEFG$
中序序列：$CBEDAFG$
特点：先序遍历，根结点必在先序序列头部
唯一确定的二叉树为：

2.2.已知中序和后续序列求二叉树。
中序序列：$BDCEAFHG$
后序序列：$DECBHGFA$
特点：后序遍历，根结点必在先序序列尾部
唯一确定的二叉树为：

先序、中序、后序遍历总结

遍历特点：三种遍历的递归算法中每个结点都经过三次，访问的路径是相同，只是访问结点值的时机不同：先序遍历第1次经过时访问、中序遍历第2次经过时访问、后序遍历第3次经过时访问。

层次遍历

从根结点开始，按从上到下、从左到右的顺序访问每一个结点(每个结点只访问一次)的过程称为层次遍历。

对下图中的树进行层次遍历结果为：$ABCDEFGHI$

层次遍历的算法实现，需要借助一个队列：

  1. 将根节点进队；
  2. 队不为空时从队列中出列一个结点 $p$，访问该结点，若它有左孩子结点，将左孩子结点进队；若它有右孩子结点，将右孩子结点进队。

线索二叉树

二叉链表的存储中结点存在空指针域，则：

  • 如果结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；
  • 如果结点的右孩子为空，则将空的右孩子指针域改为指向其后继。
    这种指向前驱和后继的指针称为线索。

加上了线索的二叉树称为线索二叉树。

将二叉树按某种遍历次序使其变为线索二叉树的过程称为线索化。

为了区分左指针和右指针指向的是孩子还是前驱或后继，在二叉链表中每个结点增设两个标志域 $ltag$ 和 $rtag$：

  • $ltag=0$ ：左指针指向该结点的左孩子；$ltag=1$ ：左指针指向该结点的前驱
  • $rtag=0$ ：右指针指向该结点的右孩子；$rtag=1$ ：右指针指向该结点的后继

构造线索二叉树

线索二叉树构造的实质：遍历二叉树得到每个结点的前驱和后继结点，将二叉链表中的空指针指向前驱或后继的线索。

构造线索二叉树的步骤

以中序遍历为例实现二叉树的线索化，增加两个指针记录结点的先后顺序：指针 $pre$ 指向刚刚访问过的结点，指针 $p$ 指向当前访问的结点。

对以 $p$ 为根结点的子树进行中序线索化：

  1. 如果 $p$ 非空，左子树递归线索化；
  2. 如果 $p$ 的左孩子为空，则 $p$ 的左指针指向 $pre$，将 $ltag$ 置为1；否则将 $p$ 的 $ltag$ 置为 0；
  3. 如果 $pre$ 的右孩子为空，则 $pre$ 的右指针指向 $p$，将 $rtag$ 置为1；否则将 $pre$ 的 $rtag$ 置为 0；
  4. 将 $pre$ 指向刚访问过的结点 $p$ ，即 $pre = p$；
  5. 右子树递归线索化。

带有头结点的线索二叉树：

  1. 其头结点 $ltag = 0$，左指针指向根结点；
  2. $rtag = 1$，右指针指向遍历序列中最后一个结点；
  3. 遍历序列中第一个结点的左指针域和最后一个结点的右指针域均指向头结点

遍历线索二叉树

本节讨论如何在线索二叉树中查找结点的前驱和后继结点，以下仅讨论在中序线索二叉树中查找，先序和后序线索二叉树中的查找可类似得到

在中序线索二叉树中查找

查找结点 $p$ 的前驱结点：

  • 若 $p.ltag = 1$ 表示 $p$ 的左子树空，$p.lchild$ 指向其中序前驱结点；
  • 若 $p.ltag = 0$ 表示 $p$ 的左子树不为空，则 $p$ 的中序前驱必是其左子树中第一个中序遍历到的结点。
    • 从 $p$ 的左孩子开始，沿该孩子的右指针链往下查找，直至找到一个没有右孩子的结点为止；
    • 该结点是 $p$ 的左子树中"最右下"的结点，即 $p$ 的中序前驱结点。

查找结点 $p$ 的后继结点：

  • 若 $p.rtag = 1$ 表示 $p$ 的右子树空，$p.rchild$ 指向其中序后继结点；
  • 若 $p.rtag = 0$ 表示 $p$ 的右子树不为空，则 $p$ 的中序后继必是其右子树中第一个中序遍历到的结点。
    • 从 $p$ 的右孩子开始，沿该孩子的左链往下查找，直至找到一个没有左孩子的结点为止；
    • 该结点是 $p$ 的右子树中"最左下"的结点，即 $p$ 的中序后继结点。

最优二叉树(赫夫曼树)

从树中一个结点到另一个结点之间的分支构成这两个结点间的路径称为路径。
两结点间路径上的分支数称为结点的路径长度。
从树根到每一个结点的路径长度之和称为树的路径长度。

将树中结点赋给一个有着某种含义的数值，则该值成为结点的权。
从根结点到该结点之间的路径长度与该结点的权的乘积称为结点的带权路径的长度。
树中所有叶子结点的带权路径长度之和称为树的带权路径长度。

带权路径长度最短的二叉树称为最优二叉树

不同路径长度的二叉树

最优二叉树的构造算法

为了树的带权路径长度越小，权越大的叶子需离根越近。

给定 $n$ 个权值为 ${w_1,w_2,...,w_n}$ 集合，最优二叉树的构造步骤如下：

  • 构造森林全是根：
    • 将集合中的每个元素构成一个二叉树的根节点，则所有二叉树构成森林 $F$；
    • 根结点的权为 $w_i$，并且左右子树均为空。
  • 选用两小造新树：
    • 在 $F$ 中选取两棵根节点权值最小的树作为左右子树构造成一棵新的二叉树；
    • 重置新的二叉树的根节点的权值为左右子树的根节点的权值之和。
  • 删除两小造新人：
    • 在 $F$ 中删除这两棵树；
    • 将新得到的二叉树加入到 $F$ 中。
  • 重复2、3剩单根：
    • 重复2、3步骤；
    • 直到 $F$ 只包含一棵树为止。

最优二叉树的特点：

  • 包含 $n$ 棵树的森林要经过 $n-1$ 次合并才能形成最优二叉树；
  • 最优二叉树的构造过程共产生 $n-1$ 个新结点，且该 $n-1$ 个新结点都具有两个孩子的分支结点；
  • 最优二叉树共有 $2n-1$ 个结点，且所有分支结点的度均不为 1。

最优二叉树的构造示例

赫夫曼树的构造过程：采用顺序存储结构，使用一维结构数组；每个结点存储权重、双亲结点下标、左孩子结点下标、右孩子结点下标。

若权 $w=(5,29,7,8,14,23,3,11)$，则构造的数组长度为 15，数组前 8 个位置放置已知结点，后 7 个位置放置新创建的结点。则根据权$w$构早出的赫夫曼树如下：

其构造过程的存储如下：

赫夫曼编码

赫夫曼编码特点：在使用不定长编码时，应使任意字符的编码都不是另一个字符编码的前缀。

赫夫曼编码步骤：

  • 统计字符集中每个字符出现的平均概率（频率越大，编码越短）；
  • 将每个字符的概率值作为权值构造赫夫曼树(概率越大，路径越短)；
  • 在赫夫曼树的每个分支上标 0 或 1：左分支为 0，右分支为 1；把从根结点到每个叶子的路径上的标号连接起来，作为该叶子的字符编码。

解码：

  1. 构造赫夫曼树
  2. 依次读入二进制码，一旦到达某叶子结点时，即可译出字符
  3. 再从根结点出发继续译码，直到结束

算法例题

1.计算右侧小于当前元素的个数 例题：给定一个整数数组 nums，按要求返回一个新数组 counts，使得数组 counts 有该性质——counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例 输入：[5, 2, 6, 1] 输出：[2, 1, 1, 0]

解释 5 的右侧有 2 个更小的元素（2 和 1） 2 的右侧仅有 1 个更小的元素（1） 6 的右侧有 1 个更小的元素（1） 1 的右侧有 0 个更小的元素

解题思路：
给定一个数组 nums，里面都是一些整数，现在要求打印输出一个新的数组 counts，counts 数组的每个元素 counts[i] 表示 nums 中第 i 个元素右边有多少个数小于 nums[i]。

例如，输入数组是 [5, 2, 6, 1]，应该输出的结果是 [2, 1, 1, 0]。

因为，对于 5，右边有两个数比它小，分别是 2 和 1，所以输出的结果中，第一个元素是 2；对于 2，右边只有 1 比它小，所以第二个元素是 1，类推。

如果使用线段树解法，需要理清线段树的每个节点应该需要包含什么样的信息。

线段树每个节点记录的区间是数组下标所形成的区间，然而对于这道题，因为要统计的是比某个数还要小的数的总和，如果把分段的区间设计成按照数值的大小来划分，并记录下在这个区间中的数的总和，就能快速地知道比当前数还要小的数有多少个。

  1. 首先，让从线段树的根节点开始，根节点记录的是数组里最小值到最大值之间的所有元素的总和，然后分割根节点成左区间和右区间，不断地分割下去。
  2. 初始化，每个节点记录的在此区间内的元素数量是 0，接下来从数组的最后一位开始往前遍历，每次遍历，判断这个数落在哪个区间，那么那个区间的数量加一。
  3. 遇到 1，把它加入到线段树里，此时线段树里各个节点所统计的数量会发生变化。
  4. 当前所遇到的最小值就是 1。
  5. 把 6 加入到线段树里。
  6. 求比 6 小的数有多少个，即查询线段树，从 1 到 5 之间有多少个数。
  7. 从根节点开始查询。由于所要查询的区间是 1 到 5，无法包含根节点的区间 1 到 6，所以继续往下查询。
  8. 左边，区间 1 到 3 被完全包含在 1 到 5 之间，把该节点所统计好的数返回。
  9. 右边，区间 1 到 5 跟区间 4 到 6 有交叉，继续往下看，区间 4 到 5 完全被包含在 1 到 5 之间，所以可以马上返回，并把统计的数量相加。
  10. 最后得出，在当前位置，在 6 的右边比 6 小的数只有一个。

通过这样的方法，每次把当前的数用线段树进行个数统计，然后再计算出比它小的数即可。算法复杂度是 O(nlogm)。

参考

  • 《数据结构(C语言版)》 严魏敏、吴伟民著
  • 《数据结构(第3版)》 刘大有等著
  • 《搞定数据结构与算法》 苏勇