跳转至

数据结构增强版教材

第5章树与二叉树代码

第5章树与二叉树代码¶

使用建议¶

先配合对应章节阅读：第5章树与二叉树正文
这一页优先提供站内可直接查看的代码版本，适合网页阅读和搜索。
这一页主要用于网页阅读，建议结合对应正文与逐行注释版一起使用。

文件位置¶

普通代码版：第5章普通代码版
逐行注释版：第5章逐行注释版代码
兼容编码版：第5章兼容编码版逐行注释代码

普通代码版¶

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 128
#define MAX_HUFFMAN_NODES 128
#define MAX_UNION_FIND_SIZE 32

/* 二叉链表结点：data 保存当前结点值，lchild/rchild 分别指向左右孩子。 */
typedef struct BiTNode {
    char data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
} BiTNode, *BiTree;

/* 顺序队列结点数组：层序遍历时需要按先进先出的顺序管理结点。 */
typedef struct {
    BiTree data[MAX_QUEUE_SIZE];
    int front;
    int rear;
} BiTreeQueue;

/* 并查集：parent[i] < 0 表示 i 是根，且绝对值表示集合大小。 */
typedef struct {
    int parent[MAX_UNION_FIND_SIZE];
    int size;
} UnionFind;

/* 哈夫曼树数组结点：weight 为权值，parent/left/right 存储父子关系下标。 */
typedef struct {
    int weight;
    int parent;
    int left;
    int right;
} HuffmanNode;

/* 线索二叉树结点：ltag/rtag 为 false 表示指向孩子，true 表示指向前驱或后继线索。 */
typedef struct ThreadNode {
    char data;
    struct ThreadNode *lchild;
    struct ThreadNode *rchild;
    bool ltag;
    bool rtag;
} ThreadNode, *ThreadTree;

/* 普通树 / 森林结点：first_child 指向第一个孩子，next_sibling 指向下一个兄弟。 */
typedef struct GTreeNode {
    char data;
    struct GTreeNode *first_child;
    struct GTreeNode *next_sibling;
} GTreeNode, *GTree;

/* 初始化队列，让 front 和 rear 都回到 0。 */
void InitBiTreeQueue(BiTreeQueue *queue) {
    if (queue == NULL) {
        return;
    }
    queue->front = 0;
    queue->rear = 0;
}

/* 判断队列是否为空：front 和 rear 相等时说明没有元素。 */
bool IsBiTreeQueueEmpty(const BiTreeQueue *queue) {
    return queue == NULL || queue->front == queue->rear;
}

/* 入队：把一个二叉树结点指针压到队尾，供层序遍历后续处理。 */
bool EnqueueBiTree(BiTreeQueue *queue, BiTree node) {
    int next_rear;

    if (queue == NULL) {
        return false;
    }

    next_rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
    if (next_rear == queue->front) {
        return false;
    }

    queue->data[queue->rear] = node;
    queue->rear = next_rear;
    return true;
}

/* 出队：取出当前队头结点，并让队头向前移动一格。 */
bool DequeueBiTree(BiTreeQueue *queue, BiTree *node) {
    if (queue == NULL || node == NULL || IsBiTreeQueueEmpty(queue)) {
        return false;
    }

    *node = queue->data[queue->front];
    queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
    return true;
}

/* 创建一个新结点：先申请内存，再把左右孩子指针置空。 */
BiTree CreateNode(char data) {
    BiTree node;

    node = (BiTree)malloc(sizeof(BiTNode));
    if (node == NULL) {
        return NULL;
    }

    node->data = data;
    node->lchild = NULL;
    node->rchild = NULL;
    return node;
}

/* 按先序字符串创建二叉树：'#' 表示空结点，适合教材演示递归建树。 */
BiTree CreateBiTreeByPreorder(const char **cursor) {
    BiTree root;

    if (cursor == NULL || *cursor == NULL || **cursor == '\0') {
        return NULL;
    }

    if (**cursor == '#') {
        (*cursor)++;
        return NULL;
    }

    root = CreateNode(**cursor);
    if (root == NULL) {
        return NULL;
    }

    (*cursor)++;
    root->lchild = CreateBiTreeByPreorder(cursor);
    root->rchild = CreateBiTreeByPreorder(cursor);
    return root;
}

/* 销毁二叉树：先释放左右子树，再释放当前结点。 */
void DestroyBiTree(BiTree *tree) {
    if (tree == NULL || *tree == NULL) {
        return;
    }

    DestroyBiTree(&((*tree)->lchild));
    DestroyBiTree(&((*tree)->rchild));
    free(*tree);
    *tree = NULL;
}

/* 访问函数：统一打印一个结点的数据，方便各类遍历复用。 */
void VisitNode(BiTree node) {
    if (node == NULL) {
        return;
    }
    printf("%c ", node->data);
}

/* 先序遍历：先访问根，再访问左子树，最后访问右子树。 */
void PreorderTraversal(BiTree tree) {
    if (tree == NULL) {
        return;
    }

    VisitNode(tree);
    PreorderTraversal(tree->lchild);
    PreorderTraversal(tree->rchild);
}

/* 中序遍历：先访问左子树，再访问根，最后访问右子树。 */
void InorderTraversal(BiTree tree) {
    if (tree == NULL) {
        return;
    }

    InorderTraversal(tree->lchild);
    VisitNode(tree);
    InorderTraversal(tree->rchild);
}

/* 后序遍历：先访问左右子树，最后访问根。 */
void PostorderTraversal(BiTree tree) {
    if (tree == NULL) {
        return;
    }

    PostorderTraversal(tree->lchild);
    PostorderTraversal(tree->rchild);
    VisitNode(tree);
}

/* 层序遍历：使用队列按层从左到右访问所有结点。 */
void LevelOrderTraversal(BiTree tree) {
    BiTreeQueue queue;
    BiTree current;

    if (tree == NULL) {
        return;
    }

    InitBiTreeQueue(&queue);
    EnqueueBiTree(&queue, tree);

    while (!IsBiTreeQueueEmpty(&queue)) {
        DequeueBiTree(&queue, &current);
        VisitNode(current);

        if (current->lchild != NULL) {
            EnqueueBiTree(&queue, current->lchild);
        }
        if (current->rchild != NULL) {
            EnqueueBiTree(&queue, current->rchild);
        }
    }
}

/* 统计结点总数：当前结点算 1，再加左右子树结点数。 */
int CountNodes(BiTree tree) {
    if (tree == NULL) {
        return 0;
    }
    return 1 + CountNodes(tree->lchild) + CountNodes(tree->rchild);
}

/* 统计叶子结点：左右孩子都为空时，这个结点就是叶子。 */
int CountLeaves(BiTree tree) {
    if (tree == NULL) {
        return 0;
    }
    if (tree->lchild == NULL && tree->rchild == NULL) {
        return 1;
    }
    return CountLeaves(tree->lchild) + CountLeaves(tree->rchild);
}

/* 统计度为 1 的结点：恰好只有一个孩子的结点记为 1。 */
int CountDegreeOne(BiTree tree) {
    int current;

    if (tree == NULL) {
        return 0;
    }

    current = ((tree->lchild == NULL) ^ (tree->rchild == NULL)) ? 1 : 0;
    return current + CountDegreeOne(tree->lchild) + CountDegreeOne(tree->rchild);
}

/* 统计度为 2 的结点：左右孩子都非空的结点记为 1。 */
int CountDegreeTwo(BiTree tree) {
    int current;

    if (tree == NULL) {
        return 0;
    }

    current = (tree->lchild != NULL && tree->rchild != NULL) ? 1 : 0;
    return current + CountDegreeTwo(tree->lchild) + CountDegreeTwo(tree->rchild);
}

/* 求二叉树高度：取左右子树高度较大者，再加上当前根这一层。 */
int GetBiTreeHeight(BiTree tree) {
    int left_height;
    int right_height;

    if (tree == NULL) {
        return 0;
    }

    left_height = GetBiTreeHeight(tree->lchild);
    right_height = GetBiTreeHeight(tree->rchild);
    return (left_height > right_height ? left_height : right_height) + 1;
}

/* 查找指定字符所在层次：根在第 1 层，找到就返回层号，找不到返回 0。 */
int FindNodeLevel(BiTree tree, char target, int level) {
    int left_result;
    int right_result;

    if (tree == NULL) {
        return 0;
    }

    if (tree->data == target) {
        return level;
    }

    left_result = FindNodeLevel(tree->lchild, target, level + 1);
    if (left_result != 0) {
        return left_result;
    }

    right_result = FindNodeLevel(tree->rchild, target, level + 1);
    return right_result;
}

/* 交换每个结点的左右孩子：这是二叉树“镜像化”的经典递归模板。 */
void SwapChildren(BiTree tree) {
    BiTree temp;

    if (tree == NULL) {
        return;
    }

    temp = tree->lchild;
    tree->lchild = tree->rchild;
    tree->rchild = temp;

    SwapChildren(tree->lchild);
    SwapChildren(tree->rchild);
}

/* 输出某种遍历结果时先打印标题，让演示结果更容易对应到概念。 */
void PrintTraversalResult(const char *title, void (*traversal)(BiTree), BiTree tree) {
    if (title == NULL || traversal == NULL) {
        return;
    }

    printf("%s", title);
    traversal(tree);
    printf("\n");
}

/* 创建线索二叉树结点：先复制数据，再把左右指针和标志位置成初始状态。 */
ThreadTree CreateThreadNode(char data) {
    ThreadTree node;

    node = (ThreadTree)malloc(sizeof(ThreadNode));
    if (node == NULL) {
        return NULL;
    }

    node->data = data;
    node->lchild = NULL;
    node->rchild = NULL;
    node->ltag = false;
    node->rtag = false;
    return node;
}

