数据结构与算法 | 第五章：二叉树

本文参考网课为 数据结构与算法 ¹ 第五章二叉树，主讲人 张铭 、王腾蛟 、赵海燕 、宋国杰 、邹磊 、黄群。

本文使用IDE为 Clion，开发环境 C++14。

更新：2023 / 12 / 17

---

---

先回顾一下线性结构与非线性结构的主要区别：

• 线性结构
  线性结构中的元素满足线性关系，每个内部元素有且仅有一个前驱结点、一个后继结点。
• 非线性结构
  至少存在一个数据元素，具有两个或两个以上的前驱或者后继。
  根据前驱结点数目是否有限制，非线性结构可以进而分为树结构和图结构。
  • 树结构
    前驱唯一，后继不限

包含 n (n>=0) 个结点的有穷集合E，E上定义了一个满足以下条件关系r：

• 有且仅有一个称为树根（root）的结点e_r ∈ E，在关系r下没有前驱；
• 除结点 e_r 外，E中所有结点对于关系r来说都有且仅有一个前驱；
• 除结点 e_r 外，对任何结点 e ∈ E，都存在一个结点序列 e_r，e₁，…，e_s，使得e_r 就是树根，且 e_s = e，有序对<e_i-1，e_i> ∈ r (1 <= i <= s)；该结点序列称为从根到结点e的一条路径（path）

• 图结构
  前驱不限，后继不限

---

树

概念

术语

• 结点（ Node ）
  • 根结点（ root ）
    唯一没有前驱结点的结点
  • 父结点（ parent ）
    若 <e, e‘> ∈ r，则称 e 是 e’ 的父结点，e’ 是 e 的子结点
  • 子结点（ children ）
• 兄弟（ Sibling ）
  若 <e, e’>，<e, e’‘> ∈ r，则 e’ 和 e’’ 互称为兄弟
• 分支结点（ branch / internal node ）、叶结点（ leaf / external node ）
  根据结点是否有子结点，可以将结点区分为分支结点和叶结点。
  • 叶结点 / 外部节点 / 终端结点：没有子树的结点
  • 分支结点 / 内部结点 / 非终端结点
• 边（ edge ）
  两个结点组成的有序对 <e，e’>
• 路径（ path ）、路径长度
  • 根结点 e_r 外的 e，存在一条从根结点 e_r 到e的路径
  • 路径长度：构成路径的边的数目
• 祖先（ ancestor ）、后代（ desendant ）
  • 存在由 e_a 到 e_d 的路径，则称 e_a 为 e_d 的祖先，e_d 为 e_a 的子孙
• 结点的度数（ degree ）、层数（ levels ）
  • 结点度数：拥有子树的数目
  • 结点层数：根节点层数为0，其他结点所在层数为其父结点层数+1
• 树的深度（ depth ）、高度（ height ）
  • 树的深度：结点的最大层数
  • 树的高度：深度+1

以下面的树结构示例来进一步理解这些术语的含义：

A 为根结点（ root node ）
B 是 D和E的父结点（ parent node ），D和E是B的子结点（ children node ）
D 是E的兄弟结点（ sibling node ）
D、E、F、G 和 I 是叶结点（ external node 或者 leaf node ）
A、B、C、H 是分支结点（ internal node ）
C结点的度数（ degree ）是3
E结点的层数是2，I结点的层数是3
树的深度是3，高度是4

递归定义

树是包含 n（ n>=0 ）个结点的有限集合 T。
非空 T 满足：

• 有且仅有一个特别标出称作根的结点（e_r）
• e_r 之外结点被分成 m 个（m>=0）不相交的集合T₁，T₂，…，T_m，其中T_k（0<=k<=m）为树。T₁，T₂，…，T_m 称作根（e_r）的子树

例如，

A是根节点，BD、CEFGHI、JK分别为一颗子树。

只包含1个结点的树必然仅由根结点组成。
包含 n>1 个结点的树借助于少于n个结点的树来定义。
不包含任何结点的树称为空树。

分类

二叉树

一颗 二叉树 是由结点的有限集合来构成：

• 或为空的 二叉树
• 或由一个根结点和 1或者2颗 不相交的分别称作这个根的左子树（ left subtree ）和右子树（ right subtree ）的 二叉树 组成
  每个结点至多两颗子树，且有左右之分，不能随意交换
  即使结点只有一颗子树也须明确是左子树还是右子树

例如，

对于根结点A，BD是A的左子树，CEFGHI是A的右子树；
对于根结点C，EG是C的左子树，FHI是C的右子树；

基本形态

二叉树 拥有以下几种基本形态，

( c ) 右空 和 ( d ) 左空 是两颗不同的 二叉树，但作为 树 则是相同的。二叉树 的概念与术语与 树 的基本相同。

分类

满二叉树（ Full Binary Tree ）

一颗 二叉树 中的结点，要么为 叶结点，或恰有两颗非空子树，那么我们称这样的一颗 二叉树 为 满二叉树（ Full Binary Tree ）。

例如，

B、F、G、H、I均为叶结点
A、C、D、E都恰好有两个子结点，即满二叉树

完全二叉树（ Complete Binary Tree ）

一颗 二叉树 最多只有最下面两层的结点度数可以小于2，并且，最下面一层的结点都集中在该层最左边的若干位置上，那么我们称这样的一颗 二叉树 为 完全二叉树（ Complete Binary Tree ）。

例如，

ABCDEF是一颗 完全二叉树

再例如，

ABCDEFGHIJL不是一颗 完全二叉树，因为L没有集中到最左边的位置上。

完全二叉树 的特点如下：

• 叶结点只可能在层次最大的两层出现；
• 根结点到各结点的路径长度总和在具有同样数目结点的二叉树中达到了最小，即，任何一颗二叉树中根节点到各节点的最长路径一定不短于结点数目相同的完全二叉树中的路径长度；

扩充二叉树（ Extended Binary Tree ）

给定一颗 二叉树，我们可以通过替换该 二叉树 中的 空子树 为 空叶结点 来扩充成一颗 扩充二叉树：

• 对于不满的分支结点
  增加1个 空叶结点
• 对于叶结点
  增加2个 空叶结点

例如，

将1、4、7这3个原本度数为1的不满的分支结点在它相应的位置上扩充1个 空叶结点，将2、5、8、10这4个叶结点给扩充2个相应的 空叶结点，那么就得到了如上图所示的一个 扩充二叉树。

二叉树性质

结点数目与层次关系

性质1：非空二叉树的第 i（ i>=0 ）层至多有 2ⁱ 个结点

证明：

1. 归纳基础：i=0，结点数 1 = 2⁰；
2. 归纳假设：假设对于所有的 j（0<=j<=i），命题成立，即，j 层结点数至多有 2^j；
3. 归纳结论：对于 i = j+1，结点数至多为 2 * 2^j = 2^j+1

基于该性质，我们可以计算一个给定高度的 二叉树 中结点数目的范围，例如：

对于如上图所示的一个深度为3、高度为4的 二叉树，它的结点个数的取值范围在 4 ~ 15（2⁰+2¹+2²+2³）之间。

---

性质2：深度为k的二叉树至多有 2^k+1-1 个结点（ k>=0 ）

证明：假设第 i 层上的最大结点个数为 m_i，由性质1可知，深度为k的 二叉树 中最大的结点个数。

不同类型结点间关系

性质3：一颗 二叉树 中度为 0 的结点数目 n₀ 比度为2的结点数目 n₂多1，即 n₀ = n₂ + 1。

