返回目录

二叉树的遍历

先序遍历：先遍历根节点，然后遍历左节点，最后遍历右节点

1
2
3
4
5
6
basic_string<T> preorder() {
    auto dfs = [&](auto&& self, const node* p) -> string {
        return p == nullptr ? "" : p->data + self(self, p->ls) + self(self, p->rs);
    };
    return dfs(dfs, root);
}

中序遍历：先遍历左节点，然后遍历根节点，最后遍历右节点（把树平面投影至二维从左到右）

1
2
3
4
5
6
basic_string<T> inorder() {
    auto dfs = [&](auto&& self, const node* p) -> basic_string<T> {
        return p == nullptr ? "" : self(self, p->ls) + p->data + self(self, p->rs);
    };
    return dfs(dfs, root);
}

后序遍历：先遍历左节点，然后遍历右节点，最后遍历根节点

1
2
3
4
5
6
basic_string<T> postorder() {
    auto dfs = [&](auto&& self, const node* p) -> basic_string<T> {
        return p == nullptr ? "" : self(self, p->ls) + self(self, p->rs) + p->data;
    };
    return dfs(dfs, root);
}

层次遍历：从上向下，同一层从左向右

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
basic_string<T> levelorder() {
    queue<pair<int, node*>> Q;
    Q.push({ 0, root });
    basic_string<T> res;
    int lst = 0;
    while (!Q.empty()) {
        auto [d, p] = Q.front();
        Q.pop();
        if (d > lst) {
            res += '\n';
            lst = d;
        }
        res += p->data;
        res += " ";
        if (p->ls) Q.push({ d + 1, p->ls });
        if (p->rs) Q.push({ d + 1, p->rs });
    }
    return res;
}

二叉树的构造

给定某些遍历序列，反过来确定该二叉树。

例如，一棵二叉树的先序序列和中序序列相同，设二叉树的先序序列为 NLR，中序序列为 LNR，由于 N 不能为空，故 L 为空，所以这样的二叉树为右单支树。

对于不同形态的二叉树，先序、中序、后序序列可能相同，而先序序列和后序序列可能同时分别相同，因此，只能 由先（后）序序列和中序序列 能够唯一确定一棵二叉树。具体的方法是，由先（后）序序列 确定根的位置，在中序序列中找根，划分左右子树，递归地寻找。

二叉树与树之间的转换

将森林转化为二叉树的形式化的方法是：

  • 树中所有相邻兄弟之间加一条连线；

  • 对树中的每个结点，只保留它与第一个孩子结点之间的连线，删除它与其他孩子结点之间的连线；

  • 以树的根结点为轴心，将整棵树顺时针转动 45 度，使之结构层次分明。

  • 如果是森林，第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子结点，当所有二叉树连在一起后，此时所得到的二叉树就是由森林转换得到的二叉树。

不难发现，右子节点是兄弟，左子节点是第一个子节点。

线索二叉树

对于nn 个结点的二叉树，在二叉链存储结构中有n+1n+1 个空链域。

利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。

线索二叉树在原二叉链中增加了 ltag 和 rtag 两个标志域，按先（中、后序）遍历时，若没有子节点，则指向下一个线索。

哈夫曼树

从根结点到各个叶子结点的路径长度（指路径上边的数量）与相应结点权值的乘积的和称为该二叉树的带权路径长度

WPL⁡=∑i=0n−1wili.\operatorname{WPL}=\sum_{i=0}^{n-1}w_{i}l_{i}.

其中具有最小带权路径长度的二叉树称为 哈夫曼树。也就是说，权值越大的叶子结点越靠近根结点。

树中从根到每个叶子都有一条路径，对路径上的各分支约定指向左子树根的分支表示 0 码，指向右子树的分支表示 1 码，取每条路径上的 0 或 1 的序列作为和各个叶子对应的字符的编码，这就是 哈夫曼编码。没有一个字符的哈夫曼编码是另一个字符的哈夫曼编码的前缀。

Notes

A

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
#include <iostream>
using namespace std;
#define MaxSize 100
typedef char ElemType;

typedef struct tnode {
    ElemType data;
    struct tnode* lchild, * rchild;
} BTNode;