/* 把普通二叉树克隆成线索二叉树结点结构，方便后续在线索化时不破坏原树。 */
ThreadTree CloneBiTreeToThreadTree(BiTree tree) {
    ThreadTree root;

    if (tree == NULL) {
        return NULL;
    }

    root = CreateThreadNode(tree->data);
    if (root == NULL) {
        return NULL;
    }

    root->lchild = CloneBiTreeToThreadTree(tree->lchild);
    root->rchild = CloneBiTreeToThreadTree(tree->rchild);
    return root;
}

/* 销毁线索二叉树：只有 tag 为 false 时，左右指针才是真孩子，才需要继续递归释放。 */
void DestroyThreadTree(ThreadTree *tree) {
    if (tree == NULL || *tree == NULL) {
        return;
    }

    if (!(*tree)->ltag) {
        DestroyThreadTree(&((*tree)->lchild));
    }
    if (!(*tree)->rtag) {
        DestroyThreadTree(&((*tree)->rchild));
    }

    free(*tree);
    *tree = NULL;
}

/* 中序线索化：pre 始终指向刚刚访问完成的前一个结点，用它补前驱和后继线索。 */
void InorderThreading(ThreadTree node, ThreadTree *pre) {
    if (node == NULL) {
        return;
    }

    if (node->lchild != NULL) {
        InorderThreading(node->lchild, pre);
    }

    if (node->lchild == NULL) {
        node->ltag = true;
        node->lchild = *pre;
    }

    if (*pre != NULL && (*pre)->rchild == NULL) {
        (*pre)->rtag = true;
        (*pre)->rchild = node;
    }

    *pre = node;

    if (node->rchild != NULL) {
        InorderThreading(node->rchild, pre);
    }
}

/* 基于普通二叉树构造中序线索二叉树：先克隆，再统一完成线索化。 */
ThreadTree BuildInorderThreadedTree(BiTree tree) {
    ThreadTree threaded_root;
    ThreadTree pre;

    threaded_root = CloneBiTreeToThreadTree(tree);
    if (threaded_root == NULL) {
        return NULL;
    }

    pre = NULL;
    InorderThreading(threaded_root, &pre);
    if (pre != NULL && pre->rchild == NULL) {
        pre->rtag = true;
        pre->rchild = NULL;
    }

    return threaded_root;
}

/* 找到中序线索二叉树中的第一个结点：一路沿真正的左孩子走到底。 */
ThreadTree FirstInorderThreadNode(ThreadTree tree) {
    if (tree == NULL) {
        return NULL;
    }

    while (!tree->ltag && tree->lchild != NULL) {
        tree = tree->lchild;
    }
    return tree;
}

/* 找中序下一个结点：若右指针是线索就直接跟过去，否则去右子树找最左下结点。 */
ThreadTree NextInorderThreadNode(ThreadTree node) {
    if (node == NULL) {
        return NULL;
    }

    if (node->rtag) {
        return node->rchild;
    }

    return FirstInorderThreadNode(node->rchild);
}

/* 用线索完成中序遍历：遍历时不再需要栈，也不需要递归。 */
void InorderThreadTraversal(ThreadTree tree) {
    ThreadTree current;

    current = FirstInorderThreadNode(tree);
    while (current != NULL) {
        printf("%c ", current->data);
        current = NextInorderThreadNode(current);
    }
}

/* 创建普通树结点：先保存数据，再把孩子和兄弟指针置空。 */
GTree CreateGTreeNode(char data) {
    GTree node;

    node = (GTree)malloc(sizeof(GTreeNode));
    if (node == NULL) {
        return NULL;
    }

    node->data = data;
    node->first_child = NULL;
    node->next_sibling = NULL;
    return node;
}

/* 销毁普通树 / 森林：先释放孩子子树，再释放兄弟链，最后释放当前结点。 */
void DestroyGTree(GTree *tree) {
    if (tree == NULL || *tree == NULL) {
        return;
    }

    DestroyGTree(&((*tree)->first_child));
    DestroyGTree(&((*tree)->next_sibling));
    free(*tree);
    *tree = NULL;
}

/* 先根遍历普通树：先访问根，再从左到右依次处理所有孩子。 */
void PreRootTraversal(GTree tree) {
    GTree child;

    if (tree == NULL) {
        return;
    }

    printf("%c ", tree->data);
    child = tree->first_child;
    while (child != NULL) {
        PreRootTraversal(child);
        child = child->next_sibling;
    }
}

/* 后根遍历普通树：先处理完所有孩子，最后再访问根结点。 */
void PostRootTraversal(GTree tree) {
    GTree child;

    if (tree == NULL) {
        return;
    }

    child = tree->first_child;
    while (child != NULL) {
        PostRootTraversal(child);
        child = child->next_sibling;
    }
    printf("%c ", tree->data);
}

/* 先序打印森林：把每一棵树都当作一棵独立的普通树，按根链从左到右依次输出。 */
void PreorderForestTraversal(GTree forest) {
    GTree current_tree;

    current_tree = forest;
    while (current_tree != NULL) {
        PreRootTraversal(current_tree);
        current_tree = current_tree->next_sibling;
    }
}

/* 把普通树转换成二叉树：第一个孩子变左孩子，下一个兄弟变右孩子。 */
BiTree ConvertTreeToBinaryTree(GTree tree) {
    BiTree root;

    if (tree == NULL) {
        return NULL;
    }

    root = CreateNode(tree->data);
    if (root == NULL) {
        return NULL;
    }

    root->lchild = ConvertTreeToBinaryTree(tree->first_child);
    root->rchild = ConvertTreeToBinaryTree(tree->next_sibling);
    return root;
}

/* 把森林转换成二叉树：森林的第一棵树作根，其余树通过右兄弟链接在一起。 */
BiTree ConvertForestToBinaryTree(GTree forest) {
    return ConvertTreeToBinaryTree(forest);
}

/* 把二叉树转回普通树 / 森林：左孩子还原成第一个孩子，右孩子还原成下一个兄弟。 */
GTree ConvertBinaryTreeToGTree(BiTree tree) {
    GTree root;

    if (tree == NULL) {
        return NULL;
    }

    root = CreateGTreeNode(tree->data);
    if (root == NULL) {
        return NULL;
    }

    root->first_child = ConvertBinaryTreeToGTree(tree->lchild);
    root->next_sibling = ConvertBinaryTreeToGTree(tree->rchild);
    return root;
}

/* 构造一棵示例树：A 的孩子为 B、C、D；B 的孩子为 E、F；D 的孩子为 G。 */
GTree BuildSampleGeneralTree(void) {
    GTree a;
    GTree b;
    GTree c;
    GTree d;
    GTree e;
    GTree f;
    GTree g;

    a = CreateGTreeNode('A');
    b = CreateGTreeNode('B');
    c = CreateGTreeNode('C');
    d = CreateGTreeNode('D');
    e = CreateGTreeNode('E');
    f = CreateGTreeNode('F');
    g = CreateGTreeNode('G');

    if (a == NULL || b == NULL || c == NULL || d == NULL ||
        e == NULL || f == NULL || g == NULL) {
        DestroyGTree(&a);
        DestroyGTree(&b);
        DestroyGTree(&c);
        DestroyGTree(&d);
        DestroyGTree(&e);
        DestroyGTree(&f);
        DestroyGTree(&g);
        return NULL;
    }

    a->first_child = b;
    b->next_sibling = c;
    c->next_sibling = d;
    b->first_child = e;
    e->next_sibling = f;
    d->first_child = g;
    return a;
}

/* 构造一个示例森林：第一棵树是 A-B/C，第二棵树是 X-Y/Z。 */
GTree BuildSampleForest(void) {
    GTree a;
    GTree b;
    GTree c;
    GTree x;
    GTree y;
    GTree z;

    a = CreateGTreeNode('A');
    b = CreateGTreeNode('B');
    c = CreateGTreeNode('C');
    x = CreateGTreeNode('X');
    y = CreateGTreeNode('Y');
    z = CreateGTreeNode('Z');

    if (a == NULL || b == NULL || c == NULL || x == NULL || y == NULL || z == NULL) {
        DestroyGTree(&a);
        DestroyGTree(&b);
        DestroyGTree(&c);
        DestroyGTree(&x);
        DestroyGTree(&y);
        DestroyGTree(&z);
        return NULL;
    }

    a->first_child = b;
    b->next_sibling = c;
    x->first_child = y;
    y->next_sibling = z;
    a->next_sibling = x;
    return a;
}

/* 初始化并查集：开始时每个元素自成一个集合，大小都为 1。 */
void InitUnionFind(UnionFind *uf, int size) {
    int i;

    if (uf == NULL || size <= 0 || size > MAX_UNION_FIND_SIZE) {
        return;
    }

    uf->size = size;
    for (i = 0; i < size; i++) {
        uf->parent[i] = -1;
    }
}

/* 查找根结点：路径压缩能让后续查找更快。 */
int FindSet(UnionFind *uf, int x) {
    if (uf == NULL || x < 0 || x >= uf->size) {
        return -1;
    }

    if (uf->parent[x] < 0) {
        return x;
    }

    uf->parent[x] = FindSet(uf, uf->parent[x]);
    return uf->parent[x];
}

