Рекурсивный двоичный код обхода дерева переходит в бесконечность

Question

Я пытаюсь пересечь двоичное дерево, построенное с помощью входных данных с клавиатуры. Данные вставляется в двоичное дерево успешно. У меня есть оператор switch, где «case 2» должен пересекать (и печатать) двоичное дерево с алгоритмами обхода Inorder, Preorder и Postorder, используя рекурсию соответственно. Однако, когда вызывается «случай 2», на экране печатаются только первые данные, которые должны быть напечатаны относительно обходного пути. и он также печатается много раз (бесконечно), где мне нужно остановить компиляцию. Я был бы более чем счастлив, если бы кто-то помог мне с этим.

(RootPtr это верхний -Уровень 0- узел бинарного дерева, определенной во всем мире, и GetNode в основном функция инициализатор (используя таНос) для типа TreePtr указателей.)

Спасибо всем заранее.

Это определение структуры;

typedef struct treeItem 
{ 
    int data; 
    struct treeItem *left; 
    struct treeItem *right; 

}Tree , *TreePtr; 

Эти три функции перемещения, называемые соответственно;

void inorder (TreePtr TemPtr) 
{ 

    while(TemPtr != NULL) 
    { 
     inorder((*TemPtr).left); 
     printf(" %d ", (*TemPtr).data); 
     inorder((*TemPtr).right); 
    } 
    printf("\n"); 
} 

void preorder (TreePtr TemPtr) 
{ 
    while(TemPtr != NULL) 
    { 
     printf(" %d ", (*TemPtr).data); 
     preorder((*TemPtr).left); 
     preorder((*TemPtr).right); 
    } 
    printf("\n"); 
} 

void postorder (TreePtr TemPtr) 
{ 
    while(TemPtr != NULL) 
    { 
     postorder((*TemPtr).left); 
     postorder((*TemPtr).right); 
     printf(" %d", (*TemPtr).data); 
    } 
    printf("\n"); 
} 

Этот вопрос относится к «случаю» оператора switch;

case 2: 
      TreePtr LocPtr; 
      GetNode(&LocPtr); 
      LocPtr = RootPtr; 

      printf("\n"); 
      printf("Inorder traversal:"); 
      inorder(LocPtr); 
      printf("Preorder traversal:"); 
      preorder(LocPtr); 
      printf("Postorder traversal:"); 
      postorder(LocPtr); 
      printf("\n"); 

      break; 

Answer 1

Непрерывная петля внутри ваших функций обхода. Рекурсия будет идти во всех узлах уже.

void inorder (TreePtr TemPtr) 
{ 
    if (TemPtr != NULL) { 
     inorder((*TemPtr).left); 
     printf(" %d ", (*TemPtr).data); 
     inorder((*TemPtr).right); 
    } 

    printf("\n"); 
} 

Если вы думаете об этом, ваш параметр TemPtr не меняется в NULL, когда вы итерации в цикле. Поэтому он застревает в бесконечном цикле.

Объяснение на обходе дерева:

В вашем главном, case 2, вы называете inorder с корнем дерева в качестве параметра. Затем нам нужно пройти дерево.

inorder(LocPtr); 

В-порядке обхода является:

пойти налево ребенка ... посетить текущий узел ... иди направо ребенка

Нам нужны две вещи в рекурсивной функции/method: базовый регистр и рекурсивный вызов.

Здесь наш базовый чехол if (TemPtr != NULL). Когда это условие ложно, мы знаем, что мы достигли листа. Если TemPtr действительно является листом, мы не идем дальше к его детям (что бы порождать ошибки).

Но если TemPtr не NULL, это значит, что мы в настоящее время находимся на допустимом узле. Поэтому мы должны следовать определению обхода порядка (как указано ранее).

Мы посещаем левую ребенок:

inorder((*TemPtr).left); // equivalent to inorder(TemPtr->left); 

мы посещаем текущий узел:

printf(" %d ", (*TemPtr).data); // equivalent to printf (" %d ", TemPtr->data); 

и мы посещаем правильный ребенок:

inorder((*TemPtr).right); // equivalent to inorder(TemPtr->right); 

Когда inorder закончена , вызывающий абонент inorder продолжит где это было. Этот процесс продолжается до тех пор, пока inorder(LocPtr) не закончится, и в этот момент вы вернетесь в основное место, и все ваше дерево будет пройдено по заказу.

Самый простой способ визуализировать это - нарисовать вызовы на листе бумаги. Функции будут складываться друг на друга (main внизу) и удаляются из стека после их завершения.