void CreateBTree(BTNode*& bt, char* str)//由括号表示串创建二叉链
{
    BTNode* St[MaxSize], * p = NULL;
    int top = -1, k, j = 0;
    char ch;
    bt = NULL;            //建立的二叉树初始时为空
    ch = str[j];
    while (ch != '\0')    //str未扫描完时循环
    {
        switch (ch) {
            case '(':top++; St[top] = p; k = 1; break;//为左孩子结点
            case ')':top--; break;
            case ',':k = 2; break;    //为右孩子结点
            default:p = new BTNode();
                p->data = ch; p->lchild = p->rchild = NULL;
                if (bt == NULL)    //*p为二叉树的根结点
                    bt = p;
                else            //已建立二叉树根结点
                {
                    switch (k) {
                        case 1:St[top]->lchild = p; break;
                        case 2:St[top]->rchild = p; break;
                    }
                }
        }
        j++;
        ch = str[j];
    }
}
void DestroyBTree(BTNode*& bt)        //销毁二叉链
{
    if (bt != NULL) {
        DestroyBTree(bt->lchild);
        DestroyBTree(bt->rchild);
        delete bt;
    }
}
// 在此处补充你的代码

void PreOrder(BTNode*& bt) {
    if (bt == nullptr) return;
    cout << bt->data;
    PreOrder(bt->lchild);
    PreOrder(bt->rchild);
}

void InOrder(BTNode*& bt) {
    if (bt == nullptr) return;
    InOrder(bt->lchild);
    cout << bt->data;
    InOrder(bt->rchild);
}

void PostOrder(BTNode*& bt) {
    if (bt == nullptr) return;
    PostOrder(bt->lchild);
    PostOrder(bt->rchild);
    cout << bt->data;
}

int main() {
    char tree[MaxSize];
    cin >> tree;
    BTNode* bt;
    CreateBTree(bt, tree);
    PreOrder(bt); cout << endl;
    InOrder(bt); cout << endl;
    PostOrder(bt); cout << endl;
    DestroyBTree(bt);
    return 0;
}

B

1
2
3
4
5
6
7
8
9
10
int main() {
    string s;
    cin >> s;

    BinaryTree<char> bt(s);

    cout << bt.levelorder() << endl;

    return 0;
}

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main() {
    string s;
    cin >> s;

    BinaryTree<char> bt(s);

    auto res = bt.preorder();

    char c;
    cin >> c;

    res = res.substr(0, res.find(c) + 1);
    for (auto c : res) {
        cout << c << " ";
    }

    return 0;
}

D

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main() {
    int t;
    cin >> t;

    while (t--) {
        string s1, s2;
        cin >> s1 >> s2;

        BinaryTree<char> bt1(s1), bt2(s2);

        cout << (bt1.shape() == bt2.shape() ? "same" : "different") << endl;
    }

    return 0;
}

E

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
struct node {
    int val;
    int id;
    bool used;
    BinaryTree<char> bt;
    bool operator<(const node& o) const {
        return val == o.val ? id < o.id : val < o.val;
    }
} v[N];

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        v[i].bt.root = new BinaryTree<char>::node;
        v[i].bt.root->data = c;
        v[i].bt.root->ls = v[i].bt.root->rs = nullptr;
        v[i].bt.root->parent = nullptr;
        v[i].used = false;
    }

    for (int i = 1; i <= n; i++) {
        cin >> v[i].val;
        v[i].id = i;
    }

    int siz = n + 1;
    v[0].val = 0x3f3f3f3f;
    v[0].id = 0;
    v[0].used = false;
    v[0].bt.root = nullptr;

    for (int t = 1; t < n; t++) {
        int imin = 0, imin2 = 0;
        for (int i = 1; i < siz; i++) {
            if (v[i] < v[imin] && !v[i].used) {
                imin2 = imin;
                imin = i;
            } else if (v[i] < v[imin2] && !v[i].used) {
                imin2 = i;
            }
        }
        v[siz].bt.root = new BinaryTree<char>::node;
        v[siz].bt.root->data = ':';
        v[siz].bt.root->parent = nullptr;
        v[siz].bt.root->ls = v[imin].bt.root;
        v[siz].bt.root->ls->data = '0';
        v[siz].bt.root->rs = v[imin2].bt.root;
        v[siz].bt.root->rs->data = '1';
        v[siz].val = v[imin].val + v[imin2].val;
        v[siz].id = siz;
        v[siz].used = false;
        v[imin].used = v[imin2].used = true;
        siz++;
    }

    auto bt = v[siz - 1].bt;

    for (int i = 1; i <= n; i++) {
        cout << v[i].bt.root->data << bt.path(v[i].bt.root) << endl;
    }

    bt.delete_subtree(bt.root);
    for (int i = 1; i <= siz; i++) {
        v[i].bt.root = nullptr;
    }

    return 0;
}