/* 合并两个集合：按集合大小合并，尽量减少树高。 */
bool UnionSets(UnionFind *uf, int x, int y) {
    int root_x;
    int root_y;
    int temp;

    if (uf == NULL) {
        return false;
    }

    root_x = FindSet(uf, x);
    root_y = FindSet(uf, y);
    if (root_x < 0 || root_y < 0 || root_x == root_y) {
        return false;
    }

    if (uf->parent[root_x] > uf->parent[root_y]) {
        temp = root_x;
        root_x = root_y;
        root_y = temp;
    }

    uf->parent[root_x] += uf->parent[root_y];
    uf->parent[root_y] = root_x;
    return true;
}

/* 打印并查集当前根信息，便于观察哪些元素已被并到同一集合。 */
void PrintUnionFindState(UnionFind *uf) {
    int i;

    if (uf == NULL) {
        return;
    }

    printf("Union-Find roots: ");
    for (i = 0; i < uf->size; i++) {
        printf("%d->%d ", i, FindSet(uf, i));
    }
    printf("\n");
}

/* 从未被选中过父结点的结点里，找权值最小的两棵树。 */
bool SelectTwoMinNodes(HuffmanNode *tree, int end_index, int *first, int *second) {
    int i;

    if (tree == NULL || first == NULL || second == NULL) {
        return false;
    }

    *first = -1;
    *second = -1;

    for (i = 1; i <= end_index; i++) {
        if (tree[i].parent != 0) {
            continue;
        }

        if (*first == -1 || tree[i].weight < tree[*first].weight) {
            *second = *first;
            *first = i;
        } else if (*second == -1 || tree[i].weight < tree[*second].weight) {
            *second = i;
        }
    }

    return *first != -1 && *second != -1;
}

/* 构造哈夫曼树：每次选两棵权值最小的树合并成新的父结点。 */
bool BuildHuffmanTree(const int *weights, int count, HuffmanNode *tree) {
    int total_nodes;
    int i;
    int first;
    int second;

    if (weights == NULL || tree == NULL || count <= 1 || (2 * count - 1) >= MAX_HUFFMAN_NODES) {
        return false;
    }

    total_nodes = 2 * count - 1;

    for (i = 1; i <= total_nodes; i++) {
        tree[i].weight = 0;
        tree[i].parent = 0;
        tree[i].left = 0;
        tree[i].right = 0;
    }

    for (i = 1; i <= count; i++) {
        tree[i].weight = weights[i - 1];
    }

    for (i = count + 1; i <= total_nodes; i++) {
        if (!SelectTwoMinNodes(tree, i - 1, &first, &second)) {
            return false;
        }

        tree[first].parent = i;
        tree[second].parent = i;
        tree[i].left = first;
        tree[i].right = second;
        tree[i].weight = tree[first].weight + tree[second].weight;
    }

    return true;
}

/* 计算哈夫曼树 WPL：每个叶子权值乘深度，再把它们全部加起来。 */
int ComputeHuffmanWPL(HuffmanNode *tree, int leaf_count) {
    int i;
    int parent;
    int depth;
    int wpl = 0;

    if (tree == NULL || leaf_count <= 0) {
        return 0;
    }

    for (i = 1; i <= leaf_count; i++) {
        depth = 0;
        parent = tree[i].parent;

        while (parent != 0) {
            depth++;
            parent = tree[parent].parent;
        }

        wpl += tree[i].weight * depth;
    }

    return wpl;
}

/* 打印哈夫曼树数组结点，帮助理解“父结点由两个最小权值合并而来”。 */
void PrintHuffmanTree(HuffmanNode *tree, int total_nodes) {
    int i;

    if (tree == NULL) {
        return;
    }

    printf("index weight parent left right\n");
    for (i = 1; i <= total_nodes; i++) {
        printf("%5d %6d %6d %4d %5d\n",
               i,
               tree[i].weight,
               tree[i].parent,
               tree[i].left,
               tree[i].right);
    }
}

int main(void) {
    const char *preorder_text = "ABD##E##CF###";
    const int huffman_weights[] = {5, 2, 3, 6, 8, 9};
    BiTree tree;
    BiTree converted_tree;
    BiTree forest_binary_tree;
    ThreadTree threaded_tree;
    GTree general_tree;
    GTree restored_tree;
    GTree forest;
    UnionFind uf;
    HuffmanNode huffman_tree[MAX_HUFFMAN_NODES];

    tree = CreateBiTreeByPreorder(&preorder_text);
    if (tree == NULL) {
        printf("Failed to create binary tree.\n");
        return 1;
    }

    printf("Binary tree built from preorder string: ABD##E##CF###\n");
    PrintTraversalResult("Preorder: ", PreorderTraversal, tree);
    PrintTraversalResult("Inorder: ", InorderTraversal, tree);
    PrintTraversalResult("Postorder: ", PostorderTraversal, tree);
    PrintTraversalResult("Level order: ", LevelOrderTraversal, tree);

    printf("Node count: %d\n", CountNodes(tree));
    printf("Leaf count: %d\n", CountLeaves(tree));
    printf("Degree-one count: %d\n", CountDegreeOne(tree));
    printf("Degree-two count: %d\n", CountDegreeTwo(tree));
    printf("Height: %d\n", GetBiTreeHeight(tree));
    printf("Level of node E: %d\n", FindNodeLevel(tree, 'E', 1));

    threaded_tree = BuildInorderThreadedTree(tree);
    if (threaded_tree != NULL) {
        printf("Inorder threaded traversal: ");
        InorderThreadTraversal(threaded_tree);
        printf("\n");
    }

    general_tree = BuildSampleGeneralTree();
    if (general_tree != NULL) {
        printf("General tree preorder: ");
        PreRootTraversal(general_tree);
        printf("\n");
        printf("General tree postorder: ");
        PostRootTraversal(general_tree);
        printf("\n");

        converted_tree = ConvertTreeToBinaryTree(general_tree);
        if (converted_tree != NULL) {
            PrintTraversalResult("Binary tree preorder converted from tree: ", PreorderTraversal, converted_tree);
            PrintTraversalResult("Binary tree inorder converted from tree: ", InorderTraversal, converted_tree);

            restored_tree = ConvertBinaryTreeToGTree(converted_tree);
            if (restored_tree != NULL) {
                printf("Restored general tree preorder: ");
                PreRootTraversal(restored_tree);
                printf("\n");
                DestroyGTree(&restored_tree);
            }

            DestroyBiTree(&converted_tree);
        }
    }

    forest = BuildSampleForest();
    if (forest != NULL) {
        printf("Forest preorder: ");
        PreorderForestTraversal(forest);
        printf("\n");

        forest_binary_tree = ConvertForestToBinaryTree(forest);
        if (forest_binary_tree != NULL) {
            PrintTraversalResult("Binary tree preorder converted from forest: ", PreorderTraversal, forest_binary_tree);
            DestroyBiTree(&forest_binary_tree);
        }
    }

    SwapChildren(tree);
    PrintTraversalResult("Preorder after swapping children: ", PreorderTraversal, tree);
    SwapChildren(tree);

    InitUnionFind(&uf, 8);
    UnionSets(&uf, 0, 1);
    UnionSets(&uf, 1, 2);
    UnionSets(&uf, 4, 5);
    UnionSets(&uf, 5, 6);
    printf("FindSet(2) = %d\n", FindSet(&uf, 2));
    printf("FindSet(6) = %d\n", FindSet(&uf, 6));
    PrintUnionFindState(&uf);

    if (BuildHuffmanTree(huffman_weights, 6, huffman_tree)) {
        PrintHuffmanTree(huffman_tree, 11);
        printf("Huffman WPL: %d\n", ComputeHuffmanWPL(huffman_tree, 6));
    }

    DestroyGTree(&forest);
    DestroyGTree(&general_tree);
    DestroyThreadTree(&threaded_tree);
    DestroyBiTree(&tree);
    return 0;
}

逐行注释版¶

