树的抽象类

树是一种递归结构：一个结点可以有若干子树，而每棵子树本身又是一棵树。和线性表相比，树不再只有唯一的前驱/后继关系，而是体现层次关系，例如文件目录、组织结构、表达式语法树等。抽象类中的 root、parent、child 等接口描述的是这种层次关系，而不是具体采用数组还是指针存储。

1
2
3
4
5
6
7
8
9
10
11
template<class T>
class tree {
public:
    virtual void clear() = 0;
    virtual bool isEmpty() const = 0;
    virtual T root(T flag) const = 0; //非空，返回根节点；空树，返回flag
    virtual T parent(T x, T flag) const = 0;
    virtual T child(T x, int i, T flag) const = 0;
    virtual void remove(T x, int i) = 0;
    virtual void traverse() const = 0;
};

二叉树

二叉树是最常用的树形结构之一，因为每个结点最多只有左、右两个孩子，递归定义简单，代码实现也相对规整。后续的二叉查找树、堆、哈夫曼树等结构，都可以看作在二叉树上额外增加不同约束：查找树增加有序性，堆增加父子优先级关系，哈夫曼树增加带权路径长度最小化目标。

基本定义

  1. 二叉树（Binary Tree）是结点的有限集合，它或者为空，或者由一个根结点及两棵互不相交的左、右子树构成，而其左、右子树又都是二叉树。
  2. 注意：二叉树必须严格区分左右子树。即使只有一棵子树，也要说明它是左子树还是右子树。交换一棵二叉树的左右子树后得到的是另一棵二叉树。
  3. 二叉树和有序树是不同的概念。
  4. 树和二叉树都是树型结构。二叉树不是一种特殊的树。二叉树可以为空。树不能为空。

满二叉树

  • 一棵高度为 kk 并具有 2k−12^k - 1 个结点的二叉树称为满二叉树。
  • 一棵二叉树中任意一层的结点个数都达到了最大值。

满二叉树强调“每一层都填满”，因此结点数和高度之间有非常紧的关系。只要知道高度，就能直接推出结点总数；反过来也能通过结点数判断高度。这类结构常作为复杂度分析中的理想情况。

完全二叉树

在满二叉树的基础上，最后一层的结点可以不满，但必须从左到右依次排列。

  • 所有叶结点都出现在最低的两层上。
  • 对任意结点，如果其右子树高度为 kk，则其左子树高度为 kk 或 k+1k + 1。

完全二叉树强调“除了最后一层外尽量填满，最后一层从左向右填”。这个性质使它可以用数组紧凑存储，并通过下标直接推导父子关系，因此二叉堆会要求底层树形必须是完全二叉树。

二叉树性质

  1. 一棵非空二叉树的第 ii 层上最多有 2i−12^{i - 1} 个结点（i≥1i \ge 1）。
  2. 一棵高度为 kk 的二叉树最多有 2k−12^k - 1 个结点。
  3. 对于一棵非空二叉树，如果叶子结点数为 n0n_0，度数（子结点的个数）为 22 的结点数为 n2n_2，则有：

n0=n2+1n_0 = n_2 + 1

  1. 结论推广：对于一棵非空 KK 叉树，如果叶子结点数为 n0n_0，度数为 ii 的结点数为 nin_i，则有：

n0=1+∑i=2K(i−1)nin_0 = 1 + \sum_{i = 2}^{K}(i - 1)n_i

  1. 具有 nn 个结点的完全二叉树的高度：

k=⌊log⁡2n⌋+1k = \lfloor \log_2 n \rfloor + 1

二叉树抽象类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<class T>
class bTree {
public:
    virtual void clear() = 0;
    virtual bool isEmpty() const = 0;
    virtual T Root(T flag) const = 0;
    virtual T parent(T x, T flag) const = 0;
    virtual T lchild(T x, T flag) const = 0;
    virtual T rchild(T x, T flag) const = 0;
    virtual void delLeft(T x) = 0;
    virtual void delRight(T x) = 0;
    virtual void preOrder() const = 0;
    virtual void midOrder() const = 0;
    virtual void postOrder() const= 0;
    virtual void levelOrder() const = 0;
};

二叉树的遍历

  1. 前序遍历

如果二叉树为空，则操作为空，否则：

  • 访问根结点
  • 前序遍历左子树
  • 前序遍历右子树
  1. 中序遍历

如果二叉树为空，则操作为空，否则：

  • 中序遍历左子树
  • 访问根结点
  • 中序遍历右子树
  1. 后序遍历

