c - C中的BST遍历

Question

使用 C 遍历树。它将接受一个字符并打印后缀/中缀/前缀。 问题是当它打印输出时，它看起来像这样

 input
 a
 b
 c
 d
 e
 f
 g
 h
 i   
    IN ORDER:   C abcdefghi
    PRE ORDER:  C  abcdefghi
    POST ORDER:  ihgfedcba C

遍历时有空格和字符“C”，前后顺序错误。我不知道出了什么问题。我在这里输入错误？使用scanf获取字符的地址？ 这是完整的代码

#include<conio.h>
#include<stdio.h>
#include<stdlib.h>



typedef struct BST
{
    char data;
    struct BST *lchild, *rchild;
}node;

node *get_node()
{
    node *temp;
    temp=(node *)malloc(sizeof(node));
    temp->lchild=NULL;
    temp->rchild=NULL;
    return temp;
}

void insert(node *root, node *new_node)
{
    if((new_node->data) < (root->data))
    {
            if((root->lchild)==NULL)
            {
                root->lchild=new_node;
            }
            else
            {
                insert(root->lchild,new_node);
            }

    }

    if(new_node->data > root->data)
    {
        if((root->rchild)==NULL)
        {
            root->rchild=new_node;
        }
        else
        {
            insert(root->rchild,new_node);
        }
    }
}

void inorder(node *temp)
{
    if(temp!=NULL)
    {
        inorder(temp->lchild);
        putchar(temp->data);
        inorder(temp->rchild);
    }
}

void preorder(node *temp)
{
    if(temp!=NULL)
    {

            putchar(temp->data);
            preorder(temp->lchild);
            preorder(temp->rchild);

    }
}

void postorder(node *temp)
{
    if(temp!=NULL)
    {
        postorder(temp->lchild);
        postorder(temp->rchild);
        putchar(temp->data);

    }

}

void main()
{
    int i;
    node *new_node, *root, *tmp, *parent;
    node *get_node();
    char c;
    clrscr();

    for(i=0;i<9;i++)
    {
        fflush(stdin);

        new_node=get_node();


        printf("\nenter element: ");
        scanf("%c", &new_node->data);

        if(root==NULL)
        {
            root = new_node;
        }   
        else
        {
            insert(root, new_node);
        }

    }

    printf("\n\nIN ORDER: ");
    inorder(root);
    printf("\nPRE ORDER: ");
    preorder(root);
    printf("\nPOST ORDER: ");
    postorder(root);




    getch();
}

Answer 1

There are spaces and the character 'C' when I traverse

这很可能是由于缺少 root 的初始化，正如 Joachim Pileborg 注意到的那样。

the pre and post order is wrong

他们不是；除了空格和“C”之外，还有退化(或病态)树

                a
                 \
                  b
                   \
                    c
                     \
                      d
                       \
                        e
                         \
                          f
                           \
                            g
                             \
                              h
                               \
                                i

其输出顺序是正确的。