/* 第1行注释：本行引入头文件，为后续用到的标准库类型和函数提供声明。 */
#include <stdbool.h>
/* 第2行注释：本行引入头文件，为后续用到的标准库类型和函数提供声明。 */
#include <stdio.h>
/* 第3行注释：本行引入头文件，为后续用到的标准库类型和函数提供声明。 */
#include <stdlib.h>
/* 第4行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第5行注释：本行定义宏常量，统一管理本章代码中的固定上限。 */
#define MAX_QUEUE_SIZE 128
/* 第6行注释：本行定义宏常量，统一管理本章代码中的固定上限。 */
#define MAX_HUFFMAN_NODES 128
/* 第7行注释：本行定义宏常量，统一管理本章代码中的固定上限。 */
#define MAX_UNION_FIND_SIZE 32
/* 第8行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第9行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 二叉链表结点：data 保存当前结点值，lchild/rchild 分别指向左右孩子。 */
/* 第10行注释：本行开始定义结构体类型，把相关字段组织成一个整体。 */
typedef struct BiTNode {
/* 第11行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    char data;
/* 第12行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    struct BiTNode *lchild;
/* 第13行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    struct BiTNode *rchild;
/* 第14行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
} BiTNode, *BiTree;
/* 第15行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第16行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 顺序队列结点数组：层序遍历时需要按先进先出的顺序管理结点。 */
/* 第17行注释：本行开始定义结构体类型，把相关字段组织成一个整体。 */
typedef struct {
/* 第18行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    BiTree data[MAX_QUEUE_SIZE];
/* 第19行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int front;
/* 第20行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int rear;
/* 第21行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
} BiTreeQueue;
/* 第22行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第23行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 并查集：parent[i] < 0 表示 i 是根，且绝对值表示集合大小。 */
/* 第24行注释：本行开始定义结构体类型，把相关字段组织成一个整体。 */
typedef struct {
/* 第25行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int parent[MAX_UNION_FIND_SIZE];
/* 第26行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int size;
/* 第27行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
} UnionFind;
/* 第28行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第29行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 哈夫曼树数组结点：weight 为权值，parent/left/right 存储父子关系下标。 */
/* 第30行注释：本行开始定义结构体类型，把相关字段组织成一个整体。 */
typedef struct {
/* 第31行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int weight;
/* 第32行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int parent;
/* 第33行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int left;
/* 第34行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int right;
/* 第35行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
} HuffmanNode;
/* 第36行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第37行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 线索二叉树结点：ltag/rtag 为 false 表示指向孩子，true 表示指向前驱或后继线索。 */
/* 第38行注释：本行开始定义结构体类型，把相关字段组织成一个整体。 */
typedef struct ThreadNode {
/* 第39行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    char data;
/* 第40行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    struct ThreadNode *lchild;
/* 第41行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    struct ThreadNode *rchild;
/* 第42行注释：本行处理线索标志位，用来区分当前指针是孩子还是线索。 */
    bool ltag;
/* 第43行注释：本行处理线索标志位，用来区分当前指针是孩子还是线索。 */
    bool rtag;
/* 第44行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
} ThreadNode, *ThreadTree;
/* 第45行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第46行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 普通树 / 森林结点：first_child 指向第一个孩子，next_sibling 指向下一个兄弟。 */
/* 第47行注释：本行开始定义结构体类型，把相关字段组织成一个整体。 */
typedef struct GTreeNode {
/* 第48行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    char data;
/* 第49行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    struct GTreeNode *first_child;
/* 第50行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    struct GTreeNode *next_sibling;
/* 第51行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
} GTreeNode, *GTree;
/* 第52行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第53行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 初始化队列，让 front 和 rear 都回到 0。 */
/* 第54行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
void InitBiTreeQueue(BiTreeQueue *queue) {
/* 第55行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (queue == NULL) {
/* 第56行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        return;
/* 第57行注释：本行结束当前代码块。 */
    }
/* 第58行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    queue->front = 0;
/* 第59行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    queue->rear = 0;
/* 第60行注释：本行结束当前代码块。 */
}
/* 第61行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第62行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 判断队列是否为空：front 和 rear 相等时说明没有元素。 */
/* 第63行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
bool IsBiTreeQueueEmpty(const BiTreeQueue *queue) {
/* 第64行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return queue == NULL || queue->front == queue->rear;
/* 第65行注释：本行结束当前代码块。 */
}
/* 第66行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第67行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 入队：把一个二叉树结点指针压到队尾，供层序遍历后续处理。 */
/* 第68行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
bool EnqueueBiTree(BiTreeQueue *queue, BiTree node) {
/* 第69行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int next_rear;
/* 第70行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第71行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (queue == NULL) {
/* 第72行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return false;
/* 第73行注释：本行结束当前代码块。 */
    }
/* 第74行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第75行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    next_rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
/* 第76行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (next_rear == queue->front) {
/* 第77行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return false;
/* 第78行注释：本行结束当前代码块。 */
    }
/* 第79行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第80行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    queue->data[queue->rear] = node;
/* 第81行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    queue->rear = next_rear;
/* 第82行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return true;
/* 第83行注释：本行结束当前代码块。 */
}
/* 第84行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第85行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 出队：取出当前队头结点，并让队头向前移动一格。 */
/* 第86行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
bool DequeueBiTree(BiTreeQueue *queue, BiTree *node) {
/* 第87行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (queue == NULL || node == NULL || IsBiTreeQueueEmpty(queue)) {
/* 第88行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return false;
/* 第89行注释：本行结束当前代码块。 */
    }
/* 第90行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第91行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    *node = queue->data[queue->front];
/* 第92行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
/* 第93行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return true;
/* 第94行注释：本行结束当前代码块。 */
}
/* 第95行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第96行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 创建一个新结点：先申请内存，再把左右孩子指针置空。 */
/* 第97行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
BiTree CreateNode(char data) {
/* 第98行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    BiTree node;
/* 第99行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第100行注释：本行动态申请内存，为新结点分配可用存储空间。 */
    node = (BiTree)malloc(sizeof(BiTNode));
/* 第101行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (node == NULL) {
/* 第102行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return NULL;
/* 第103行注释：本行结束当前代码块。 */
    }
/* 第104行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第105行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    node->data = data;
/* 第106行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    node->lchild = NULL;
/* 第107行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    node->rchild = NULL;
/* 第108行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return node;
/* 第109行注释：本行结束当前代码块。 */
}
/* 第110行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第111行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 按先序字符串创建二叉树：'#' 表示空结点，适合教材演示递归建树。 */
/* 第112行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
BiTree CreateBiTreeByPreorder(const char **cursor) {
/* 第113行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    BiTree root;
/* 第114行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第115行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (cursor == NULL || *cursor == NULL || **cursor == '\0') {
/* 第116行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return NULL;
/* 第117行注释：本行结束当前代码块。 */
    }
/* 第118行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第119行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (**cursor == '#') {
/* 第120行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        (*cursor)++;
/* 第121行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return NULL;
/* 第122行注释：本行结束当前代码块。 */
    }
/* 第123行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第124行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    root = CreateNode(**cursor);
/* 第125行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (root == NULL) {
/* 第126行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return NULL;
/* 第127行注释：本行结束当前代码块。 */
    }
/* 第128行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第129行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    (*cursor)++;
/* 第130行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    root->lchild = CreateBiTreeByPreorder(cursor);
/* 第131行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    root->rchild = CreateBiTreeByPreorder(cursor);
/* 第132行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return root;
/* 第133行注释：本行结束当前代码块。 */
}
/* 第134行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第135行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 销毁二叉树：先释放左右子树，再释放当前结点。 */
/* 第136行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
void DestroyBiTree(BiTree *tree) {
/* 第137行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL || *tree == NULL) {
/* 第138行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        return;
/* 第139行注释：本行结束当前代码块。 */
    }
/* 第140行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第141行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    DestroyBiTree(&((*tree)->lchild));
/* 第142行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    DestroyBiTree(&((*tree)->rchild));
/* 第143行注释：本行释放之前动态申请的内存，避免产生内存泄漏。 */
    free(*tree);
/* 第144行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    *tree = NULL;
/* 第145行注释：本行结束当前代码块。 */
}
/* 第146行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第147行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 访问函数：统一打印一个结点的数据，方便各类遍历复用。 */
/* 第148行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
void VisitNode(BiTree node) {
/* 第149行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (node == NULL) {
/* 第150行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        return;
/* 第151行注释：本行结束当前代码块。 */
    }
/* 第152行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
    printf("%c ", node->data);
/* 第153行注释：本行结束当前代码块。 */
}
/* 第154行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第155行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 先序遍历：先访问根，再访问左子树，最后访问右子树。 */
/* 第156行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
void PreorderTraversal(BiTree tree) {
/* 第157行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL) {
/* 第158行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        return;
/* 第159行注释：本行结束当前代码块。 */
    }
/* 第160行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第161行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    VisitNode(tree);
/* 第162行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    PreorderTraversal(tree->lchild);
/* 第163行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    PreorderTraversal(tree->rchild);
/* 第164行注释：本行结束当前代码块。 */
}
/* 第165行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第166行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 中序遍历：先访问左子树，再访问根，最后访问右子树。 */
/* 第167行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
void InorderTraversal(BiTree tree) {
/* 第168行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL) {
/* 第169行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        return;
/* 第170行注释：本行结束当前代码块。 */
    }
/* 第171行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第172行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    InorderTraversal(tree->lchild);
/* 第173行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    VisitNode(tree);
/* 第174行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    InorderTraversal(tree->rchild);
/* 第175行注释：本行结束当前代码块。 */
}
/* 第176行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第177行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 后序遍历：先访问左右子树，最后访问根。 */
/* 第178行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
void PostorderTraversal(BiTree tree) {
/* 第179行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL) {
/* 第180行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        return;
/* 第181行注释：本行结束当前代码块。 */
    }
/* 第182行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第183行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    PostorderTraversal(tree->lchild);
/* 第184行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    PostorderTraversal(tree->rchild);
/* 第185行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    VisitNode(tree);
/* 第186行注释：本行结束当前代码块。 */
}
/* 第187行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第188行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 层序遍历：使用队列按层从左到右访问所有结点。 */
/* 第189行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
void LevelOrderTraversal(BiTree tree) {
/* 第190行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    BiTreeQueue queue;
/* 第191行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    BiTree current;
/* 第192行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第193行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL) {
/* 第194行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        return;
/* 第195行注释：本行结束当前代码块。 */
    }
/* 第196行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第197行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    InitBiTreeQueue(&queue);
/* 第198行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    EnqueueBiTree(&queue, tree);
/* 第199行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第200行注释：本行开始循环，只要条件成立就持续重复执行。 */
    while (!IsBiTreeQueueEmpty(&queue)) {
/* 第201行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        DequeueBiTree(&queue, &current);
/* 第202行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        VisitNode(current);
/* 第203行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第204行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
        if (current->lchild != NULL) {
/* 第205行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
            EnqueueBiTree(&queue, current->lchild);
/* 第206行注释：本行结束当前代码块。 */
        }
/* 第207行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
        if (current->rchild != NULL) {
/* 第208行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
            EnqueueBiTree(&queue, current->rchild);
/* 第209行注释：本行结束当前代码块。 */
        }
/* 第210行注释：本行结束当前代码块。 */
    }
/* 第211行注释：本行结束当前代码块。 */
}
/* 第212行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第213行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 统计结点总数：当前结点算 1，再加左右子树结点数。 */
/* 第214行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
int CountNodes(BiTree tree) {
/* 第215行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL) {
/* 第216行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return 0;
/* 第217行注释：本行结束当前代码块。 */
    }
