Блог

Может кто-нибудь объяснить, почему мой вывод неправильный и как это исправить?

например: я введу A B C D E

вывод дает мне B C D E

вместо обхода по порядку: 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",amp;choice);

    switch(choice)
    {
    case 1:
        root = NULL;
        printf("nn Nodes : ");
        scanf("%d",amp;n);
        
        for(int i = 1; i <= n; i  )
        {
            printf("nEnter data for node %d : ", i);
            scanf(" %c",amp;item);
            root = Create(root,item);
        }
        break;
        
    case 2:
        printf("nBST Traversal in INORDER n");
        Inorder(root); break;
  
    default:
        printf("nnINVALID OPTION  TRY AGAINnn"); 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);
}
}  
 

я дважды проверил алгоритм обхода по порядку, но мой вывод по-прежнему неправильный, я не понимаю, почему? я что-то пропустил здесь

Результат соответствует ожиданиям. Обход по порядку не должен создавать D B E A C для вашего ввода A B C D E

Вот как строится дерево.

Сначала создается корень со значением A

Затем вставляется B . Поскольку B> A, он вставляется как правый дочерний элемент корня:

     A
     
      B
 

Затем вставляется B . Поскольку C> A, он вставляется в нужное поддерево. Там снова мы находим C> B, поэтому новый узел будет вставлен как правильный дочерний элемент B:

     A
     
      B
       
        C
 

Таким же образом вставляются D, а затем E, что дает это дерево:

     A
     
      B
       
        C 
         
          D
           
            E
 

Обратите внимание, что это дерево вообще не сбалансировано. Это то, что происходит, когда вы вставляете узлы в их лексическом порядке. Если бы вы вставляли их в более случайном порядке, мы ожидали бы, что дерево будет более сбалансированным.

Но на самом деле это не имеет значения для обхода по порядку. То, что вы реализовали это двоичный поиск дереве (по британскому летнему времени). И одним из важных свойств BSTS является то, что их обход по порядку всегда выдает данные в правильном порядке. И поэтому, независимо от порядка, в котором вы вводите буквы A B C D и E, обход по порядку всегда должен выводить эту последовательность:

  A B C D E
 

Это правильно.