二叉树的打印顺序

Question

二叉树的打印顺序

颜良文丑

271120

发布于
2018-09-05

程序来源

这个程序来自k&r的《the c programming language 》第六章第五节

部分代码

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 ....."

结果

问题

请问这个输出为什么是这样，它不应该是按中序遍历的结果打印吗？

---------以下是程序全部代码---------------------------
标签： '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;
}

标签： 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];
}

标签： 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");
}