/* 第218行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return 1 + CountNodes(tree->lchild) + CountNodes(tree->rchild);
/* 第219行注释：本行结束当前代码块。 */
}
/* 第220行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第221行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 统计叶子结点：左右孩子都为空时，这个结点就是叶子。 */
/* 第222行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
int CountLeaves(BiTree tree) {
/* 第223行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL) {
/* 第224行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return 0;
/* 第225行注释：本行结束当前代码块。 */
    }
/* 第226行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree->lchild == NULL && tree->rchild == NULL) {
/* 第227行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return 1;
/* 第228行注释：本行结束当前代码块。 */
    }
/* 第229行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return CountLeaves(tree->lchild) + CountLeaves(tree->rchild);
/* 第230行注释：本行结束当前代码块。 */
}
/* 第231行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第232行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 统计度为 1 的结点：恰好只有一个孩子的结点记为 1。 */
/* 第233行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
int CountDegreeOne(BiTree tree) {
/* 第234行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int current;
/* 第235行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第236行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL) {
/* 第237行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return 0;
/* 第238行注释：本行结束当前代码块。 */
    }
/* 第239行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第240行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    current = ((tree->lchild == NULL) ^ (tree->rchild == NULL)) ? 1 : 0;
/* 第241行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return current + CountDegreeOne(tree->lchild) + CountDegreeOne(tree->rchild);
/* 第242行注释：本行结束当前代码块。 */
}
/* 第243行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第244行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 统计度为 2 的结点：左右孩子都非空的结点记为 1。 */
/* 第245行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
int CountDegreeTwo(BiTree tree) {
/* 第246行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int current;
/* 第247行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第248行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL) {
/* 第249行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return 0;
/* 第250行注释：本行结束当前代码块。 */
    }
/* 第251行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第252行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    current = (tree->lchild != NULL && tree->rchild != NULL) ? 1 : 0;
/* 第253行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return current + CountDegreeTwo(tree->lchild) + CountDegreeTwo(tree->rchild);
/* 第254行注释：本行结束当前代码块。 */
}
/* 第255行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第256行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 求二叉树高度：取左右子树高度较大者，再加上当前根这一层。 */
/* 第257行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
int GetBiTreeHeight(BiTree tree) {
/* 第258行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int left_height;
/* 第259行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int right_height;
/* 第260行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第261行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL) {
/* 第262行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return 0;
/* 第263行注释：本行结束当前代码块。 */
    }
/* 第264行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第265行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    left_height = GetBiTreeHeight(tree->lchild);
/* 第266行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    right_height = GetBiTreeHeight(tree->rchild);
/* 第267行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return (left_height > right_height ? left_height : right_height) + 1;
/* 第268行注释：本行结束当前代码块。 */
}
/* 第269行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第270行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 查找指定字符所在层次：根在第 1 层，找到就返回层号，找不到返回 0。 */
/* 第271行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
int FindNodeLevel(BiTree tree, char target, int level) {
/* 第272行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int left_result;
/* 第273行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int right_result;
/* 第274行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第275行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL) {
/* 第276行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return 0;
/* 第277行注释：本行结束当前代码块。 */
    }
/* 第278行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第279行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree->data == target) {
/* 第280行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return level;
/* 第281行注释：本行结束当前代码块。 */
    }
/* 第282行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第283行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    left_result = FindNodeLevel(tree->lchild, target, level + 1);
/* 第284行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (left_result != 0) {
/* 第285行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return left_result;
/* 第286行注释：本行结束当前代码块。 */
    }
/* 第287行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第288行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    right_result = FindNodeLevel(tree->rchild, target, level + 1);
/* 第289行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return right_result;
/* 第290行注释：本行结束当前代码块。 */
}
/* 第291行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第292行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 交换每个结点的左右孩子：这是二叉树“镜像化”的经典递归模板。 */
/* 第293行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
void SwapChildren(BiTree tree) {
/* 第294行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    BiTree temp;
/* 第295行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第296行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL) {
/* 第297行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        return;
/* 第298行注释：本行结束当前代码块。 */
    }
/* 第299行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第300行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    temp = tree->lchild;
/* 第301行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    tree->lchild = tree->rchild;
/* 第302行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    tree->rchild = temp;
/* 第303行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第304行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    SwapChildren(tree->lchild);
/* 第305行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    SwapChildren(tree->rchild);
/* 第306行注释：本行结束当前代码块。 */
}
/* 第307行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第308行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 输出某种遍历结果时先打印标题，让演示结果更容易对应到概念。 */
/* 第309行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
void PrintTraversalResult(const char *title, void (*traversal)(BiTree), BiTree tree) {
/* 第310行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (title == NULL || traversal == NULL) {
/* 第311行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        return;
/* 第312行注释：本行结束当前代码块。 */
    }
/* 第313行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第314行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
    printf("%s", title);
/* 第315行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    traversal(tree);
/* 第316行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
    printf("\n");
/* 第317行注释：本行结束当前代码块。 */
}
/* 第318行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第319行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 创建线索二叉树结点：先复制数据，再把左右指针和标志位置成初始状态。 */
/* 第320行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
ThreadTree CreateThreadNode(char data) {
/* 第321行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    ThreadTree node;
/* 第322行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第323行注释：本行动态申请内存，为新结点分配可用存储空间。 */
    node = (ThreadTree)malloc(sizeof(ThreadNode));
/* 第324行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (node == NULL) {
/* 第325行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return NULL;
/* 第326行注释：本行结束当前代码块。 */
    }
/* 第327行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第328行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    node->data = data;
/* 第329行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    node->lchild = NULL;
/* 第330行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    node->rchild = NULL;
/* 第331行注释：本行处理线索标志位，用来区分当前指针是孩子还是线索。 */
    node->ltag = false;
/* 第332行注释：本行处理线索标志位，用来区分当前指针是孩子还是线索。 */
    node->rtag = false;
/* 第333行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return node;
/* 第334行注释：本行结束当前代码块。 */
}
/* 第335行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第336行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 把普通二叉树克隆成线索二叉树结点结构，方便后续在线索化时不破坏原树。 */
/* 第337行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
ThreadTree CloneBiTreeToThreadTree(BiTree tree) {
/* 第338行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    ThreadTree root;
/* 第339行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第340行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL) {
/* 第341行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return NULL;
/* 第342行注释：本行结束当前代码块。 */
    }
/* 第343行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第344行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    root = CreateThreadNode(tree->data);
/* 第345行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (root == NULL) {
/* 第346行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return NULL;
/* 第347行注释：本行结束当前代码块。 */
    }
/* 第348行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第349行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    root->lchild = CloneBiTreeToThreadTree(tree->lchild);
/* 第350行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    root->rchild = CloneBiTreeToThreadTree(tree->rchild);
/* 第351行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return root;
/* 第352行注释：本行结束当前代码块。 */
}
/* 第353行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第354行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 销毁线索二叉树：只有 tag 为 false 时，左右指针才是真孩子，才需要继续递归释放。 */
/* 第355行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
void DestroyThreadTree(ThreadTree *tree) {
/* 第356行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL || *tree == NULL) {
/* 第357行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        return;
/* 第358行注释：本行结束当前代码块。 */
    }
/* 第359行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第360行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (!(*tree)->ltag) {
/* 第361行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        DestroyThreadTree(&((*tree)->lchild));
/* 第362行注释：本行结束当前代码块。 */
    }
/* 第363行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (!(*tree)->rtag) {
/* 第364行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        DestroyThreadTree(&((*tree)->rchild));
/* 第365行注释：本行结束当前代码块。 */
    }
/* 第366行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第367行注释：本行释放之前动态申请的内存，避免产生内存泄漏。 */
    free(*tree);
/* 第368行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    *tree = NULL;
/* 第369行注释：本行结束当前代码块。 */
}
/* 第370行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第371行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 中序线索化：pre 始终指向刚刚访问完成的前一个结点，用它补前驱和后继线索。 */
/* 第372行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
void InorderThreading(ThreadTree node, ThreadTree *pre) {
/* 第373行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (node == NULL) {
/* 第374行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        return;
/* 第375行注释：本行结束当前代码块。 */
    }
/* 第376行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第377行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (node->lchild != NULL) {
/* 第378行注释：本行涉及 pre 指针，它表示刚刚访问完成的前一个结点。 */
        InorderThreading(node->lchild, pre);
/* 第379行注释：本行结束当前代码块。 */
    }
/* 第380行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第381行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (node->lchild == NULL) {
/* 第382行注释：本行处理线索标志位，用来区分当前指针是孩子还是线索。 */
        node->ltag = true;
/* 第383行注释：本行涉及 pre 指针，它表示刚刚访问完成的前一个结点。 */
        node->lchild = *pre;
/* 第384行注释：本行结束当前代码块。 */
    }
/* 第385行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第386行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (*pre != NULL && (*pre)->rchild == NULL) {
/* 第387行注释：本行处理线索标志位，用来区分当前指针是孩子还是线索。 */
        (*pre)->rtag = true;
/* 第388行注释：本行涉及 pre 指针，它表示刚刚访问完成的前一个结点。 */
        (*pre)->rchild = node;
/* 第389行注释：本行结束当前代码块。 */
    }
/* 第390行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第391行注释：本行涉及 pre 指针，它表示刚刚访问完成的前一个结点。 */
    *pre = node;
/* 第392行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第393行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (node->rchild != NULL) {
/* 第394行注释：本行涉及 pre 指针，它表示刚刚访问完成的前一个结点。 */
        InorderThreading(node->rchild, pre);
/* 第395行注释：本行结束当前代码块。 */
    }
