Может кто-нибудь объяснить, почему мой вывод неверен и как это исправить?
например: я введу A B C D E
вывод дает мне A B C D E
вместо 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);
}
}
я дважды проверил алгоритм обхода Inorder, но мой вывод все еще неверен, я не понимаю, почему? я что-то пропустил здесь
Результат ожидаемый. Обход по порядку не должен производить D B E A C для вашего ввода A B C D E.
Вот так устроено дерево.
Сначала создается корень со значением A
Затем вставляется Б. Поскольку B > A, он вставляется как правый дочерний элемент корня:
A
\
B
Затем вставляется Б. Поскольку C > A, он вставляется в правое поддерево. Там снова мы находим C > B, поэтому новый узел будет вставлен как правый дочерний узел B:
A
\
B
\
C
Таким же образом вставляются D, а затем E, что дает это дерево:
A
\
B
\
C
\
D
\
E
Обратите внимание, что это дерево вообще не сбалансировано. Вот что происходит, когда вы вставляете узлы в их лексическом порядке. Если бы вы вставляли их в более случайном порядке, мы ожидали бы, что дерево будет более сбалансированным.
Но на самом деле это не имеет значения для обхода по порядку. Вы реализовали двоичное дерево поиска (BST). И одно важное свойство BST заключается в том, что их обход по порядку всегда дает данные в правильном порядке. Таким образом, независимо от порядка, в котором вы вводите буквы A B C D и E, обход по порядку всегда должен выводить следующую последовательность:
A B C D E
Это верно.