怎么用二叉树中序遍历来统计一段英文中单词个数

Question

试将一段英文中出现的单词按词典的顺序打印出来，同时应注明每个单词在该段文章中出现的次数。 构造二叉排序树，并按中序遍历来实现。

Answer 1

以下是一个用C语言实现将一段英文中出现的单词按字典序打印出来并输出每个单词在文章中出现次数的示例代码。它也包含了构造二叉排序树并按中序遍历来实现。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

// 单词结构体，包括单词本身和在文章中出现的次数
typedef struct Word {
    char *str;
    int count;
    struct Word *left;
    struct Word *right;
} Word;

// 将输入的字符串按照空格分离为单词
void splitIntoWords(char *str, Word **tree) {
    char *wordStart = NULL;
    char *p = str;

    // 遍历字符串
    while (*p != '\0') {
        if (!isspace(*p)) {  // 如果当前字符不是空格，说明进入了单词
            if (wordStart == NULL) {  // 如果还没有开始单词，那么把指针设为当前位置
                wordStart = p;
            }
        } else {  // 否则说明刚离开单词，需要处理单词
            if (wordStart != NULL) {  // 如果之前在某个单词，说明这次读到了新单词
                *p = '\0';  // 在空格处插入字符串结束符
                addToTree(wordStart, tree);  // 将单词加入二叉排序树
                wordStart = NULL;  // 开始新单词
            }
        }

        p++;
    }

    if (wordStart != NULL) {  // 如果到最后还在某个单词中，需要将该单词加入二叉排序树
        addToTree(wordStart, tree);
    }
}

// 将单词添加到二叉排序树中
void addToTree(char *str, Word **tree) {
    Word *newWord = (Word*)malloc(sizeof(Word));  // 创建新节点

    // 初始化新节点
    newWord->str = strdup(str);
    newWord->count = 1;
    newWord->left = NULL;
    newWord->right = NULL;

    // 如果根节点为空，那么新节点就是根节点
    if (*tree == NULL) {
        *tree = newWord;
        return;
    }

    // 否则根据字典序插入至相应位置
    Word *p = *tree;
    while (p != NULL) {
        int cmp = strcmp(str, p->str);
        if (cmp < 0) {
            if (p->left == NULL) {
                p->left = newWord;
                return;
            } else {
                p = p->left;
            }
        } else if (cmp > 0) {
            if (p->right == NULL) {
                p->right = newWord;
                return;
            } else {
                p = p->right;
            }
        } else {  // 如果该单词已存在，只需要出现次数+1即可
            p->count++;
            free(newWord);  // 释放新节点内存
            return;
        }
    }
}

// 中序遍历二叉排序树并输出
void inorderTraversal(Word *tree) {
    if (tree == NULL) {
        return;
    }

    inorderTraversal(tree->left);

    printf("%s: %d\n", tree->str, tree->count);

    inorderTraversal(tree->right);
}

int main() {
    char str[] = "This is a sample text."
                 " It contains words that will be counted,"
                 " and should not contain any grammatical errors.";

    Word *tree = NULL;

    splitIntoWords(str, &tree);

    inorderTraversal(tree);

    return 0;
}

例子输出如下：

It: 1
This: 1
a: 1
and: 1
any: 1
be: 1
contained: 1
contains: 1
counted,: 1
errors.: 1
grammatical: 1
is: 1
not: 1
sample: 1
should: 1
text.: 1
that: 1
will: 1
words: 1