如果二叉树为空，则操作为空，否则：

  • 后序遍历左子树
  • 后序遍历右子树
  • 访问根结点

Tip:根据前序序列+ 中序序列可以唯一确定一棵二叉树。根据后序序列+ 中序序列也可以唯一确定一棵二叉树。

三种深度优先遍历的差别只在“访问根结点”的时机：前序是先访问根，中序是夹在左、右子树之间，后序是最后访问根。写代码时递归框架几乎完全一致，真正改变的只有 cout << t->data 放在哪一行。层次遍历则完全不同，它不是沿着一条路径深入，而是借助队列按一层一层的顺序访问。

二叉树的类定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
template<class T>
class binaryTree : public bTree<T> {
    friend void printTree(const binaryTree &t, T flag);
private:
struct Node { //二叉树结点
    Node *left , *right ; // 左、右孩子指针
    T data;               // 结点保存的数据
    Node() : left(NULL), right(NULL) { }
    Node(T item, Node *L = NULL, Node * R =NULL ) :
    data(item), left(L), right(R) {}
    ~Node() {}
};
    Node *root;
public:
    binaryTree() : root(NULL) {}
    binaryTree(T x) { root = new Node(x); }
    ~binaryTree();
    void clear() ;//删除整棵树
    bool isEmpty() const;
    T Root(T flag) const;
    T lchild(T x, T flag) const;
    T rchild(T x, T flag) const;
    void delLeft(T x) ;
    void delRight(T x);
    void preOrder() const;//遍历整棵二叉树 （包裹函数，下同）
    void midOrder() const;
    void postOrder() const;
    void levelOrder() const;
    void createTree(T flag);//输入一颗二叉树
private:
    Node *find(T x, Node *t ) const;//t为当前根
    void clear(Node *&t) ;
    int count(Node *t) const;
    int height(Node *t) const;
    void preOrder(Node *t) const;
    void midOrder(Node *t) const;
    void postOrder(Node *t) const;
};

//判树空
template<class T>
bool binaryTree<T>::isEmpty() const {
    return root == NULL;
}

//求树根
template<class T>
T binaryTree<T>::Root(T flag) const {
    if (root == nullptr) return flag;
    else return root->data;
}

//求结点数
template<class T>
int binaryTree<T>::count(Node *t) const {
    if (t == nullptr) return 0;
    return 1 + count(t->left) + count(t->right);
}