证明：n₀，n₁，n₂ 分别表示 n 个结点中度为0、1、2的结点数，则有 n = n0 + n1 + n2 （1）
若用e表示树的边数，则有 n=e+1（除了根结点以外，其他结点都有一条与父结点之间的边存在，所以我们有树中结点数目等于树的边数+1）
边均由度为1和2的结点射出，故有e=n1+2n2，即，
n = e + 1 = n1 + 2n2 + 1 （2）
由（1）和（2）得，
n0 + n1 + n2 = n1 + 2 * n2 + 1
即，n0 = n2 + 1

---

性质4：满二叉树定理：非空满二叉树的叶结点数目为其分支结点数+1。

证明：设 二叉树 结点数为n，其中叶结点数为m、分支结点数为b，则有
n（总结点数）= m（叶）+ b（分支） （1）
因为每个分支恰有2个子结点（满），故有2*b条边；n个结点，故
n - 1 = 2b （2）
所以，由（1）和（2）可以得到 n-1 = m+b-1 = 2b，即
m（叶）= b（分支）+1

---

性质5：满二叉树定理推论：一个非空二叉树的空子树数目等于其结点数+1。
证明：设二叉树为T，将其所有空子树替换为叶结点，所得的扩充满二叉树为T’，亦即，T的原有结点变为T’ 的分支结点。
根据满二叉树定理，T’ 的叶结点数目等于T的结点个数加1；每个新添加的叶结点对应T德一个空子树
所以，T中空子树数目等于T中结点数加1。

结点数目与深度/高度关系

性质6：具有n个结点的完全二叉树的高度和深度分别为 log₂(n+1) 和 log₂(n+1) - 1
证明：设其深度为k，则有
n = 2⁰ + 2¹ + 2^2 + … + 2^k-1 + m_k = 2^k - 1 + m_k （1）
故 2^k - 1 < n <= 2^k+1 -1 （2）
2^k < n+1 <= 2^k+1
k < log₂(n+1) <= k+1
所以 k = log₂(n+1) - 1

二叉树抽象数据类型

在明确了 二叉树 的逻辑结构和 二叉树 的性质后，我们可以来考虑 二叉树 上可以实施的运算的集合，以适用于不同应用的需求。

一般来说，二叉树 的运算有：

• 针对整棵树的运算
  • 初始化二叉树
  • 合并两颗二叉树
  • 遍历（周游）二叉树
• 围绕结点的运算
  • 访问某个节点的左子结点、右子结点、父结点
  • 访问结点存储的数据

抽象数据类型定义了二叉树基本操作的集合，在具体应用中可根据实际情况以此为基础进行适当的扩充/删减。
抽象数据类型定义的操作的具体实现与二叉树的存储相关。

二叉树结点抽象数据类型

二叉树 结点的抽象数据类型，包括这个结点的数据域，以及可以有适应于不同初始条件的结点的构造函数。

template <class T>
class BinaryTreeNode {
    friend class BinaryTreeNode<T>;                                             // 声明二叉树类为友元类
private:
    T info;                                                                     // 二叉树结点数据域
public:
    BinaryTreeNode();                                                           // 缺省构造函数
    BinaryTreeNode(const T &ele);                                               // 给定数据的构造
    BinaryTreeNode(const T &ele, BinaryTreeNode<T> *l, BinaryTreeNode<T> *r);   // 子树构造结点
    T value() const;                                                            // 返回当前结点数据
    BinaryTreeNode<T>* leftchild() const;                                       // 返回左子树
    BinaryTreeNode<T>* rightchild() const;                                      // 返回右子树
    BinaryTreeNode<T>* Parent();                                                // 返回父结点
    BinaryTreeNode<T>* LeftSibling();                                           // 返回左兄结点
    BinaryTreeNode<T>* RightSibling();                                          // 返回右兄结点
    BinaryTreeNode<T>& operator = (const BinaryTreeNode<T>& Node);              // 重载赋值操作符
    bool isLeaf() const;                                                        // 判断是否为叶结点
    void setLeftchild(BinaryTreeNode<T>*);                                      // 设置左子树
    void setRightchild(BinaryTreeNode<T>*);                                     // 设置右子树
    void setValue(const T& val);                                                // 设置数据域
};

二叉树抽象数据类型

template <class T>
class BinaryTree{
private:
    BinaryTreeNode<T>* root;                                                            // 二叉树根节点
public:
    BinaryTree(){root=NULL;};                                                           // 构造函数
    ~BinaryTree(){DeleteBinaryTree(root);};                                             // 析构函数
    bool isEmpty() const;                                                               // 判定二叉树是否为空树
    BinaryTreeNode<T>* Root(){return root;}                                             // 返回根结点

    void CreateTree(const T& info, BinaryTree<T>& leftTree, BinaryTree<T>& rightTree);  // 构造新树
    void PreOrder(BinaryTreeNode<T> *root);                                             // 前序遍历二叉树或其子树
    void InOrder(BinaryTreeNode<T> *root);                                              // 中序遍历二叉树或其子树
    void PostOrder(BinaryTreeNode<T> *root);                                            // 后序遍历二叉树或其子树
    void LevelOrder(BinaryTreeNode<T> *root);                                           // 按层次遍历二叉树或其子树
    void DeleteBinaryTree(BinaryTreeNode<T> *root);                                     // 删除二叉树或其子树
};

二叉树遍历

二叉树 的遍历也就是将非线性结构的 二叉树 线性化的过程，又成周游（ traversal ）。这代表着系统访问数据结构中的每个结点，使得每个结点恰好被访问且仅被访问到1次。
访问是指对结点进行期望的操作，具体地操作取决于应用的需求，譬如对二叉树结点数据成员进行读、写、改等操作。

二叉树 的遍历分为：

• 深度优先（ depth-first search / traversal，DFS / DFT）
  从一个结点出发，沿着分支向尽可能深的方向进行周游
• 广度优先（ breadth-first search / traversal，BFT / BFS ）
  按照结点的层次，从上到下，从左到右来进行周游

深度优先遍历

一颗 二叉树 由3部分组成：

• 根结点 t
• 根结点的左子树 L（ left child ）
• 根结点的右子树 R（ right child ）

通过变换根结点的遍历顺序，可以有以下3种方案：

• 前序遍历（ preorder traversal ）
  访问根结点 -> 前序遍历左子树 -> 谦虚遍历右子树
  t -> L -> R
• 中序遍历（ inorder traversal ）
  中序遍历左子树 -> 访问根节点 -> 中序遍历右子树
  L -> t -> R
• 后序遍历（ postorder traversal ）
  后序遍历左子树 -> 后序遍历右子树 -> 访问根结点
  L -> R -> t

以下面的 二叉树 为例，

1. 通过 前序遍历 得到的序列为 A、B、D、E、G、C、F、H、I
2. 通过 中序遍历 得到的序列为 D、B、G、E、A、C、H、F、I
3. 通过 后序遍历 得到的序列为 D、G、E、B、H、I、F、C、A

应用

表达式二叉树

以上面的 二叉树 为例，可以以3种不同的遍历方式得到表达同一表达式的不同序列：

1. 通过 前序遍历 得到的序列为 ÷-ab+cd，即波兰表示法
2. 通过 中序遍历 得到的序列为 (a-b)/(c+d)，即中缀表示
3. 通过 后序遍历 得到的序列为 ab-cd+÷，即逆波兰表示法

算法

实现 二叉树 深度优先遍历的方式有:

1. 递归算法
   算法简洁，且当前编译系统优化效率很好
2. 非递归算法
   适用于某些资源受限的应用环境
   但需要设置一个栈来记录尚未遍历的结点/子树，以备后续访问

递归算法

如果是 前序遍历，按照以下的递归算法进行遍历：

