C 中的 BST 遍历

Question

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

 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

遍历的时候有空格和字符‘C’

这很可能是由于缺少

root

的初始化，正如 Joachim Pileborg 注意到的那样。

前后顺序错误

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

一个
                 \
                  乙
                   \
                    c
                     \
                      d
                       \
                        e
                         \
                          f
                           \
                            克
                             \
                              小时
                               \
                                我

输出顺序正确。

Answer 2

这些二叉搜索树 (BST) 遍历的问题受到退化树的影响，这是由于树的不平衡结构引起的

您可以通过确保树平衡来一一插入值，否则在大多数情况下树将不平衡

例如：如果插入 10,20,30

树会像

10
20
30

不喜欢

20 /
10 30

这个问题的解决方案是

使用平衡策略（例如 AVL、红黑）或随机化来避免退化树。