/* 第396行注释：本行结束当前代码块。 */
}
/* 第397行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第398行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 基于普通二叉树构造中序线索二叉树：先克隆，再统一完成线索化。 */
/* 第399行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
ThreadTree BuildInorderThreadedTree(BiTree tree) {
/* 第400行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    ThreadTree threaded_root;
/* 第401行注释：本行涉及 pre 指针，它表示刚刚访问完成的前一个结点。 */
    ThreadTree pre;
/* 第402行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第403行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    threaded_root = CloneBiTreeToThreadTree(tree);
/* 第404行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (threaded_root == NULL) {
/* 第405行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return NULL;
/* 第406行注释：本行结束当前代码块。 */
    }
/* 第407行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第408行注释：本行涉及 pre 指针，它表示刚刚访问完成的前一个结点。 */
    pre = NULL;
/* 第409行注释：本行涉及 pre 指针，它表示刚刚访问完成的前一个结点。 */
    InorderThreading(threaded_root, &pre);
/* 第410行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (pre != NULL && pre->rchild == NULL) {
/* 第411行注释：本行处理线索标志位，用来区分当前指针是孩子还是线索。 */
        pre->rtag = true;
/* 第412行注释：本行涉及 pre 指针，它表示刚刚访问完成的前一个结点。 */
        pre->rchild = NULL;
/* 第413行注释：本行结束当前代码块。 */
    }
/* 第414行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第415行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return threaded_root;
/* 第416行注释：本行结束当前代码块。 */
}
/* 第417行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第418行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 找到中序线索二叉树中的第一个结点：一路沿真正的左孩子走到底。 */
/* 第419行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
ThreadTree FirstInorderThreadNode(ThreadTree tree) {
/* 第420行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL) {
/* 第421行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return NULL;
/* 第422行注释：本行结束当前代码块。 */
    }
/* 第423行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第424行注释：本行开始循环，只要条件成立就持续重复执行。 */
    while (!tree->ltag && tree->lchild != NULL) {
/* 第425行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        tree = tree->lchild;
/* 第426行注释：本行结束当前代码块。 */
    }
/* 第427行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return tree;
/* 第428行注释：本行结束当前代码块。 */
}
/* 第429行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第430行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 找中序下一个结点：若右指针是线索就直接跟过去，否则去右子树找最左下结点。 */
/* 第431行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
ThreadTree NextInorderThreadNode(ThreadTree node) {
/* 第432行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (node == NULL) {
/* 第433行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return NULL;
/* 第434行注释：本行结束当前代码块。 */
    }
/* 第435行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第436行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (node->rtag) {
/* 第437行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return node->rchild;
/* 第438行注释：本行结束当前代码块。 */
    }
/* 第439行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第440行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return FirstInorderThreadNode(node->rchild);
/* 第441行注释：本行结束当前代码块。 */
}
/* 第442行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第443行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 用线索完成中序遍历：遍历时不再需要栈，也不需要递归。 */
/* 第444行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
void InorderThreadTraversal(ThreadTree tree) {
/* 第445行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    ThreadTree current;
/* 第446行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第447行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    current = FirstInorderThreadNode(tree);
/* 第448行注释：本行开始循环，只要条件成立就持续重复执行。 */
    while (current != NULL) {
/* 第449行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
        printf("%c ", current->data);
/* 第450行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        current = NextInorderThreadNode(current);
/* 第451行注释：本行结束当前代码块。 */
    }
/* 第452行注释：本行结束当前代码块。 */
}
/* 第453行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第454行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 创建普通树结点：先保存数据，再把孩子和兄弟指针置空。 */
/* 第455行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
GTree CreateGTreeNode(char data) {
/* 第456行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree node;
/* 第457行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第458行注释：本行动态申请内存，为新结点分配可用存储空间。 */
    node = (GTree)malloc(sizeof(GTreeNode));
/* 第459行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (node == NULL) {
/* 第460行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return NULL;
/* 第461行注释：本行结束当前代码块。 */
    }
/* 第462行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第463行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    node->data = data;
/* 第464行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    node->first_child = NULL;
/* 第465行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    node->next_sibling = NULL;
/* 第466行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return node;
/* 第467行注释：本行结束当前代码块。 */
}
/* 第468行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第469行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 销毁普通树 / 森林：先释放孩子子树，再释放兄弟链，最后释放当前结点。 */
/* 第470行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
void DestroyGTree(GTree *tree) {
/* 第471行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL || *tree == NULL) {
/* 第472行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        return;
/* 第473行注释：本行结束当前代码块。 */
    }
/* 第474行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第475行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    DestroyGTree(&((*tree)->first_child));
/* 第476行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    DestroyGTree(&((*tree)->next_sibling));
/* 第477行注释：本行释放之前动态申请的内存，避免产生内存泄漏。 */
    free(*tree);
/* 第478行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    *tree = NULL;
/* 第479行注释：本行结束当前代码块。 */
}
/* 第480行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第481行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 先根遍历普通树：先访问根，再从左到右依次处理所有孩子。 */
/* 第482行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
void PreRootTraversal(GTree tree) {
/* 第483行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree child;
/* 第484行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第485行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL) {
/* 第486行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        return;
/* 第487行注释：本行结束当前代码块。 */
    }
/* 第488行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第489行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
    printf("%c ", tree->data);
/* 第490行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    child = tree->first_child;
/* 第491行注释：本行开始循环，只要条件成立就持续重复执行。 */
    while (child != NULL) {
/* 第492行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        PreRootTraversal(child);
/* 第493行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
        child = child->next_sibling;
/* 第494行注释：本行结束当前代码块。 */
    }
/* 第495行注释：本行结束当前代码块。 */
}
/* 第496行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第497行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 后根遍历普通树：先处理完所有孩子，最后再访问根结点。 */
/* 第498行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
void PostRootTraversal(GTree tree) {
/* 第499行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree child;
/* 第500行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第501行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL) {
/* 第502行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        return;
/* 第503行注释：本行结束当前代码块。 */
    }
/* 第504行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第505行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    child = tree->first_child;
/* 第506行注释：本行开始循环，只要条件成立就持续重复执行。 */
    while (child != NULL) {
/* 第507行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        PostRootTraversal(child);
/* 第508行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
        child = child->next_sibling;
/* 第509行注释：本行结束当前代码块。 */
    }
/* 第510行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
    printf("%c ", tree->data);
/* 第511行注释：本行结束当前代码块。 */
}
/* 第512行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第513行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 先序打印森林：把每一棵树都当作一棵独立的普通树，按根链从左到右依次输出。 */
/* 第514行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
void PreorderForestTraversal(GTree forest) {
/* 第515行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree current_tree;
/* 第516行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第517行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    current_tree = forest;
/* 第518行注释：本行开始循环，只要条件成立就持续重复执行。 */
    while (current_tree != NULL) {
/* 第519行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        PreRootTraversal(current_tree);
/* 第520行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
        current_tree = current_tree->next_sibling;
/* 第521行注释：本行结束当前代码块。 */
    }
/* 第522行注释：本行结束当前代码块。 */
}
/* 第523行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第524行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 把普通树转换成二叉树：第一个孩子变左孩子，下一个兄弟变右孩子。 */
/* 第525行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
BiTree ConvertTreeToBinaryTree(GTree tree) {
/* 第526行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    BiTree root;
/* 第527行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第528行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL) {
/* 第529行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return NULL;
/* 第530行注释：本行结束当前代码块。 */
    }
/* 第531行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第532行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    root = CreateNode(tree->data);
/* 第533行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (root == NULL) {
/* 第534行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return NULL;
/* 第535行注释：本行结束当前代码块。 */
    }
/* 第536行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第537行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    root->lchild = ConvertTreeToBinaryTree(tree->first_child);
/* 第538行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    root->rchild = ConvertTreeToBinaryTree(tree->next_sibling);
/* 第539行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return root;
/* 第540行注释：本行结束当前代码块。 */
}
/* 第541行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第542行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 把森林转换成二叉树：森林的第一棵树作根，其余树通过右兄弟链接在一起。 */
/* 第543行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
BiTree ConvertForestToBinaryTree(GTree forest) {
/* 第544行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return ConvertTreeToBinaryTree(forest);
/* 第545行注释：本行结束当前代码块。 */
}
/* 第546行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第547行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 把二叉树转回普通树 / 森林：左孩子还原成第一个孩子，右孩子还原成下一个兄弟。 */
/* 第548行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
GTree ConvertBinaryTreeToGTree(BiTree tree) {
/* 第549行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree root;
/* 第550行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第551行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL) {
/* 第552行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return NULL;
/* 第553行注释：本行结束当前代码块。 */
    }
/* 第554行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第555行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    root = CreateGTreeNode(tree->data);
/* 第556行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (root == NULL) {
/* 第557行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return NULL;
/* 第558行注释：本行结束当前代码块。 */
    }
