Прохождение и печать двоичного дерева по уровню

Question

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

(RootPtr - это верхний -уровень 0-узла бинарного дерева, определяемый глобально; TreeDepth() - это функция, вычисляющая «глубина» дерева, где глубина, определенная глобально, и корневой узел имеет глубину 0, а GetNode в основном функция инициализации (с использованием malloc) для указателей типа TreePtr.)

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

Вот соответствующий код:

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

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

}Tree , *TreePtr; 

Это случай переключателя, в котором я вызываю функцию (-ы) пересечения по уровню;

case 4: 
       TreePtr temp; 
       GetNode(&temp); 

       temp = RootPtr; 

       printLevelOrder(temp); 
       printf("\n\n"); 

       break; 

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

void printGivenLevel(TreePtr TemPtr, int level) 
{ 
    if (items == 0) 
     return; 
    else 
    { if(level == 0) 
     { 
      printf(" %d", (*TemPtr).data); //the line I got ERROR 
     } 
     else 
     { 
      printGivenLevel((*TemPtr).left, (level-1)); 
      printGivenLevel((*TemPtr).right, (level-1)); 
     } 
    } 
} 

void printLevelOrder(TreePtr TemPtr) 
{ 
    TreeDepth(); 
    if (items == 0) 
     printf("\nTree is empty.\n"); 
    else 
    { 
     printf("Traverse level by level:"); 

     for (int i=0; i<=Depth; i++) 
     { 
      printGivenLevel(TemPtr, i); 
     } 
    } 
} 

Answer 1

Это одна ошибка. В вашей петле:

for (int i=0; i<=Depth; i++) 

Вы проходите этот цикл Depth + 1 раз. Это означает, что вы пытаетесь получить доступ к еще одному уровню, чем есть на самом деле. В частности, при окончательном вызове printGivenLevel в точке рекурсии, где level == 1, вы уже находитесь в нижней части дерева. Теперь вы снова повторяетесь, но указатели, которые вы переходите на следующий уровень рекурсии, являются указателями на мусор (они не гарантируют, что вы укажете на то, что вам разрешен доступ или даже существует). Поэтому, когда вы пытаетесь разыменовать их, вы получаете сообщение об ошибке.

Еще одна вещь: эта реализация довольно неэффективна, так как вы много раз пересекаете дерево. Лучше сделать поиск по ширине, например, поцелуй. Таким образом, вы пройдете только дерево один раз, что намного быстрее (хотя оно использует больше памяти).