template <class T>
void BinaryTree<T>::DepthOrder(BinaryTreeNode<T>* root){
    if (root != NULL){                                      // 前序
        Visit(root);                                        
        DepthOrder(root->leftchild());                      // 递归访问左子树
        DepthOrder(root->rightchild());                     // 递归访问右子树
    }
}

如果是 中序遍历，按照以下的递归算法进行遍历：

template <class T>
void BinaryTree<T>::DepthOrder(BinaryTreeNode<T>* root){
    if (root != NULL){                                      // 中序
        DepthOrder(root->leftchild());                      // 递归访问左子树
        Visit(root);
        DepthOrder(root->rightchild());                     // 递归访问右子树
    }
}

如果是 后序遍历，按照以下的递归算法进行遍历：

template <class T>
void BinaryTree<T>::DepthOrder(BinaryTreeNode<T>* root){
    if (root != NULL){                                      // 后序
        DepthOrder(root->leftchild());                      // 递归访问左子树
        DepthOrder(root->rightchild());                     // 递归访问右子树
        Visit(root);
    }
}

非递归算法

前序遍历

1. 遇到一个结点，访问该结点，同时将其非空右子树的结点压栈；
2. 左路下降，遍历其左子树的结点；
3. 从栈顶弹出一个结点，访问该结点，并继续遍历其右子树的结点；

示例

以上面的二叉树为例，

以前序遍历的方式进行周游时，

1. 从根结点A开始，A的左、右子树非空，将A的右子树C压栈并继续访问A的左子树B；
   前序序列：A B
   栈内元素：C
   入栈序列：C
2. B的左子树非空、右子树为空，没有元素进栈并继续访问B的左子树D；
   前序序列：A B D
   栈内元素：C
   入栈序列：C
3. D的左、右子树均为空，没有元素进栈并从栈顶弹出C来继续访问；
   前序序列：A B D C
   栈内元素：
   入栈序列：C
4. C的左、右子树非空，将C的右子树F压栈并继续访问C的左子树E；
   前序序列：A B D C E
   栈内元素：F
   入栈序列：C F
5. E的左子树空、右子树非空，将E的右子树G压栈并从栈顶弹出G来继续访问；
   前序序列：A B D C E G
   栈内元素：F
   入栈序列：C F G
6. F的左右子树非空，将F的右子树I压栈并继续访问F的左子树H；
   前序序列：A B D C E G F H
   栈内元素：I
   入栈序列：C F G I
7. H的左右子树均为空，没有元素进栈并从栈顶弹出I；
   前序序列：A B D C E G F H I
   栈内元素：
   入栈序列：C F G I

此时栈为空，遍历结束。

用代码来实现以上描述，如下所示：

template <class T> void BinaryTree<T>::PreOrderWithoutRecursion(BinaryTreeNode<T> *root){
    using std::stack;                                                                       // 使用STL中的栈
    stack<BinaryTreeNode<T>* > aStack;
    BinaryTreeNode<T> *pointer = root;                                                      // 从根结点开始访问
    aStack.pull(NULL);                                                                      // 放入栈底监视哨
    while (pointer){                                                                        // 当pointer有值，或者！aStack.empty()
        Visit(pointer -> value());                                                          // 访问当前结点
        if (pointer -> rightchild()!=NULL)                                                  // 如果当前结点的右子树非空
            aStack.push(pointer->rightchild());                                             // 将右子树结点压栈
        if (pointer -> leftchild()!=NULL)                                                   // 如果左子树非空
            pointer = pointer -> leftchild();                                               // 左路下降，访问左子树结点
        else{                                                                               // 如果左子树为空
            pointer = aStack.top();
            aStack.pop();                                                                   // 栈顶元素弹出、退栈
        }
    }
}

中序遍历

1. 遇到一个结点，将其压栈，并遍历其左子树；
2. 从栈顶弹出该结点，并访问之；
3. 右路下降，遍历其右子树的结点；

示例

以上面的二叉树为例，

以中序遍历的方式进行周游时，

1. 从根结点A开始，将A压栈；
   中序序列：
   栈内元素：A
   入栈序列：A
2. A的左子树非空，左路下降、继续访问B，将B压栈；
   中序序列：
   栈内元素：A B
   入栈序列：A B
3. B的左子树非空，左路下降、继续访问D，将D压栈；
   中序序列：
   栈内元素：A B D
   入栈序列：A B D
4. D的左、右子树均为空，没有元素入栈并弹出栈顶元素D、B；
   中序序列：D B
   栈内元素：A
   入栈序列：A B D
5. B的右子树为空，弹出栈顶元素A；
   中序序列：D B A
   栈内元素：
   入栈序列：A B D
6. A的右子树非空，右路下降、继续访问C，将C压栈；
   中序序列：D B A
   栈内元素：C
   入栈序列：A B D C
7. C的左子树非空，左路下降、继续访问E，将E压栈；
   中序序列：D B A
   栈内元素：C E
   入栈序列：A B D C E
8. E的左子树为空、右子树非空，没有元素入栈并弹出栈顶元素；右路下降、继续访问G；
   中序序列：D B A E
   栈内元素：C G
   入栈序列：A B D C E G
9. G的左、右子树均为空，没有元素入栈并弹出栈顶元素G、C；
   中序序列：D B A E G C
   栈内元素：
   入栈序列：A B D C E G
10. C的右子树非空，右路下降、继续访问F，将F压栈；
    中序序列：D B A E G C
    栈内元素：F
    入栈序列：A B D C E G F
11. F的左子树非空，左路下降、继续访问H，将H压栈；
    中序序列：D B A E G C
    栈内元素：F H
    入栈序列：A B D C E G F H
12. H的左、右子树均为空，没有元素入栈并弹出栈顶元素H、F；
    中序序列：D B A E G C H F
    栈内元素：
    入栈序列：A B D C E G F H
13. F的右子树非空，右路下降、继续访问I，将I压栈；
    中序序列：D B A E G C H F
    栈内元素：I
    入栈序列：A B D C E G F H I
14. I的左、右子树均为空，没有元素入栈并连续弹出栈顶元素2次，第1次过后栈内已无元素可弹出，即结束。
    中序序列：D B A E G C H F I
    栈内元素：
    入栈序列：A B D C E G F H I

后序遍历

1. 遇到一个结点，将其压栈，并遍历其左子树；
2. 右路下降，遍历其右子树的结点；
3. 栈中的元素增加一个特征位，以区别栈顶弹出结点时是从其左子树（仍需遍历右子树），还是从右子树返回。

• L表示进入左子树并从其返回；
• R表示进入右子树并从其返回；
  访问栈顶元素并弹出；

示例

以上面的二叉树为例，

以后序遍历的方式进行周游时，

1. 从根结点A开始，将A标记为（A，L）并压栈；
   后序序列：
   栈内元素：（A，L）
   入栈序列：（A，L）
2. A的左子树非空，左路下降、继续访问B，将B标记为（B，L）并压栈；
   后序序列：
   栈内元素：（A，L）（B，L）
   入栈序列：（A，L）（B，L）
3. B的左子树非空，左路下降、继续访问D，将D标记为（D，L）并压栈；
   后序序列：
   栈内元素：（A，L）（B，L）（D，L）
   入栈序列：（A，L）（B，L）（D，L）
4. D的左子树为空，弹出栈顶元素（D，L）；此时还不能访问D，右路下降、继续访问D的右子树，将（D，R）压栈；D的右子树为空，弹出栈顶元素（D，R）；访问D；
   后序序列：D
   栈内元素：（A，L）（B，L）
   入栈序列：（A，L）（B，L）（D，L）（D，R）
