如何按计数参数排序二叉树并提取文本中Top N高频单词？

嘿，这个需求我太熟了！你现在手里有个存着单词和计数的二叉树，要按频次排序输出Top N高频词，对吧？下面给你几个靠谱的实现方案，都是实际项目里能用的：

方法1：全遍历收集节点 + 排序取Top N #

这是最直观也最容易实现的方案，不管你的二叉树是啥结构（普通二叉树还是按单词排序的BST）都能用。

步骤拆解： #

• 先遍历整个二叉树，把所有节点（Node*）收集到一个动态数组或者链表中。遍历方式随便选——递归、迭代的前/中/后序遍历都行，只要能覆盖所有节点就行（迭代版更适合超大树，避免递归栈溢出）。
• 用排序函数对数组里的节点按count值降序排序（count大的排前面）。C语言里可以直接用标准库的qsort，自己写比较规则就行。
• 最后从排序后的数组里取前N个节点，输出它们的word和count就行，记得处理总单词数不足N的情况（比如总共只有3个单词，却要取Top5，那就全输出）。

代码示例（C语言）： #

// 用于qsort的比较函数：按count降序排序
int compareNodes(const void* a, const void* b) {
    Node* nodeA = *(Node**)a;
    Node* nodeB = *(Node**)b;
    return nodeB->count - nodeA->count;
}

// 迭代式中序遍历，收集所有节点到动态数组
void collectAllNodes(Node* root, Node*** nodes, int* size) {
    if (!root) return;
    Node** stack = malloc(100 * sizeof(Node*)); // 初始栈大小，可按需扩容
    int top = -1;
    Node* current = root;

    while (current || top != -1) {
        // 先遍历左子树到底
        while (current) {
            stack[++top] = current;
            current = current->left;
        }
        current = stack[top--];
        // 把当前节点加入数组
        *nodes = realloc(*nodes, (*size + 1) * sizeof(Node*));
        (*nodes)[*size] = current;
        (*size)++;
        // 遍历右子树
        current = current->right;
    }
    free(stack);
}

// 主流程调用
int main() {
    Node* treeRoot = ...; // 你的二叉树根节点
    int topN = 5; // 需要取的Top N值
    Node** nodeArray = NULL;
    int arraySize = 0;

    // 收集所有节点
    collectAllNodes(treeRoot, &nodeArray, &arraySize);
    // 排序
    qsort(nodeArray, arraySize, sizeof(Node*), compareNodes);

    // 输出Top N
    printf("Top %d 高频单词:\n", topN);
    int outputNum = (arraySize < topN) ? arraySize : topN;
    for (int i = 0; i < outputNum; i++) {
        printf("%s - %d\n", nodeArray[i]->word, nodeArray[i]->count);
    }

    // 记得释放内存
    free(nodeArray);
    // 若不需要保留原二叉树，也要记得递归释放所有节点内存
    return 0;
}

优缺点： #

• 优点：实现简单，逻辑清晰，不需要依赖二叉树的特殊结构，新手也能快速上手。
• 缺点：如果二叉树特别大，收集所有节点会占用较多内存，但绝大多数日常场景下完全够用。

方法2：遍历+最小堆维护Top N #

如果你的二叉树规模超大，不想占用太多内存，可以用最小堆来实时维护当前的Top N高频节点。这种方法只需要占用N个节点的内存，非常省空间。

步骤拆解： #

• 实现一个最小堆：堆的元素是Node*，堆的比较规则是按count从小到大排序（堆顶是当前堆里count最小的节点）。
• 遍历二叉树的每个节点：
  • 如果堆的大小还没到N，直接把当前节点插入堆。
  • 如果堆已经满了，就把当前节点的count和堆顶的count比较——如果当前count更大，就弹出堆顶，把当前节点插入堆。
• 遍历完成后，堆里的节点就是Top N高频词。不过堆里是按最小堆排序的，要输出从高到低的话，要么倒序输出，要么把堆里的元素再排一次序。

代码思路： #

你需要自己实现堆的基本操作：heapInit（初始化堆）、heapInsert（插入节点）、heapExtractMin（弹出堆顶最小元素）、heapify（堆化调整）。比如堆的结构体可以定义成：

typedef struct {
    Node** elements;
    int size;
    int capacity;
} MinHeap;

具体的堆实现代码这里就不展开了，核心就是维护堆的性质：父节点的count <= 子节点的count。

优缺点： #

• 优点：内存占用极小，只需要维护N个节点的堆，适合处理超大规模的二叉树。
• 缺点：实现复杂度比方法1高，需要自己写堆的逻辑，对新手不太友好。

额外说明：如果是按单词排序的BST怎么办？ #

看你给的示例结构，这个二叉树应该是按word排序的BST（比如"The"的左右子节点是"Project"和"of"，符合字典序），但count和word没有关联，所以不管是BST还是普通二叉树，都没办法通过简单的遍历顺序直接拿到按count排序的结果，还是得用上面两种方法。

内容的提问来源于stack exchange，提问作者Vadim Tor