二叉樹的打印順序

程序來源

這個(gè)程序來自k&r的《the c programming language 》第六章第五節(jié)

部分代碼

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

struct tnode{
    char *word;               /* point to a text */
    int count;             /* count the text ocurrence frequence */
    struct tnode *left;     /* left child */
    struct tnode *right;    /* right child */
};

輸入

**輸入下圖的中的這句話"now is the ....."

結(jié)果

問題

請(qǐng)問這個(gè)輸出為什么是這樣，它不應(yīng)該是按中序遍歷的結(jié)果打印嗎？

---------以下是程序全部代碼---------------------------
標(biāo)簽： 'tree.c'

struct tnode{
    char *word;               /* point to a text */
    int count;             /* count the text ocurrence frequence */
    struct tnode *left;     /* left child */
    struct tnode *right;    /* right child */
};

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

#define MAXWORD 100

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

/* word frequency count */
int main()
{
    struct tnode *root; /* root node  */
    char word[MAXWORD];

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

struct tnode *talloc(void);
char* my_strdup(const char *s);

/* addtree : add a node with w,at or below p */
struct tnode *addtree(struct tnode *p, char *w)
{
    int cond;

    if ( p == NULL)     /* a new word has arrived */ 
    {
        p = talloc();   /* make a new node */
        p->word = my_strdup(w);
        p->count = 1;
        p->left = p->right = NULL;
    }
    else if ((cond = strcmp(w, p->word)) == 0)
    {
        p->count++;
    }
    else if (cond > 0)
        p->left = addtree(p->left, w);
    else 
        p->right = addtree(p->right, w);
    return p;
}

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

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

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

標(biāo)簽： getword.c

#include<ctype.h>

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

    while (isspace(c = getch()))
        ;
    if (c != EOF)
        *w++ = c;
    if (!isalpha(c))
    {
        *w = '\0';
        return c;
    }

    for ( ; --lim > 0; w++)
    {
        if(!isalnum(*w  = getch()))
        {
            ungetch(*w);
            break;
        }
    }
    *w = '\0';
    return word[0];
}

標(biāo)簽： getch.c

#include<stdio.h>
#define BUFSIZE 100

char buf[BUFSIZE];
int bufcp = 0;

int getch(void)
{
    int c;
    if(bufcp > 0)
        c = buf[--bufcp];
    else
        c = getchar();
    return c;
}

void ungetch(int c)
{
    if (bufcp < BUFSIZE)
        buf[bufcp++] = c;
    else
        printf("error: the buf is over!\n");
}