5. 弹出栈顶元素（B，L），此时还不能访问B，右路下降、继续访问B的右子树，将（B，R）压栈；B的右子树为空，弹出栈顶元素（B，R）；访问B；
   后序序列：D B
   栈内元素：（A，L）
   入栈序列：（A，L）（B，L）（D，L）（D，R）（B，R）
6. 弹出栈顶元素（A，L），此时还不能访问A，右路下降、继续访问A的右子树，将（A，R）压栈；
   后序序列：D B
   栈内元素：（A，R）
   入栈序列：（A，L）（B，L）（D，L）（D，R）（B，R）（A，R）
7. A的右子树非空，将（C，L）压栈，左路下降、继续访问C的左子树；
   后序序列：D B
   栈内元素：（A，R）（C，L)
   入栈序列：（A，L）（B，L）（D，L）（D，R）（B，R）（A，R）（C，L）
8. C的左子树非空，左路下降、继续访问E，将E标记为（E，L）并压栈；E的左子树为空，弹出栈顶元素（E，L）；此时还不能访问E，右路下降，继续访问E的右子树，将（E，R）压栈；
   后序序列：D B
   栈内元素：（A，R）（C，L) （E，R）
   入栈序列：（A，L）（B，L）（D，L）（D，R）（B，R）（A，R）（C，L）(E，L) （E，R）
9. E的右子树非空，右路下降、继续访问G，将G标记为（G，L）并压栈；G的左子树为空，弹出栈顶元素（G，L）；此时还不能访问G，右路下降，继续访问G的右子树，将（G，R）压栈；G的右子树为空，弹出栈顶元素（G，R），访问G；E的右子树遍历完毕，弹出栈顶元素（E，R），访问E；
   后序序列：D B G E
   栈内元素：（A，R）（C，L)
   入栈序列：（A，L）（B，L）（D，L）（D，R）（B，R）（A，R）（C，L）(E，L) （E，R）（G，L）（G，R）
10. 弹出栈顶元素（C，L），此时不能访问C，右路下降、继续访问C的右子树，将（C，R）压栈；
    后序序列：D B G E
    栈内元素：（A，R）(C，R)
    入栈序列：（A，L）（B，L）（D，L）（D，R）（B，R）（A，R）（C，L）(E，L) （E，R）（G，L）（G，R）（C，R）
11. C的右子树非空，将（F，L）压栈，左路下降、继续访问F的左子树；
    后序序列：D B G E
    栈内元素：（A，R）(C，R)（F，L）
    入栈序列：（A，L）（B，L）（D，L）（D，R）（B，R）（A，R）（C，L）(E，L) （E，R）（G，L）（G，R）（C，R）（F，L）
12. F的左子树非空，左路下降、继续访问H，将H标记为（H，L）并压栈；H的左子树为空，弹出栈顶元素（H，L）；此时还不能访问H，右路下降，继续访问H的右子树，将（H，R）压栈；H的右子树为空，弹出栈顶元素（H，R）；访问H；
    后序序列：D B G E H
    栈内元素：（A，R）(C，R)（F，L）
    入栈序列：（A，L）（B，L）（D，L）（D，R）（B，R）（A，R）（C，L）(E，L) （E，R）（G，L）（G，R）（C，R）（F，L）（H，L）（H，R）
13. 弹出栈顶元素（F，L），此时还不能访问F，右路下降、继续访问F的右子树；将（F，R）压栈；
    后序序列：D B G E H
    栈内元素：（A，R）(C，R)（F，R）
    入栈序列：（A，L）（B，L）（D，L）（D，R）（B，R）（A，R）（C，L）(E，L) （E，R）（G，L）（G，R）（C，R）（F，L）（H，L）（H，R）（F，R）
14. F的右子树非空，右路下降、继续访问I，将I标记为（I，L）并压栈；I的左子树为空，弹出栈顶元素（I，L）；此时还不能访问I，右路下降，继续访问I的右子树，将（I，R）压栈；I的右子树为空，弹出栈顶元素（I，R），访问I；I的右子树遍历完毕，弹出栈顶元素（F，R），访问F；
    后序序列：D B G E H F
    栈内元素：（A，R）(C，R)
    入栈序列：（A，L）（B，L）（D，L）（D，R）（B，R）（A，R）（C，L）(E，L) （E，R）（G，L）（G，R）（C，R）（F，L）（H，L）（H，R）（F，R）（I，L）（I，R)
15. 弹出栈顶元素（C，R），访问C；
    后序序列：D B G E H F C
    栈内元素：（A，R）
    入栈序列：（A，L）（B，L）（D，L）（D，R）（B，R）（A，R）（C，L）(E，L) （E，R）（G，L）（G，R）（C，R）（F，L）（H，L）（H，R）（F，R）（I，L）（I，R)
16. 弹出栈顶元素（A，R），访问A；
    后序序列：D B G E H F C A
    栈内元素：
    入栈序列：（A，L）（B，L）（D，L）（D，R）（B，R）（A，R）（C，L）(E，L) （E，R）（G，L）（G，R）（C，R）（F，L）（H，L）（H，R）（F，R）（I，L）（I，R)

此时栈为空，遍历结束。

时间、空间代价分析

• 时间代价
  遍历具有n个结点的 二叉树 需要 O(n) 时间

  • 前序遍历 和 中序遍历 中，某些结点入栈 / 出栈一次，不超过 O(n)
  • 后序遍历 中，每个结点分别从左、右边各入栈 / 出栈一次 O(n)
    前提是，处理各节点的时间为常数

• 空间代价
  遍历过程中栈的最大容量与树的高度成正比

  • 最坏情况
    高度为n，所需空间复杂度为 O(n)
  • 最佳情况
    空间复杂度为 O(logn)

广度优先遍历

广度优先遍历 是从 二叉树 的第0层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。

时间、空间代价分析

• 时间代价
  每个结点都被访问且只被访问一次，时间代价为 O(n)

• 空间代价
  与树的最大宽度相关

  • 最坏情况
    O(n)
  • 最佳情况
    O(1)

二叉树存储

二叉树 的存储一般分为：

• 顺序存储
  用 数组 实现 完全二叉树
• 链式存储
  用 指针 实现 二叉树

根据应用的需要和 二叉树 的结构特点，我们可以采用不同的存储方式：

• 顺序存储
  当要求 二叉树 按紧凑结构存储，且在应用过程中二叉树的大小和形状很少发生剧烈变化时，可采用 顺序存储 方法
  • 所有结点按一定的次序顺序存储到一片事先申请的连续存储单元中
  • 适当安排结点的线性序列，使结点在序列中的相互位置反映出二叉树结构的部分信息
  • 在结点中附加一些其他的必要信息来反映整个结构

顺序存储

按照广度优先遍历的方式，即按层次顺序将一颗具有n个结点的 完全二叉树 的结点从 0 到 n-1 编号，得到结点的一个线性序列。如下所示：

从结点编号i可推知其父结点、子结点、兄弟结点的编号：

• 当2i+1<n时，其左子结点编号为2i+1，否则没有左子树；
• 当2i+2<n时，其右子结点编号为2i+2，否则没有右子树；
• 当0<i<n时 ，其父结点编号 (i-1) / 2；
• 当i为偶数且0<i<n时，其左兄结点编号为i-1，否则没有左兄；
• 当I为奇数且i+1<n时，其右弟结点编号为i+1，否则没有右弟；

完全二叉树 的层次结构足以反映其结构，按层次序列顺序存储，根据结点的存储位置可计算其左、右子结点、父节点、兄弟结点的存储地址。

完全二叉树 的 顺序存储，在存储结构上是线性的，但依然完整的反应了 二叉树 的逻辑结构。

