Двоичные деревья - отслеживание кода

Question

Учитывая двоичное дерево, показанное ниже, определите порядок, в котором посещаются узлы двоичного дерева, показанного ниже, при условии, что вызывается функция A (root).Предположим, что узлы и указатели дерева определены так, как показано.Предположим, что root является указателем на узел, содержащий 60. Мой ответ на эту проблему приведен ниже.Это правильно?Что я сделал не так?

                                   60
                                 /    \
                                30     90
                               /  \   / 
                              5   38  77
                               \  /  / \
                               8 32 62  88



struct treeNode{
  int data;
  struct treeNode *left, *right:
  {

struct treeNode *tree_ptr;

void A(struct treeNode *node_ptr){
    if (node_ptr != NULL){
    printf(“%d ,”,node_ptr->data);
    B(node_ptr->left);
    B(node_ptr->right);
   }   
}

void B(struct treeNode *node_ptr){
    if (node_ptr != NULL) {
    A(node_ptr->left);
    printf(“%d ,”,node_ptr->data);
    A(node_ptr->right);
   }
 }   

Ответ: В пустоте А он говорит сначала распечатать данные node_ptr->, чтобы было напечатано 60. Затем функция вызывает B (node_ptr-> влево), затем в B вызывается A (node_ptr-> left), затем вы печатаете те данные, которые равны 5. И затем вызывается A (node_ptr-> right), возвращайтесь обратно к A, печатаете эти данные, так что 8 печатается.Теперь я не уверен, что делать дальше, но я получаю логически, было бы разумно напечатать 30, но я не уверен, как получится ptr с 8 до 30. А потом, если вы продолжите в том же шаблоне, 38 будет напечатано, а 32 напечатано.Для правильного поддерева ... 90 77 62 88

Answer 1

трасса, как указано выше, не может быть правильной ни для предзаказа, ни для ордера До - 60, 30, 5, 8, 35, 32 и т. Д. В - 5, 8, 30, 32, 35 и т. Д.

Answer 2

Просто запишите полный стек выполнения с течением времени. Как это:

A(60)
  printf
  B(30)
    A(5)
      ...
    printf
    A(38)
      ...
  B(90)
    ...

(Остаток дерева оставлен читателю в качестве упражнения.)

Затем просто идите сверху вниз, записывая результаты операторов printf.

Answer 3

A - это обход по предварительному заказу, тогда как B - это обход по порядку.

Простой способ определить порядок печати - посмотреть, как вы посещаетесами узлы.Я обычно рисую контур вокруг дерева (начиная с корня и двигаясь по левому или правому краю, основываясь на поддереве, которое вы сначала просматриваете).Если я делаю обход по предварительному заказу, я распечатываю узел всякий раз, когда перемещаюсь по его внешней стороне .Если я выполняю обход в порядке, я распечатываю узел только тогда, когда я перемещаю в (это имеет смысл, когда вы смотрите обходы в порядке, потому что вы заканчиваете тем, что сначала печатаете листья; онипервые узлы, которые вы перемещаете в при рисовании контура).Если я выполняю обход после заказа, я распечатываю узел только тогда, когда я двигаюсь вдоль его внутри .

ОБНОВЛЕНИЕ

Причина30 распечатывается после 5 и 8, если вы не выполняете чисто предварительный обход.Вы перепрыгиваете между предзаказом и обходом по порядку.

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

A(60)
  printf(60)
  call B(60.left)
    B(30)
      call A(30.left)
        A(5)
          printf(5)
          call B(5.left)
            B(null)
          call B(5.right)
            B(8)
              call A(8.left)
                A(null)
              printf(8)
              call A(8.right)
                A(null)
      printf(30)
      call A(30.right)
        A(38)
        ...

Вы можете легко увидеть порядок, в котором печатаются узлы, и, что более важно, почему вы «переходите» с печати 8 напечать 30 (один рекурсивный вызов закончился, и вы отступаете на один уровень).

Answer 4

Для начала, в вашем коде есть куча ошибок. Я предполагаю, что это должно быть больше так:

struct treeNode{
  int data;
  struct treeNode *left, *right;
}

treeNode *tree_ptr;

void A(treeNode *node_ptr){
    if (node_ptr != NULL){  /// this could be just if(node_ptr)
        printf(“%d ,”,node_ptr->data);
        B(node_ptr->left);
        B(node_ptr->right);
    }   
}

void B(treeNode *node_ptr){
    if (node_ptr != NULL) {
        A(node_ptr->left);
        printf(“%d ,”,node_ptr->data);
        A(node_ptr->right);
    }
}   

Вы также смешиваете два разных алгоритма обхода. A() - предварительный заказ, B() - заказ. A() и B() должны называть себя, а не друг друга. (Еще одна причина использовать реальные имена переменных / функций вместо A, B и т. Д.)