/* 第559行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第560行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    root->first_child = ConvertBinaryTreeToGTree(tree->lchild);
/* 第561行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    root->next_sibling = ConvertBinaryTreeToGTree(tree->rchild);
/* 第562行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return root;
/* 第563行注释：本行结束当前代码块。 */
}
/* 第564行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第565行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 构造一棵示例树：A 的孩子为 B、C、D；B 的孩子为 E、F；D 的孩子为 G。 */
/* 第566行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
GTree BuildSampleGeneralTree(void) {
/* 第567行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree a;
/* 第568行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree b;
/* 第569行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree c;
/* 第570行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree d;
/* 第571行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree e;
/* 第572行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree f;
/* 第573行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree g;
/* 第574行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第575行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    a = CreateGTreeNode('A');
/* 第576行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    b = CreateGTreeNode('B');
/* 第577行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    c = CreateGTreeNode('C');
/* 第578行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    d = CreateGTreeNode('D');
/* 第579行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    e = CreateGTreeNode('E');
/* 第580行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    f = CreateGTreeNode('F');
/* 第581行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    g = CreateGTreeNode('G');
/* 第582行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第583行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (a == NULL || b == NULL || c == NULL || d == NULL ||
/* 第584行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        e == NULL || f == NULL || g == NULL) {
/* 第585行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        DestroyGTree(&a);
/* 第586行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        DestroyGTree(&b);
/* 第587行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        DestroyGTree(&c);
/* 第588行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        DestroyGTree(&d);
/* 第589行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        DestroyGTree(&e);
/* 第590行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        DestroyGTree(&f);
/* 第591行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        DestroyGTree(&g);
/* 第592行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return NULL;
/* 第593行注释：本行结束当前代码块。 */
    }
/* 第594行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第595行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    a->first_child = b;
/* 第596行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    b->next_sibling = c;
/* 第597行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    c->next_sibling = d;
/* 第598行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    b->first_child = e;
/* 第599行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    e->next_sibling = f;
/* 第600行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    d->first_child = g;
/* 第601行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return a;
/* 第602行注释：本行结束当前代码块。 */
}
/* 第603行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第604行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 构造一个示例森林：第一棵树是 A-B/C，第二棵树是 X-Y/Z。 */
/* 第605行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
GTree BuildSampleForest(void) {
/* 第606行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree a;
/* 第607行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree b;
/* 第608行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree c;
/* 第609行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree x;
/* 第610行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree y;
/* 第611行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree z;
/* 第612行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第613行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    a = CreateGTreeNode('A');
/* 第614行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    b = CreateGTreeNode('B');
/* 第615行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    c = CreateGTreeNode('C');
/* 第616行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    x = CreateGTreeNode('X');
/* 第617行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    y = CreateGTreeNode('Y');
/* 第618行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    z = CreateGTreeNode('Z');
/* 第619行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第620行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (a == NULL || b == NULL || c == NULL || x == NULL || y == NULL || z == NULL) {
/* 第621行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        DestroyGTree(&a);
/* 第622行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        DestroyGTree(&b);
/* 第623行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        DestroyGTree(&c);
/* 第624行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        DestroyGTree(&x);
/* 第625行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        DestroyGTree(&y);
/* 第626行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        DestroyGTree(&z);
/* 第627行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return NULL;
/* 第628行注释：本行结束当前代码块。 */
    }
/* 第629行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第630行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    a->first_child = b;
/* 第631行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    b->next_sibling = c;
/* 第632行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    x->first_child = y;
/* 第633行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    y->next_sibling = z;
/* 第634行注释：本行处理普通树的孩子兄弟表示法，描述第一个孩子和下一个兄弟之间的关系。 */
    a->next_sibling = x;
/* 第635行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return a;
/* 第636行注释：本行结束当前代码块。 */
}
/* 第637行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第638行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 初始化并查集：开始时每个元素自成一个集合，大小都为 1。 */
/* 第639行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
void InitUnionFind(UnionFind *uf, int size) {
/* 第640行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int i;
/* 第641行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第642行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (uf == NULL || size <= 0 || size > MAX_UNION_FIND_SIZE) {
/* 第643行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        return;
/* 第644行注释：本行结束当前代码块。 */
    }
/* 第645行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第646行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    uf->size = size;
/* 第647行注释：本行开始计数循环，通常用于顺序扫描数组或编号。 */
    for (i = 0; i < size; i++) {
/* 第648行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        uf->parent[i] = -1;
/* 第649行注释：本行结束当前代码块。 */
    }
/* 第650行注释：本行结束当前代码块。 */
}
/* 第651行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第652行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 查找根结点：路径压缩能让后续查找更快。 */
/* 第653行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
int FindSet(UnionFind *uf, int x) {
/* 第654行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (uf == NULL || x < 0 || x >= uf->size) {
/* 第655行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return -1;
/* 第656行注释：本行结束当前代码块。 */
    }
/* 第657行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第658行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (uf->parent[x] < 0) {
/* 第659行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return x;
/* 第660行注释：本行结束当前代码块。 */
    }
/* 第661行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第662行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    uf->parent[x] = FindSet(uf, uf->parent[x]);
/* 第663行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return uf->parent[x];
/* 第664行注释：本行结束当前代码块。 */
}
/* 第665行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第666行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 合并两个集合：按集合大小合并，尽量减少树高。 */
/* 第667行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
bool UnionSets(UnionFind *uf, int x, int y) {
/* 第668行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int root_x;
/* 第669行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int root_y;
/* 第670行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int temp;
/* 第671行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第672行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (uf == NULL) {
/* 第673行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return false;
/* 第674行注释：本行结束当前代码块。 */
    }
/* 第675行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第676行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    root_x = FindSet(uf, x);
/* 第677行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    root_y = FindSet(uf, y);
/* 第678行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (root_x < 0 || root_y < 0 || root_x == root_y) {
/* 第679行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return false;
/* 第680行注释：本行结束当前代码块。 */
    }
/* 第681行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第682行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (uf->parent[root_x] > uf->parent[root_y]) {
/* 第683行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        temp = root_x;
/* 第684行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        root_x = root_y;
/* 第685行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        root_y = temp;
/* 第686行注释：本行结束当前代码块。 */
    }
/* 第687行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第688行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    uf->parent[root_x] += uf->parent[root_y];
/* 第689行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    uf->parent[root_y] = root_x;
/* 第690行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return true;
/* 第691行注释：本行结束当前代码块。 */
}
/* 第692行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第693行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 打印并查集当前根信息，便于观察哪些元素已被并到同一集合。 */
/* 第694行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
void PrintUnionFindState(UnionFind *uf) {
/* 第695行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int i;
/* 第696行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第697行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (uf == NULL) {
/* 第698行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        return;
/* 第699行注释：本行结束当前代码块。 */
    }
/* 第700行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第701行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
    printf("Union-Find roots: ");
/* 第702行注释：本行开始计数循环，通常用于顺序扫描数组或编号。 */
    for (i = 0; i < uf->size; i++) {
/* 第703行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
        printf("%d->%d ", i, FindSet(uf, i));
/* 第704行注释：本行结束当前代码块。 */
    }
/* 第705行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
    printf("\n");
/* 第706行注释：本行结束当前代码块。 */
}
/* 第707行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第708行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 从未被选中过父结点的结点里，找权值最小的两棵树。 */
/* 第709行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
bool SelectTwoMinNodes(HuffmanNode *tree, int end_index, int *first, int *second) {
/* 第710行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int i;
/* 第711行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第712行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL || first == NULL || second == NULL) {
/* 第713行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return false;
/* 第714行注释：本行结束当前代码块。 */
    }
/* 第715行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第716行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    *first = -1;
/* 第717行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    *second = -1;
/* 第718行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第719行注释：本行开始计数循环，通常用于顺序扫描数组或编号。 */
    for (i = 1; i <= end_index; i++) {
/* 第720行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
        if (tree[i].parent != 0) {
/* 第721行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
            continue;
/* 第722行注释：本行结束当前代码块。 */
        }
/* 第723行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第724行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
        if (*first == -1 || tree[i].weight < tree[*first].weight) {
/* 第725行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
            *second = *first;
/* 第726行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
            *first = i;
/* 第727行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        } else if (*second == -1 || tree[i].weight < tree[*second].weight) {
/* 第728行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
            *second = i;
/* 第729行注释：本行结束当前代码块。 */
        }
/* 第730行注释：本行结束当前代码块。 */
    }
/* 第731行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第732行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return *first != -1 && *second != -1;
/* 第733行注释：本行结束当前代码块。 */
}
/* 第734行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第735行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 构造哈夫曼树：每次选两棵权值最小的树合并成新的父结点。 */
/* 第736行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
bool BuildHuffmanTree(const int *weights, int count, HuffmanNode *tree) {
/* 第737行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int total_nodes;
/* 第738行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int i;
/* 第739行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int first;
/* 第740行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int second;
/* 第741行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第742行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (weights == NULL || tree == NULL || count <= 1 || (2 * count - 1) >= MAX_HUFFMAN_NODES) {
/* 第743行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return false;
/* 第744行注释：本行结束当前代码块。 */
    }
/* 第745行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第746行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    total_nodes = 2 * count - 1;
/* 第747行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第748行注释：本行开始计数循环，通常用于顺序扫描数组或编号。 */
    for (i = 1; i <= total_nodes; i++) {
/* 第749行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        tree[i].weight = 0;
/* 第750行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        tree[i].parent = 0;
/* 第751行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        tree[i].left = 0;
/* 第752行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        tree[i].right = 0;
/* 第753行注释：本行结束当前代码块。 */
    }
/* 第754行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第755行注释：本行开始计数循环，通常用于顺序扫描数组或编号。 */
    for (i = 1; i <= count; i++) {
/* 第756行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        tree[i].weight = weights[i - 1];
/* 第757行注释：本行结束当前代码块。 */
    }
/* 第758行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第759行注释：本行开始计数循环，通常用于顺序扫描数组或编号。 */
    for (i = count + 1; i <= total_nodes; i++) {
/* 第760行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
        if (!SelectTwoMinNodes(tree, i - 1, &first, &second)) {
/* 第761行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
            return false;
/* 第762行注释：本行结束当前代码块。 */
        }