链式存储

树结构最自然的存储方式是 链式存储，不同结点随机存储在内存空间中，结点间关系用指针表示。

结点的形式如下所示：

每个结点除存储结点本身的数据外，设置两个指针字段 left 和 right 分别存储其左子结点和右子结点的地址。若结点的某个子节点为空，则相应的指针应为空指针。

以下面的 二叉树 为例，

将上面的 二叉树 转换为如下所示的 二叉链表：

n 个结点的 二叉链表 有 n+1 个空指针。

链式存储 的优缺点如下：

• 优点
  运算方便，通过指针可直接访问相关结点
• 缺点
  空指针有 n+1 个，存储密度低、结构性开销大

向 BinbaryTreeNode 类中增加两个私有数据成员，如下所示：

private:                                    // 增加2个私有数据成员
    BinaryTreeNode<T> *left;                // 指向左子树的指针
    BinaryTreeNode<T> *right;               // 指向右子树的指针

template <class T> class BinaryTreeNode{
    friend class BinaryTreeNode<T>;         // 声明二叉树类为友元类
private:
    T info;                                 // 二叉树结点数据域
public:
    BinaryTreeNode();                       // 缺省构造函数
    BinaryTreeNode(const T & ele);          // 给定数据的构造
    BinaryTreeNode(const T & ele, BinaryTreeNode<T> *l, BinaryTreeNode<T> *r);
};

寻找父节点

以递归框架寻找

