二叉树实现单词统计分享 - C语言论坛

楼主

已结贴√ 问题点数：20 回复次数：5

二叉树实现单词统计分享

当初递归理解不是很清楚，又从新去回忆了下递归，导致这个程序理解花了太长时间了。代码虽然短小，里面要学的东西不少，要加油咯。

binary_tree.cpp:

程序代码：

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

#define MAXWORD    100

struct tnode
{
    char *word;
    int count;
    struct tnode *left;
    struct tnode *right;
};

struct tnode *addtree(struct tnode*, char *);
struct tnode *talloc();
char *strdup1(char *);
void treeprint(struct tnode*);
int getword(char *, int);

int main()
{
    struct tnode *root;
    char word[MAXWORD];

    root = NULL;
    while (getword(word, MAXWORD) != EOF)
        if (isalpha(*word))
            root = addtree(root, word);
    treeprint(root);
    return 0;
    
}

struct tnode *addtree(struct tnode *p, char *w)
{
    int cond;

    if (p == NULL)
    {
        p = talloc();
        p->word = strdup1(w);
        p->count = 1;
        p->left = p->right = NULL;
    }
    else if (!(cond = strcmp(p->word, w)))
        p->count++;
    else if (cond < 0)
        p->left = addtree(p->left, w);
    else
        p->right = addtree(p->right, w);
    return p;
}

struct tnode *talloc()
{
    return (struct tnode *)malloc(sizeof(struct tnode));
}

char *strdup1(char *s)
{
    char *p;

    p = (char *)malloc(strlen(s) + 1);
    if(p != NULL)
    strcpy(p, s);
    return p;
}

void treeprint(struct tnode *p)
{
    if (p != NULL) {
        treeprint(p->left);
        printf("%4d %s\n", p->count, p->word);
        treeprint(p->right);
    }
}

getword.cpp:

程序代码：

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

int getword(char *word, int lim)
{
    int c, getch();
    void ungetch(int);
    char *w = word;

    while (isspace(c = getch()))
        ;
    if (c != EOF)
        *w++ = c;
    if (!isalpha(c)) {
        *w = '\0';
        return c;
    }
    for (; --lim; w++)
        if (!isalnum(*w = getch()))
        {
            break;
        }
    *w = '\0';
    return word[0];
}

getch.cpp:

程序代码：

#include<stdio.h>

#define BUFSIZE 100

char buf[BUFSIZE];
int bufp = 0;

int getch()
{
    return (bufp > 0) ? buf[--bufp] : getchar();
}

void ungetch(int c)
{
    if (bufp >= BUFSIZE)
        printf("ungetch: too many charaters\n");
    else
        buf[bufp++] = c;
}