/* 第763行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第764行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        tree[first].parent = i;
/* 第765行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        tree[second].parent = i;
/* 第766行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        tree[i].left = first;
/* 第767行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        tree[i].right = second;
/* 第768行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        tree[i].weight = tree[first].weight + tree[second].weight;
/* 第769行注释：本行结束当前代码块。 */
    }
/* 第770行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第771行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return true;
/* 第772行注释：本行结束当前代码块。 */
}
/* 第773行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第774行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 计算哈夫曼树 WPL：每个叶子权值乘深度，再把它们全部加起来。 */
/* 第775行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
int ComputeHuffmanWPL(HuffmanNode *tree, int leaf_count) {
/* 第776行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int i;
/* 第777行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int parent;
/* 第778行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int depth;
/* 第779行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int wpl = 0;
/* 第780行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第781行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL || leaf_count <= 0) {
/* 第782行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return 0;
/* 第783行注释：本行结束当前代码块。 */
    }
/* 第784行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第785行注释：本行开始计数循环，通常用于顺序扫描数组或编号。 */
    for (i = 1; i <= leaf_count; i++) {
/* 第786行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        depth = 0;
/* 第787行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        parent = tree[i].parent;
/* 第788行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第789行注释：本行开始循环，只要条件成立就持续重复执行。 */
        while (parent != 0) {
/* 第790行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
            depth++;
/* 第791行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
            parent = tree[parent].parent;
/* 第792行注释：本行结束当前代码块。 */
        }
/* 第793行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第794行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        wpl += tree[i].weight * depth;
/* 第795行注释：本行结束当前代码块。 */
    }
/* 第796行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第797行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return wpl;
/* 第798行注释：本行结束当前代码块。 */
}
/* 第799行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第800行注释：本行是原始注释，用来概括下面这一小段代码的职责。 */
/* 打印哈夫曼树数组结点，帮助理解“父结点由两个最小权值合并而来”。 */
/* 第801行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
void PrintHuffmanTree(HuffmanNode *tree, int total_nodes) {
/* 第802行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    int i;
/* 第803行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第804行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL) {
/* 第805行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        return;
/* 第806行注释：本行结束当前代码块。 */
    }
/* 第807行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第808行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
    printf("index weight parent left right\n");
/* 第809行注释：本行开始计数循环，通常用于顺序扫描数组或编号。 */
    for (i = 1; i <= total_nodes; i++) {
/* 第810行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
        printf("%5d %6d %6d %4d %5d\n",
/* 第811行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
               i,
/* 第812行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
               tree[i].weight,
/* 第813行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
               tree[i].parent,
/* 第814行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
               tree[i].left,
/* 第815行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
               tree[i].right);
/* 第816行注释：本行结束当前代码块。 */
    }
/* 第817行注释：本行结束当前代码块。 */
}
/* 第818行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第819行注释：本行开始定义一个函数，下面会展开这个函数的完整实现。 */
int main(void) {
/* 第820行注释：本行涉及 pre 指针，它表示刚刚访问完成的前一个结点。 */
    const char *preorder_text = "ABD##E##CF###";
/* 第821行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    const int huffman_weights[] = {5, 2, 3, 6, 8, 9};
/* 第822行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    BiTree tree;
/* 第823行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    BiTree converted_tree;
/* 第824行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    BiTree forest_binary_tree;
/* 第825行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    ThreadTree threaded_tree;
/* 第826行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree general_tree;
/* 第827行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree restored_tree;
/* 第828行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    GTree forest;
/* 第829行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    UnionFind uf;
/* 第830行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    HuffmanNode huffman_tree[MAX_HUFFMAN_NODES];
/* 第831行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第832行注释：本行涉及 pre 指针，它表示刚刚访问完成的前一个结点。 */
    tree = CreateBiTreeByPreorder(&preorder_text);
/* 第833行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (tree == NULL) {
/* 第834行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
        printf("Failed to create binary tree.\n");
/* 第835行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
        return 1;
/* 第836行注释：本行结束当前代码块。 */
    }
/* 第837行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第838行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
    printf("Binary tree built from preorder string: ABD##E##CF###\n");
/* 第839行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    PrintTraversalResult("Preorder: ", PreorderTraversal, tree);
/* 第840行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    PrintTraversalResult("Inorder: ", InorderTraversal, tree);
/* 第841行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    PrintTraversalResult("Postorder: ", PostorderTraversal, tree);
/* 第842行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    PrintTraversalResult("Level order: ", LevelOrderTraversal, tree);
/* 第843行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第844行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
    printf("Node count: %d\n", CountNodes(tree));
/* 第845行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
    printf("Leaf count: %d\n", CountLeaves(tree));
/* 第846行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
    printf("Degree-one count: %d\n", CountDegreeOne(tree));
/* 第847行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
    printf("Degree-two count: %d\n", CountDegreeTwo(tree));
/* 第848行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
    printf("Height: %d\n", GetBiTreeHeight(tree));
/* 第849行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
    printf("Level of node E: %d\n", FindNodeLevel(tree, 'E', 1));
/* 第850行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第851行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    threaded_tree = BuildInorderThreadedTree(tree);
/* 第852行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (threaded_tree != NULL) {
/* 第853行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
        printf("Inorder threaded traversal: ");
/* 第854行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        InorderThreadTraversal(threaded_tree);
/* 第855行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
        printf("\n");
/* 第856行注释：本行结束当前代码块。 */
    }
/* 第857行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第858行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    general_tree = BuildSampleGeneralTree();
/* 第859行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (general_tree != NULL) {
/* 第860行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
        printf("General tree preorder: ");
/* 第861行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        PreRootTraversal(general_tree);
/* 第862行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
        printf("\n");
/* 第863行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
        printf("General tree postorder: ");
/* 第864行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        PostRootTraversal(general_tree);
/* 第865行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
        printf("\n");
/* 第866行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第867行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        converted_tree = ConvertTreeToBinaryTree(general_tree);
/* 第868行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
        if (converted_tree != NULL) {
/* 第869行注释：本行涉及 pre 指针，它表示刚刚访问完成的前一个结点。 */
            PrintTraversalResult("Binary tree preorder converted from tree: ", PreorderTraversal, converted_tree);
/* 第870行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
            PrintTraversalResult("Binary tree inorder converted from tree: ", InorderTraversal, converted_tree);
/* 第871行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第872行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
            restored_tree = ConvertBinaryTreeToGTree(converted_tree);
/* 第873行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
            if (restored_tree != NULL) {
/* 第874行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
                printf("Restored general tree preorder: ");
/* 第875行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
                PreRootTraversal(restored_tree);
/* 第876行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
                printf("\n");
/* 第877行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
                DestroyGTree(&restored_tree);
/* 第878行注释：本行结束当前代码块。 */
            }
/* 第879行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第880行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
            DestroyBiTree(&converted_tree);
/* 第881行注释：本行结束当前代码块。 */
        }
/* 第882行注释：本行结束当前代码块。 */
    }
/* 第883行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第884行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    forest = BuildSampleForest();
/* 第885行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (forest != NULL) {
/* 第886行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
        printf("Forest preorder: ");
/* 第887行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        PreorderForestTraversal(forest);
/* 第888行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
        printf("\n");
/* 第889行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第890行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        forest_binary_tree = ConvertForestToBinaryTree(forest);
/* 第891行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
        if (forest_binary_tree != NULL) {
/* 第892行注释：本行涉及 pre 指针，它表示刚刚访问完成的前一个结点。 */
            PrintTraversalResult("Binary tree preorder converted from forest: ", PreorderTraversal, forest_binary_tree);
/* 第893行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
            DestroyBiTree(&forest_binary_tree);
/* 第894行注释：本行结束当前代码块。 */
        }
/* 第895行注释：本行结束当前代码块。 */
    }
/* 第896行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第897行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    SwapChildren(tree);
/* 第898行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    PrintTraversalResult("Preorder after swapping children: ", PreorderTraversal, tree);
/* 第899行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    SwapChildren(tree);
/* 第900行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第901行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    InitUnionFind(&uf, 8);
/* 第902行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    UnionSets(&uf, 0, 1);
/* 第903行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    UnionSets(&uf, 1, 2);
/* 第904行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    UnionSets(&uf, 4, 5);
/* 第905行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    UnionSets(&uf, 5, 6);
/* 第906行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
    printf("FindSet(2) = %d\n", FindSet(&uf, 2));
/* 第907行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
    printf("FindSet(6) = %d\n", FindSet(&uf, 6));
/* 第908行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    PrintUnionFindState(&uf);
/* 第909行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第910行注释：本行开始条件判断，根据当前情况选择不同处理路径。 */
    if (BuildHuffmanTree(huffman_weights, 6, huffman_tree)) {
/* 第911行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
        PrintHuffmanTree(huffman_tree, 11);
/* 第912行注释：本行输出当前结果，方便把程序行为和知识点对上。 */
        printf("Huffman WPL: %d\n", ComputeHuffmanWPL(huffman_tree, 6));
/* 第913行注释：本行结束当前代码块。 */
    }
/* 第914行注释：本行是空行，用来分隔逻辑块，帮助阅读时自然停顿。 */

/* 第915行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    DestroyGTree(&forest);
/* 第916行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    DestroyGTree(&general_tree);
/* 第917行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    DestroyThreadTree(&threaded_tree);
/* 第918行注释：本行在推进当前算法步骤，请结合前后文理解它在整体过程中的作用。 */
    DestroyBiTree(&tree);
/* 第919行注释：本行返回当前函数的结果，把计算结论交还给调用者。 */
    return 0;
/* 第920行注释：本行结束当前代码块。 */
}

继续阅读¶

← 上一章代码：第4章串代码下一章代码：第6章图代码 →