template<class T>
BinaryTreeNode<T>* BinaryTree<T>::
Parent(BinaryTreeNode<T> *rt, BinaryTreeNode<T> *current){
    BinaryTreeNode<T> *tmp;
    if (rt == NULL) return (NULL);                                      // 如果根结点是NULL，返回NULL
    if (current == rt -> leftchild() || current == rt -> rightchild())  // 如果当前结点为根结点的左/右子树，返回rt
        return rt;
    if ((tmp = Parent(rt -> leftchild, current) != NULL)
        return tmp;
    if ((tmp = Parent(rt -> rightchild, current) != NULL)
        return tmp;
    return NULL;
}

以非递归框架寻找

BinaryTreeNode<T>* BinaryTree<T>::Parent(BinaryTreeNode<T> *current){
    using std::stack;                                                                 // 使用STL中的栈
    stack<BinaryTreeNode<T>* > aStack;
    BinaryTreeNode<T> *pointer = root;
    aStack.push(NULL);                                                                // 栈底监视哨
    while (pointer){                                                                  // 当pointer存在，或者，!aStack.empty()时
        if (current == pointer -> leftchild() || current == pointer -> rightchild())  // 若current为pointer的子结点，则返回pointer
            return pointer;
        if (pointer -> rightchild() != NULL)                                          // 若右子结点非空，则右子结点入栈
            aStack.push(pointer -> rightchild());
        if (pointer -> leftchild() != NULL)                                           // 若左子结点非空，则左路下降
            pointer = pointer -> leftchild();
        else                                                                          // 若左子结点为空，弹出栈顶元素（退栈），poniter取栈顶
            pointer = aStack.top();aStack.pop();                                    
    }
}

对于经常要回溯父节点的应用，可以增加一个指向其父节点的指针域，成为如下所示的 三叉链表，以提供向上访问的能力：

虽然增加一个指针域，付出了空间的代价，但是可以使得经常要去找父节点的运算变得高效。

空间代价分析

α + γ = 1

• 存储密度 α
  α = $\frac{数据本身存储量}{整个结构占用的存储量}$
  表示数据结构存储的效率。当存储空间全部用于数据本身的存储结构，存储密度即为1。存储密度越大，空间利用率越高。
• 结构性开销 γ
  γ = $\frac{辅助结构存储量}{整个结构占用的存储量}$
  表示实现数据结构需要占用的辅助空间。并非用于存储数据，而是保存数据结构的逻辑特性或方便运算。

以 二叉链表 为例进行空间代价分析：
每个结点占用两个指针、一个数据域，假定数据域大小为d、指针域大小为p，整个结构由n个结点组成，那么总体空间大小是 (2p+d)n，总体结构性开销是 2pn。
γ = $\frac{2pn}{(2p+d)n}$，如果 p = d，γ = $\frac{2}{3}$。
为降低结构性开销，若只有叶结点存储数据、分支结点为内部结构，则开销取决于二叉树满的程度，越满则存储效率越高。

叶结点和分支结点差别较大，可区分叶结点存储和分支结点的存储。例如在叶结点存储操作数、在分支结点存储操作符：

采用不同的存储实现，不仅空间开销有差异，对于运算和操作的实现也不同。
具体应用中采取何种存储结构，除了二叉树的形态外，还应该考虑运算：

• 时间复杂度
• 空间复杂度
• 算法简洁性

应用

二叉树 的一个主要用途是提供对数据（包括索引）的快速检索，而一般二叉树对此并不具有性能优势。

二叉搜索树

概念

和上图右侧的树类似的树，我们称其为 二叉搜索树（ Binary Search Tree，简称 BST ）。它在中文里还有其他常用名称，例如 二叉查找树、二叉检索树、二叉排序树。

二叉搜索树 具有以下性质：

• 或为一颗空树
• 或任何一个检索码为 K 的结点满足：
  • 其左子树（若非空）任一结点的检索码均小于K
  • 其右子树（若非空）任一结点的检索码均大于或等于K
  • 其左、右子树分别为二叉搜索树
• 其中序序列为按检索码值从小到大的有序序列
  
  以中序序列遍历上面的 二叉树，可以得到一个有序序列 15 17 18 22 35 51 60 88 93

操作

对于 二叉搜索树，常用的操作有 检索、插入（ 生成 ）、删除。

所有的操作都围绕 二叉搜索树 的性质，并保持相应的性质。操作的效率取决于树的高度。

检索

假定待检索的检索码为 K，

• 从根结点开始，若根结点检索码为 K，则检索成功并结束；否则，则继续：
  • 若 K 小于根结点的值，则只检索左子树
  • 若 K 大于根结点的值，则只检索右子树

如此，一直持续到 K 被找到，或者，遇上叶结点仍没发现 K，则检索失败，说明不存在满足条件的结点。

示例

1. 查找检索码为 35 的结点
   从根结点 35 开始，根结点检索码为 35，检索成功并结束。
2. 查找检索码为 19 的结点

• 从根结点 35 开始，根结点 35 和 检索码 19 不一致且检索码 19 比根结点 35 小，则继续检索左子树，即以 16 为根结点的左子树
• 检索码 19 比根结点 16 大，则继续检索右子树，即以 19 为根结点的右子树。根结点 19 同检索码 19 一致，检索成功并结束。

3. 查找检索码为 40 的结点

• 从根结点 35 开始，根结点 35 和 检索码 40 不一致且检索码 40 比根结点 35 大，则继续检索右子树，即以 60 为根结点的右子树
• 检索码 40 比根结点 60 小，则继续检索左子树，即以 51 为根结点的左子树
• 以 51 为根结点的左子树为空，检索失败

时间、空间代价分析

检索的基本操作是比较。每次比较，只需要检索2个子树之一。每比较1次，树的高度降低1。因此，检索代价是 O(h)，h 是树高。

插入

插入 操作应保证结点插入后仍保持 BST 性质，即，BST 的不变量和中序有序性。

假定待插入的检索码为 K，

• 从根结点开始，若根结点检索码为空，则将 K 结点作为根结点插入，操作结束
  • 若 K 小于根结点的值，将其插入左子树
  • 若 K 大于根结点的值，将其插入右子树

示例

1. 插入检索码为 17 的结点

• 从根结点 35 开始，检索码 17 小于根结点 35，只能将检索码 17 插入根结点为 16 的左子树中
• 检索码 17 比根结点 16 大，只能将检索码 17 插入根结点为 19 的右子树中
• 检索码 17 比根结点 19 小，且根结点 19 的左子树为空，因此插入 19 的左子树，如下所示：

时间、空间代价分析

插入操作的前提是一次失败的检索，然后将新结点作为叶结点插入，改动相关特定结点的空指针即可。

其时间复杂度与根到插入位置的路径长度相关，而这个路径长度是插入结点落在先前那次失败检索时外部结点所在的层次。在最坏的情况下，这个路径长度与树的高度成正比。

删除

删除 操作应保证结点删除后仍保持 BST 性质，且树高变化较小。

首先检索到待删除结点 H，再根据其在树中所处位置分情况处理：

• 叶结点
  • 直接删除 H，并将其父结点 J 的相应指针位置置空
    
• 只有1个子结点的结点
  • 删除 H，并以 H 的子结点代替 H 原有的位置

• 有2个子结点的结点
  • 删除 H，并以 H 的左子树中最大的结点或者右子树中最小的结点来替换 H 原有的位置

示例

假设要删除 G，G 的左右子树均不为空，即符合第3种情况。
G 的右子树中最小的结点为 H，H 符合第2种情况，将 H 替换到 G 的位置，H 的右子树结点 I 替换到 H 的位置。

时间、空间代价分析

删除操作需要：

• 先检索到待删除结点的位置，比较的次数是被删结点所在的层次+1
• 需要根据情况需要，寻找待删除结点的后继，即查找替代结点，而查找的层次同待删除结点的子树的高度相关

以上两步的检索次数加起来是不会超过整个二叉搜索树的高度的。所以删除的时间代价是 O(h)，同树高 h 成正比。

其时间复杂度与根到插入位置的路径长度相关，而这个路径长度是插入结点落在先前那次失败检索时外部结点所在的层次。在最坏的情况下，这个路径长度与树的高度成正比。

堆与优先队列

概念

满足以下几种特性的二叉树：

• 在结构上是一颗 完全二叉树
• 任一结点的值小于或等于其子结点的值
• 根结点存储着树中所有结点的最小值

我们将它称为 最小值堆（ min-heap ）。如上图所示。

堆 是什么？——

• 从逻辑角度看，堆 是一种树型结构。
  • 一个 完全二叉树 的层次序列，可采用顺序数组表示
• 堆局部有序，堆不唯一
  • 结点的值与其子结点的值之间存在某种约束
  • 堆中任一结点与其兄弟之间没有约束
  • 最小堆 并非 BST 那样实现关键码的完全排序，而是局部有序，只有父结点的大小关系可以确定

堆是基于树的满足一定约束的重要数据结构，存在许多变体：二项式堆、斐波那契堆。
二叉树所表示的二叉堆是常用的一种堆，由于完全二叉树良好的性质，常采用数组来存储堆。

堆的基本操作均依赖于两个重要的函数 ShiftUp 和 ShiftDown。

• 堆的删除操作根据被删元素的位置和大小进行 ShiftUp 或 ShiftDown
• 堆的插入操作在堆尾插入新元素并通过 ShiftUp 进行调整

构建具有N个结点的堆的时间复杂度为 O(N)。
堆的深度为 logN，插入、删除元素的平均时间代价和最差时间代价都是 O(logN)
适合需要经常查找最小值、又经常增删数据的场景。但是，查找任意值的效率不高，因为往往需要遍历整棵树后才知道它在哪儿。

定义

template <class T>                          // 最小堆 ADT 定义
class MinHeap{
private:
    T* heapArray;                           // 存放堆数据的数组
    int CurrentSize;                        // 当前堆中元素数目
    int MaxSize;                            // 堆所能容纳的最大元素数目
    void BuildHeap();                       // 建堆函数
public:
    MinHeap(const int n);                   // 构造函数，n为最大元素数目
    virtual ~MinHeap(){delete []heapArray;};// 析构函数
    bool isLeaf(int pos) const;             // 若为叶结点，返回TRUE
    int leftchild(int pos) const;           // 返回左子结点位置
    int rightchild(int pos) const;          // 返回右子结点位置
    int parent(int pos) const;              // 返回父结点位置
    void ShiftDown(int left);               // 筛选法函数，参数left表示开始处理的数组下标
    void ShiftUp(int pos);                  // 从pos开始向上调整序列为堆
    bool Remove(int pos, T&node);           // 删除给定下标的元素node
    bool Insert(const T& newNode);          // 插入新元素newNode
    T& RemoveMin();                         // 删除堆顶最小值
};

建堆

筛选法

理论

如何建 堆 ？——

1. 筛选法
   将 n 个关键码组织到一维数组中，

• 可能整体并不满足堆的特性
• 以叶结点为根的子树都已满足堆的特性，亦即，当 i>=n/2 时，以关键码 K_i 为根的子树已为堆
• 从最后一个分支结点 i = n/2 - 1 开始，采用 shiftdown 从右向左、自底向上将以各个分支结点为根的子树调整成堆，直到树根为止

以下面的二叉树为例，

该二叉树存在8个结点，编号从0到7。

1. 编号大于 8/2-1=3，及编号大于等于4的这些结点，例如94、16、5、68，均是叶结点，都已经满足 堆 的性质。
2. 编号3的结点23，同其子结点68进行比较，23<68，满足 堆 的性质

3. 编号2的结点71，同其子结点16、05进行比较，71>16，71>5

16>5，将71和5进行交换，得到下面的结构：

以新编号2的结点5为根结点的一个二叉树结构已经被调整成 堆

4. 编号1的结点73，同其子结点23、94进行比较，73>23，73<94

73>23，将73和23进行交换，得到下面的结构：

新编号3的结点73，同其子结点68进行比较，73>68，将73和68进行交换，得到下面的结构：

以新编号1的结点23为根结点的一个二叉树结构已经被调整成 堆

5. 编号0的结点72，同其子结点23、5进行比较，72>23，72>5，

23>5，将72和5进行交换，得到下面的结构：

新编号2的结点72，同其子结点16、71进行比较，72>16，72>71，16>71，将72和16进行交换，得到下面的结构：

以新编号2的结点16为根结点的一个二叉树结构已经被调整成 堆

至此，原始的二叉树被调整为 最小堆 。

代码实现

如果使用代码来实现上述的 shiftdown 操作，

template <class T> 
void MinHeap<T>::ShiftDown(int position){
    int i = position;                                               // 指向父结点的指针
    int j = 2*i + 1;                                                // 指向关键值较小的子结点的指针
    T temp = heapArray[i];                                          // 使用temp来保存父结点的关键值

    while (j<CurrentSize){
        if ((j<CurrentSize-1) && (heapArray[j] > heapArray[j+1]))   // 如果编号j的结点的关键值小于编号j+1的结点的关键值
            j++;                                                    // j下移，j指向j+1
        if (temp > heapArray[j]){                                   // 如果父结点的关键值大于编号j的结点的关键值
            heapArray[i] = heapArray[j];                            // 交换父结点和编号j的结点
            i = j;
            j = 2*j+1;                                              // 向下继续
        }
        else break;                                                 // 调整结束，退出while循环
    }
    heapArray[i] = temp;
}

时间代价分析

使用 shiftdown 的时间代价分析如下：

• 基本操作包括比较和交换。
  比较需要判断子结点的大小，以及，结点是否需要筛选，即需要比较2次。
  交换需要1次，在最差的情况下每层都需要调整。
• 1个N个结点的完全二叉树，其高度是 log(N+1)。每循环一次就把目标结点下移一层，故循环最多为 log(N+1) 次。

所以，最差的情况下，shiftdown 的时间代价为 O(logN)。

---

构建具有N个结点的堆的时间代价分析如下：
以下面的完全二叉树为例，

一个N个结点的完全二叉树，若同时为满二叉树，则筛选的层数达到最大，此时有 N = 2^d - 1 => d = log(N+1)

第 k 层有至多 2^k 个结点，且第k层离叶结点的距离为 d-k-1层。

构建具有N个结点的堆需要的比较次数为：

最差的情况下，2次比较需要1次交换，所以最大交换次数为 n-logn
因此，构建具有N个结点的堆的时间复杂度为 O(N)。

堆的相关操作

插入

理论

以向下面的二叉树插入元素12为例说明如何进行 插入 操作：

1. 将新元素12插入最末端，尽最大程度降低对其他原有元素的影响，形成下面的结构：

2. 在插入新元素12后，它与同层的叶结点和父结点未必满足 堆 的性质。此时，需要同其父结点进行比较，36>12，故交换36和12、将12 shiftup 放至根结点的位置上，形成下面的结构：

3. 以此类推，逐步 shiftup，最终形成下面的结构：

代码实现

如果使用代码来实现上述的 shifup 和插入操作，

template <class T>
void MinHeap<T>::ShiftUp(int position){
    int temppos = position;                                         // 从position向上开始调整，使序列成为堆

    T temp = heapArray[temppos];                                    // 使用temp保存temppos结点

    while ((temppos > 0) && (heapArray[parent(temppos)] > temp)){
        heapArray[temppos] = heapArray[parent(temppos)];            // 交换temppos和其父结点
        temppos = parent(temppos);                                  // 交换temppos和其父结点的指针
    }
    heapArray[temppos] = temp;                                      // 最终temppos结点的关键值仍为temp
}

template <class T>
bool MinHeap<T>::Insert(const T & newNode){                         // 向堆中插入新元素newNode
    if (CurrentSize == MaxSize)                                     // 堆空间已满
        return false;
    heapArray[CurrentSize] = newNode;                               // 将新元素添加到最后
    ShiftUp(CurrentSize);                                           // 向上调整
    CurrentSize ++;
}

时间代价分析

构建具有N个结点的堆的时间复杂度为 O(N)。

堆的深度为 logN
插入、删除元素的平均时间代价和最差时间代价都是 O(logN)

删除

删除根结点后须维护和保持 堆 的特性。

理论

以下面的二叉树为例，对如何删除根结点元素进行说明：

1. 删除根结点5，整个堆的规模减1，形成下面的结构：

将最后1个元素45放到根结点上作为替代，如下所示：

但是，这时候整个二叉树结构未必再满足 堆 的特性。

2. 以新根结点45和其子结点进行比较，45<63，45>16，将45和16交换，16成为新的根结点，形成下面的结构：

以此类推，45>36，45>40，36<40，将45和36交换，形成下面的结构：

整个过程可能需要从树根一直筛到树叶，因此效率同树的高度成正比，即耗时 O(logN)。

---

再以下面的二叉树为例，对如何删除树上的元素进行说明：

1. 删除结点68，整个堆的规模减1；将最后1个元素45放到被删除结点上作为替代，形成下面的结构：

2. 以新结点45和其2个子结点进行比较，45<73 且 45<120，满足堆的特质；继续以新结点45和其父节点进行比较，63>45，将63和45交换，ShiftUp，63成为新结点，形成下面的结构：

此时，树上的各个节点满足 最小堆 的特性。至此，调整完毕。

代码实现

如果使用代码来实现删除根结点的操作，

template <class T> T MinHeap<T>::RemoveRoot(){
    if (CurrentSize == 0) exit(1);                  // 如果MinHeap的size是0，退出；

    Item tmpItem = heapArray[0];                    // 使用tmpItem保存heapArray的第0个结点;
    heapArray[0] = heapArray[CurrentSize - 1];      // 将最后一个结点和根结点进行交换
    heapArray[CurrentSize - 1] = tmpItem;

    CurrentSize --;                                 // 删除新最后1个结点，即，旧根结点
    ShiftDown(0);                                   // 将根结点shift down
    return tmpItem;
}

如果使用代码来实现删除树上某结点的操作，

template <class T>
bool MinHeap<T>::Remove(int pos, T& node){
    if ((pos<0) || (pos>=CurrentSize))              // 如果pos<0或大于树中结点的个数，非法
        return false;
    T temp = heapArray[pos];                        // 使用temp保存树上的第pos个结点
    heapArrayp[pos] = heapArray[--CurrentSize];     // 将树上的第pos个结点和最后一个结点进行交换
    if (heapArray[parent(pos)]) > heapArray[pos]    // 如果新第pos个结点的父结点比其大
        ShiftUp(pos);                               // 将新第pos个结点ShiftUp
    else ShiftDown(pos);                            // 否则，将新第pos个结点ShiftDown
    node = temp;
    return true;
}

时间代价分析

构建具有N个结点的堆的时间复杂度为 O(N)。

堆的深度为 logN
插入、删除元素的平均时间代价和最差时间代价都是 O(logN)

堆的应用

1. 堆排序
2. 优先队列（ Priority Queue ）
   2.1 根据需要释放具有最小 / 最大值的对象
   2.2 最大树、左高树（ HBLT、WBLT、maxWBLT ）
   2.3 改变已存储于优先队列中对象的优先权
   2.3.1 辅助数据结构帮助找到对象

Huffman树及其应用

编码

在程序设计以及数据通信领域，常常需要给某些给定字符集进行编码。编码是建立字符集与计算机或通信的数字系统之间的对应关系。也就是说，采用一组无歧义的规则将字符集中每个字符编码为唯一可标识的代码串。

一般编码有：

• 定长编码（ fixed-length coding scheme ）
  • 所有字符的编码长度均相同，编码一个具有n个字符的字符集需要 log₂n位。
    例如，ASCII码就是一种定长编码（ 8位 ）
  • 若字符集中每个字符使用频率大致相同，定长编码的空间效率最高
  • 具有简单、解码容易的优点
• 不等长编码（ variable-length coding scheme ）
  • 根据字符出现频率编码。常出现字符的编码较短，使用频率低的字符编码较长。
  • 不等长编码是文件压缩技术的核心。数据压缩既能节省磁盘空间，又能提高传输速度。
  • 任何一个字符的编码都不能是另外一个字符编码的前缀。
    否则容易造成歧义。
    例如，将字符集 {Z，K，F，C，U，D，L，E} 编码为 {Z(0)，K(0)，F(1)，C(01)，U(10)，D(11)，L(000)，E(001)}，“0001110” 可解码为 “ZZZDZ”、“LDZ” 或者 “FCU”。
• 前缀编码
  • 任何一个字符的编码都不能是另外一个字符编码的前缀。
    前缀特性保证了代码串被解码时，不会出现歧义。
    例如，将字符集 {Z，K，F，C，U，D，L，E} 编码为 {Z(111100)，K(111101)，F(11111)，C(1110)，U(100)，D(101)，L(110)，E(0)} 为一种前缀编码，“000110” 可解码为 “EEEL”。

可以用二叉树来设计和表示前缀编码。约定叶结点代表字符，一个结点的左分支标记 ‘0’，右分支标记 ‘1’，这样的话，根结点到叶结点的路径上所有分支标记所组成的代码串作为该叶结点所代表字符的编码。

这样的编码方式得到的一定是前缀编码。为什么呢？因为从根到一个叶结点的路径肯定不可能是根到另外一个叶结点路径的前缀，这是由二叉树的结构特性所保证的。同时，进行不等长编码的初衷是要提高空间的利用率。

如何保证这样的编码树所得到的编码总长度最小？通过 Huffman算法。

通过下面的例子来了解编码总长的概念，

上面有三颗具有4个外部结点的二叉树，相应的权值分别为6，2，3，4。
（a）、（b）、（c）三种形态的编码总长为其带权外部路径长度。

1. 对于（a）来说，它的4个结点的路径长度一样，都是2，编码总长 = 6x2 + 2x2 + 3x2 + 4x2 = 30。
2. 对于（b）来说，它的4个结点不等长。编码总长 = 6x2 + 2x3 + 3x3 + 4x1 = 31。
3. 对于（c）来说，它的4个结点不等长。编码总长 = 6x1 + 2x3 + 3x3 + 4x2 = 29。
   在 a）、（b）、（c）中（c）的编码总长最短。

Huffman编码

Huffman编码其实就是对一个待编码的字符集D={d₀，…，d_n-1}，D中各种字符的出现频率为W={w₀，…，w_n-1}，对字符集D进行二进制编码，使得通信编码总长最短，且d_i 的编码不是d_j编码的前缀。反之亦然。

Huffman编码的基本思想是，将d_i作为外部结点，w_i为外部结点的权，构造具有最小带权外部路径长度的扩充二叉树。也就是说，Huffman树是一个具有n个外部结点的扩充二叉树：

• 每个外部结点d_i有一个与之对应的权w_i
• 这个扩充二叉树的带权外部路径长度总和最小，也就是，权越大的叶结点离根越近。

构建一个Huffman树的步骤为：

1. 将待编码字符集中的字符按照 “权”（例如，频率）值组成一个有序的序列
2. 取走当前序列里 “权” 值最小的两个字符，将其标记为Huffman树的叶结点，并将这两个叶结点作为一个新生成分支结点的两个子结点，将该分支结点的权作为两个叶结点的权之和；将所得子树的 “权” 放回序列中适当位置，保持 “权” 的有序性
3. 重复上述步骤，直至序列中只剩一个元素，那么Huffman树建立完毕

以下面的示例为例对如何构建Huffman树进行说明，

以上是13个待编码的字符按照权值的有序排列，可构成下面的Huffman树，在这样的一棵树上，把每个结点到它的左子结点的边标记为0、到它的右子结点的边标记为1。那么将从根到叶结点的路径上的0、1标记组成该叶结点所代表字符的编码，如下所示：


出现频率越大的字符，其编码越短。

定义

template <class T>
HuffmanTree <T>::HuffmanTree(T weight[], int n){
    MinHeap<HuffmanTreeNode<T> heap(n)>;                                    // 最小值堆
    HuffmanTreeNode<T> *parent, firstchild, secondchild;
    HuffmanTreeNode<T> *NodeList = new HuffmanTreeNode<T>[n];
    for (int i=0; i<n; i++){                                                // 初始化
        NodeList[i].info = weight[i]
        NodeList[i].parent = NodeList[i].left = NodeList[i].right = NULL;
        heap.Insert(NodeList[i]);                                           // 向堆中添加元素
    }
    for (i=0; i<n-1; i++){                                                  // 通过n-1次合并 建立Huffman树
        parent = new HuffmanTreeNode<T>;                                    // 申请一个分支结点
        firstchild = heap.RemoveMin();                                      // 选择权值最小的结点
        secondchild = heap.RemoveMin();                                     // 选择权值次小的结点
        MergeTree(firstchild, secondchild, parent)                          // 将权值最小的两棵树合并到parent树
        heap.Insert(*parent);                                               // 把parent插入到堆中去
        root = parent;                                                      // Huffman树的根结点赋值
    }
    delete [] NodeList;
};

Huffman解码

采用Huffman算法构造的扩充二叉树即可编码字符集，也用来解码 / 译码二进制代码串。

译码与编码过程相逆：

• 从树的根结点开始
  • 沿0下降到左分支，沿1下降到右分支
    直到碰到一个叶结点，译出了一个字符
• 连续译码
  • 回到树根
  • 从二进制代码串中的下一位开始继续译码

以下面的示例为例对如何译码Huffman树进行说明，

“111 101110” 即 “d₁₂d₂”。

应用

Huffman编码适合于：

• 字符频率不等、差别较大的字符集
• 不同的频率分布会有不同饿压缩比率
• 大多数商业压缩软件都是采用几种编码方式以应对各种类型的文件
  比如zip压缩就是LZ777与Huffman结合
• 组织在外排序的时候归并顺串的时候的归并树，以优化归并趟数，来减少IO的读盘次数，从而提高我们的外排效率

正确性证明

引理

引理：
一颗含有两个以上结点的Huffman树中，使用频率最小的两个字符是兄弟结点，而且其深度不比树中其他任何叶结点浅。

证明：
记使用频率最低的两个字符为 y1 和 y2，y1和y2的父结点为y
假设x1和x2是最深的结点，x1和x2的父结点为x，y一定会有比x更大的 “权”，否则会选择y而不是x作为结点v的子结点。
但是，由于y1和y2是频率最小的字符，所以不可能出现y的权值比x权值还小的情况。

定理

定理：
对于给定的一组字符，函数Huffman Tree实现了最小外部路径权重。

证明：
对于字符个数n，可归纳如下：

• 归纳基础
  令n=2，Huffman树一定有最小外部路径权重
  • 只可能有成镜面对称的两种树
  • 两种树的叶结点加权路径长度相等
• 归纳假设
  假设由函数HuffmanTree产生的具有n-1个叶结点的Huffman树有最小外部路径权重
• 归纳步骤
  • 设一颗由函数HuffmanTree产生的树T有n个叶结点，n>2，并假设字符的 “权”，w₀ <= w₁ <= … <= w_n-1
    • 记V是频率为 w₀ 和 w₁ 的两个字符的父结点。据引理，它们已是树T中最深的结点
    • T中结点V换为一个叶结点V‘（权等于 w₀+w₁）得到另一棵树T‘
  • 根据归纳假设，T’ 具有最小的外部路径长度，将V‘展开为V(w₀+w₁)，T’ 还原为 T，则T也应有最小的外部路径长度

因此，根据归纳原理，定理成立。

编码效率

Huffman编码的空间效率评判指标是字符的平均编码长度。

各字符的编码长度 c_i 乘以其出现概率 p_i，即：
c₀p₀ + c₁p₁ + … + c_n-1p_n-1
或者，
f_i 表示第i个字符的出现频率，f_T表示所有字符出现的总次数
（c₀f₀ + c₁f₁ + … + c_n-1f_n-1）/ f_T

以下面的Huffman树为例说明Huffman的编码效率：

上面的Huffman树的编码的平均长度是，
(3*(19+23+29+31+31+47)) + 4*(11+13+17）+ 4*(11+13+17) + 57 + 65 + 7*(2+3)) / 238 = 3.38

如果将这13个字符进行等长编码，则每个字符的编码平均长度为 log13 = 4位。
然而将这13个字符进行Huffman编码，每个字符的编码平均长度为3.38位。
比起等长编码，Huffman编码只需要等长编码 3.38 / 4 = 84% 的空间。

再以下面的示例为例体会Huffman的编码效率：
如果存在一个100，000个字符组成的文件，这100，000个字符有6种字符，且这6种字符的出现频率差异较大，如下所示：

224，000 / 300，000 = 74 %
使用不等长编码可以节省 26% 的空间。

---

参考链接

---

1. 数据结构与算法 ??