二叉树遍历Inorder输出为什么不对？

Question

有人可以解释为什么我的输出错误以及如何修复它吗？

例如：我将输入A B C D E

output is giving me A B C D E

insead of Inorder Traversal: D B E A C

这是我的代码：

int main()
{
struct node *root = NULL;
int choice, n;  // item
char item;
do
{

    printf("\n1. Insert Node"); 
    printf("\n2. Traverse in Inorder");

    printf("\nEnter Choice : ");
    scanf("%d",&choice);

    switch(choice)
    {
    case 1:
        root = NULL;
        printf("\n\n Nodes : ");
        scanf("%d",&n);
        
        for(int i = 1; i <= n; i++)
        {
            printf("\nEnter data for node %d : ", i);
            scanf(" %c",&item);
            root = Create(root,item);
        }
        break;
        
    case 2:
        printf("\nBST Traversal in INORDER \n");
        Inorder(root); break;
  
    default:
        printf("\n\nINVALID OPTION  TRY AGAIN\n\n"); break;
    }
} while(choice != 3);

}

struct node *Create(struct node *root, char item)
{
if(root == NULL)
{
    root = (struct node *)malloc(sizeof(struct node));
    root->left = root->right = NULL;
    root->data = item;
    return root;
}
else
{
    if(item < root->data )
        root->left = Create(root->left,item);
    else if(item > root->data )
        root->right = Create(root->right,item);
    else
        printf(" Duplicate Element !! Not Allowed !!!");

    return(root);
}
}

void Inorder(struct node *root)
{
if( root != NULL)
{
    Inorder(root->left);
    printf(" %c ",root->data);
    Inorder(root->right);
}
}

我仔细检查了中序遍历的算法，但我的输出仍然是错误的，我不明白为什么？我错过了什么吗

Answer 1

结果符合预期。 in-order 遍历不应为您输入的 A B C D E

生成 D B E A C

这就是树的构造方式。

首先创建值为 A 的根

然后插入B。由于B > A，它作为根的右child插入：

    A
     \
      B

然后插入B。当 C > A 时，它被插入到右子树中。我们再次发现 C > B，因此新节点将作为 B 的右 child:

插入

以相同的方式插入 D，然后插入 E，得到这棵树：

请注意，这棵树根本不平衡。这就是按词法顺序插入节点时发生的情况。如果您以更随机的顺序插入它们，我们希望树会更平衡。

但是对于in-order遍历其实并不重要。您实现的是二叉 search 树 (BST)。 BST 的一个重要属性是它们的 in-order 遍历总是以正确的顺序生成数据。因此，无论您输入字母 A B C D 和 E 的顺序如何，in-order 遍历都应该 always 输出以下序列：

 A B C D E

这是正确的。

二叉树遍历Inorder输出为什么不对？

Binary tree traversal Inorder output is wrong why?

linked-list

tree

inorder