//求树高
template<class T>
int binaryTree<T>::height(Node *t) const {
    if (t == nullptr) return 0;
    int leftHeight = height(t->left);
    int rightHeight = height(t->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

//清空树
template<class T>
void binaryTree<T>::clear() {
    clear(root);
}
template<class T>
void binaryTree<T>::clear(Node *&t) {
    if (t != nullptr) {
        clear(t->left);
        clear(t->right);
        delete t;
        t = nullptr;
    }
}

//前序遍历
template<class T>
void binaryTree<T>::preOrder(binaryTree<T>::Node *t) const
{
    if (t == NULL) return;
    cout << t->data << ' ';
    preOrder(t->left);
    preOrder(t->right);
}

//中序遍历
template<class T>
void binaryTree<T>::midOrder(binaryTree<T>::Node *t) const
{
    if (t == NULL) return;
    midOrder(t->left);
    cout << t->data << ' ';
    midOrder(t->right);
}

//后序遍历
template<class T>
void binaryTree<T>::postOrder(binaryTree<T>::Node *t) const
{
    if (t == NULL) return;
    postOrder(t->left);
    postOrder(t->right);
    cout << t->data << ' ';
}

//层次遍历（需要辅助队列）
template<class T>
void binaryTree<T>::levelOrder() const {
    linkQueue< Node * > que; //辅助队列
    Node *tmp;
    if (root == NULL) return; // 空树无需入队，避免访问空指针
    que.enQueue(root); //可以先判断root是否为空
    while (!que.isEmpty()) {
        tmp = que.deQueue();
        cout << tmp->data << ' ';
        if (tmp->left) que.enQueue(tmp->left);
        if (tmp->right) que.enQueue(tmp->right);
    }
}

这一段类定义里同时出现了“公有包裹函数”和“私有递归函数”。例如 preOrder() const 是给外部调用的接口，真正递归的是 preOrder(Node *t) const。这样设计的好处是：外部调用者不需要知道根指针 root 的存在，只需要调用无参遍历函数；类内部则把当前子树根 t 作为递归状态不断向下传递。

层次构建二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <class Type>
void binaryTree<Type>::createTree(Type flag)
{
    linkQueue<Node *> que;//队列结点为指向Node的指针
    Node *tmp;
    Type x, ldata, rdata;
    //创建树，输入flag表示空
    cout << "\n输入根结点：";
    cin >> x;
    if (x == flag) { root = NULL; return; } // 输入flag表示构造空树
    root = new Node(x);
    que.enQueue(root);
    while (!que.isEmpty()) {
        tmp = que.deQueue();
        cout << "\n输入" << tmp->data << "的两个儿子(" << flag << "表示空结点)：";
        cin >> ldata >> rdata;
        if (ldata != flag) que.enQueue(tmp->left = new Node(ldata));
        if (rdata != flag) que.enQueue(tmp->right = new Node(rdata));
    }
    cout << "create completed!\n";
}

createTree 使用队列，是因为它按层次顺序构造树。每读入一个非空结点，就把它入队；之后从队列中取出一个结点，再询问它的左右孩子。这样可以保证输入顺序与树的层序结构一致。flag 是空结点标记，作用类似“这里没有孩子”，从而避免为不存在的子树继续入队。

二叉树遍历的非递归实现

  • 递归是程序设计中强有力的工具。
  • 递归程序结构清晰、明了、美观。
  • 递归程序的弱点：它的时间、空间的效率比较低。
  • 所以在实际使用中，我们常常希望使用它的非递归版本。二叉树的遍历也是如此。尽管二叉树遍历的递归函数非常简洁，但有时我们还是希望使用速度更快的非递归函数。

非递归前序遍历

  • 前序遍历第一个被访问的结点是根结点，然后访问左子树，最后访问右子树。
  • 可以设置一个栈，保存将要访问的树的树根。
  • 开始时，把二叉树的根结点存入栈中。然后重复以下过程，直到栈为空：
  • 从栈中取出一个结点，输出根结点的值；
  • 然后把右子树，左子树放入栈中。

前序非递归版本的关键是栈的后进先出特性。因为希望左孩子先被访问，所以入栈时必须先压右孩子、再压左孩子；下一轮弹出时左孩子才会先出来。这里栈中保存的是“接下来还没有访问、但已经被发现的子树根”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class Type>
void binaryTree<Type>::preOrder() const
{
    linkStack<Node *> s;
    Node *current;
    cout << "前序遍历: ";
    if (root == NULL) return; // 空树没有结点可遍历
    s.push(root);
    while (!s.isEmpty()) {
        current = s.pop();
        cout << current->data;
        if ( current->right != NULL ) s.push( current->right ); // 右孩子先入栈，保证左孩子先访问
        if ( current->left != NULL ) s.push( current->left );
    }
}

非递归中序遍历

  • 采用一个栈存放要遍历的树的树根。
  • 中序遍历中，先要遍历左子树，接下去才能访问根结点，因此，当根结点出栈时，我们不能访问它，而要访问它的左子树，此时要把树根结点暂存一下。
  • 由于左子树访问完后还要访问根结点，因此仍可以把它存在栈中，接着左子树也进栈。此时执行出栈操作，出栈的是左子树。左子树问结束后，再次出栈的是根结点，此时根结点可被访问。根结点访问后，访问右子树，则将右子树进栈。

TimesPop 可以理解为“这个结点已经从栈中弹出过几次”。中序遍历中，一个结点第一次弹出时还不能访问，因为它的左子树还没处理；第二次弹出时，左子树已经处理完，才访问根结点，并转向右子树。这个技巧本质上是在用显式状态模拟递归调用栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//（1）初始化：根结点timespop=0,入栈。
//（2）出栈，如果timespop==0,则 timespop+=1,入栈，左子结点timespop=0,入栈；
// 如果timespop==1,则访问它，其右儿子timespop=0,入栈。
//（3）重复(2)直至栈空。

struct StNode
{
    Node *node;
    int TimesPop;
    StNode ( Node *N = NULL ):node(N), TimesPop(0) {} //TimesPop初始赋值0
};

template <class Type>
void binaryTree<Type>::midOrder() const{
    linkStack<StNode> s;
    StNode current(root); //提前判断一下是否是空树
    cout << "中序遍历: ";
    if (root == NULL) return;
    s.push(current);
    while (!s.isEmpty()) {
        current = s.pop();
        if ( ++current.TimesPop == 2 ) { //TimesPop的变化
            cout << current.node->data;
            if ( current.node->right != NULL ) s.push(StNode(current.node->right ));
        }
        else { s.push( current );
            if ( current.node->left != NULL ) s.push(StNode(current.node->left));
        }
    }
}

非递归后序遍历

  • 将中序遍历的非递归实现的思想进一步延伸，可以得到后序遍历的非递归实现。
  • 当以后序遍历一棵二叉树时，先将树根进栈，表示要遍历这棵树。
  • 根结点第一次出栈时，根结点不能访问，应该访问左子树。于是，根结点重新入栈，并将左子树也入栈。
  • 根结点第二次出栈时，根结点还是不能访问，要先访问右子树。于是，根结点再次入栈，右子树也入栈。
  • 当根结点第三次出栈时，表示右子树遍历结束，此时，根结点才能被访问。

后序遍历最容易混乱，因为根结点必须等左、右子树都访问完之后才能输出。因此一个结点需要经历三种状态：第一次弹出表示准备处理左子树，第二次弹出表示左子树已完成、准备处理右子树，第三次弹出表示左右子树都已完成、可以访问根结点。TimesPop 记录的正是这个阶段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//（1）初始化：根结点timespop=0,入栈
//（2）出栈，如果timespop==0,则timespop+=1,再次入栈;
// 同时，左子结点timespop=0，入栈；
// 如果timespop==1，则 timespop+=1,再次入栈，同时，其右儿子timespop=0,入栈;
// 如果timespop==2，则访问。
//（3）重复（2）直至栈空

template <class Type>
void binaryTree<Type>::postOrder() const
{
    linkStack< StNode > s;
    StNode current(root);
    cout << "后序遍历: ";
    if (root == NULL) return;
    s.push(current);
    while (!s.isEmpty()) {
        current = s.pop();
        if (++current.TimesPop == 3) { //TimesPop的变化
            cout << current.node->data;
            continue;
        }
        s.push(current);
        if (current.TimesPop == 1) {
            if (current.node->left != NULL) s.push(StNode(current.node->left));
        } else {
            if (current.node->right != NULL) s.push(StNode(current.node->right));
        }
    }
}

哈夫曼树与哈夫曼编码

哈夫曼编码解决的是“如何给高频字符更短编码、低频字符更长编码，并且仍能唯一解码”的问题。若所有字符都使用固定长度编码，简单但可能浪费空间；若允许变长编码，就必须保证一个字符的编码不能成为另一个字符编码的前缀，否则解码时会产生歧义。

因此哈夫曼树同时包含两个目标：编码必须是前缀码，平均编码长度还要尽可能短。树中从根到叶子的左右路径可以分别记为 0 和 1，某个字符所在叶子的路径就是它的编码。

前缀编码与哈夫曼树

  • 字符只放在叶结点中。
  • 字符编码可以有不同长度。
  • 每个字符的编码都不可能是其他字符编码的前缀
  • 前缀编码可被惟一解码
  • 哈夫曼树是一棵最小代价的二叉树，所有的字符都包含在叶结点上。

“字符只放在叶结点”是前缀编码成立的关键。如果某个字符放在内部结点，那么它的编码就会成为其子树中所有字符编码的前缀，解码时读到这段比特后就无法判断应该停下还是继续读。

哈夫曼算法

  1. 给定一个具有 n 个权值的结点的集合 A。
  2. 执行 n - 1 次循环,在每次循环时执行以下操作:从当前集合中选取权值最小、次最小的两个结点，以这两个结点作为内部结点 bi 的左右儿子，bi 的权值为其左右儿子权值之和。
  3. 在集合中去除这两个权值最小、次最小的结点，并将内部结点 bI 加入其中。这样，在集合 A 中，结点个数便减少了一个。这样，在经过了 n-1 次循环之后，集合 A 中只剩下了一个结点，这个结点就是根结点。

哈夫曼算法的贪心直觉是：权值越小的字符越应该出现在越深的位置，因为深层路径会带来更长编码。每次合并两个最小权值结点，相当于先确定“最不常出现的两个字符应该成为兄弟”，它们共同承担一段较长的前缀。不断合并后，根到叶子的路径就自然形成了每个字符的编码。

哈夫曼树的存储

  1. 在哈夫曼树中，每个要编码的元素是一个叶结点，其它结点都是度数为 2 的节点。
  2. 一旦给定了要编码的元素个数，由 n0=n2+1n_0 = n_2 + 1 可知哈夫曼树的大小为 2n−12n - 1。
  3. 哈夫曼树可以用一个大小为 2n 的数组来存储。0位置不用，根存放在下标 1 位置。叶结点依次放在 n+1 到 2n 的位置。
  4. 每个数组元素保存的信息：结点的数据、权值和父结点和左右孩子的位置。
  5. 数组下标的意义：这里的数组只是“顺序表容器”，不是完全二叉树的层序存储。因此不能使用 2i、2i + 1、i / 2 推导父子关系；父结点、左孩子、右孩子都由结点中的 parent、left、right 字段显式记录。

哈夫曼树的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
template <class Type>
class hfTree {
private:
    struct Node {
        Type data;
        int weight;
        int parent, left, right;
    };
    Node* elem;
    int length;
public:
    struct hfCode {
        Type data;
        string code;
    };
    hfTree(const Type* x, const int* w, int size);
    ~hfTree() { delete[] elem; }
    void getCode(hfCode result[]);
};

//构造函数
template <class Type>
hfTree<Type>::hfTree(const Type* v, const int* w, int size) {
    const int MAX_INT = 32767;
    int min1, min2;  // 最小树、次最小树的权值
    int x, y;        // 最小树、次最小树的下标

    // 初始化树的结构
    length = 2 * size;
    elem = new Node[length];

    // 初始化叶子节点（存储在数组的后半部分）
    for (int i = size; i < length; ++i) {
        elem[i].weight = w[i - size];
        elem[i].data = v[i - size];
        elem[i].parent = elem[i].left = elem[i].right = 0;
    }

    // 构造新的二叉树（从后向前构建非叶子节点）
    for (int i = size - 1; i > 0; --i) {
        min1 = min2 = MAX_INT; // min1存储最小权重，min2存储次小权重
        x = y = 0; // x存储次小权重下标，y存储最小权重下标

        // 找到当前未处理的两个最小权重的节点
        for (int j = i + 1; j < length; ++j) {
            if (elem[j].parent == 0) {
                if (elem[j].weight < min1) {
                    min2 = min1;
                    min1 = elem[j].weight;
                    x = y; // 更新次小权重下标为之前的最小权重下标
                    y = j; // 最小元素下标更新为当前下标
                }
                else if (elem[j].weight < min2) {
                    min2 = elem[j].weight;
                    x = j;
                }
            }
        }

        // 合并最小的两个节点，形成新的父节点
        elem[i].weight = min1 + min2;
        elem[i].left = x;
        elem[i].right = y;
        elem[i].parent = 0;  // 新节点的父节点暂时设为 0

        // 更新子节点的父节点指向
        elem[x].parent = i;
        elem[y].parent = i;
    }
}

getCode() 函数的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
template <class Type>
void hfTree<Type>::getCode(hfCode result[]) {
    int size = length / 2;  // 叶子节点的数量
    int p, s;               // p: 父节点索引, s: 当前节点索引

    // 遍历所有叶子节点
    for (int i = size; i < length; ++i) {
        // 存储当前节点的数据
        result[i - size].data = elem[i].data;
        // 初始化编码为空字符串
        result[i - size].code = "";

        // 从叶子节点回溯到根节点生成编码
        p = elem[i].parent;  // 获取父节点
        s = i;               // 当前节点

        while (p != 0) {  // 未到达根节点
            if (elem[p].left == s) {
                // 如果是左孩子，添加'0'
                result[i - size].code = '0' + result[i - size].code;
            } else {
                // 如果是右孩子，添加'1'
                result[i - size].code = '1' + result[i - size].code;
            }

            // 向上回溯
            s = p;                // 当前节点变为父节点
            p = elem[p].parent;   // 父节点变为祖父节点
        }
    }
}

示例

1
2
3
4
5
        [1] (26)
       /   \
   [2](14) [5](12)
   /   \
[3](5) [4](9)

叶子节点：

elem[3]：A（权重 5）
elem[4]：B（权重 9）
elem[5]：C（权重 12）
生成的编码：

A（elem[3]）：

父节点是 [2]，且是左孩子 → 添加 0。

父节点是 [1]，且是左孩子 → 添加 0。

最终编码：00
B（elem[4]）：

父节点是 [2]，且是右孩子 → 添加 1。

父节点是 [1]，且是左孩子 → 添加 0。

最终编码：01
C（elem[5]）：

父节点是 [1]，且是右孩子 → 添加 1。

最终编码：1