Обход после заказа для общего дерева

Question

В настоящее время я студент, чье задание связано с адаптацией методов двоичного дерева к методам общего дерева. Мой единственный вопрос: правильный ли мой пост-заказ для следующего общего дерева? Если это так, то я знаю, что мой алгоритм работает, я просто не могу правильно понять, как проходит обратный заказ, и я чувствую, что веб-сайт может помочь.

                     B
--------------------|------------------
|                   |                 |
A             ------D-----         ---I---
             |      |    |        |       |
             C      E    G        H       L
                         |
                         F

Мой результат: A C E F G D H L I B

Answer 1

Ваш ответ выглядит правильно для меня.

Этот прием работает для обобщенного дерева, а не только для двоичных.

см. http://en.wikipedia.org/wiki/Tree_traversal

С http://www.brpreiss.com/books/opus4/html/page259.html

обратный путь после заказа посещает корень последний. Чтобы сделать почтовый обход общего дерева:

Выполните обход по порядку каждого из поддеревьев корня один за другим в указанном порядке; а затем посетите корень.

Answer 2

Спасибо за график, который вы написали в этой статье, но меня это смутило, потому что это не типичное двоичное дерево. (Некоторые из узлов имеют 3 детей.)

Во всяком случае, кажется, хорошо.

Как определение пост-заказа в вики ( http://en.wikipedia.org/wiki/Tree_traversal), это правильно.

После заказа

1. Пройдите по левому поддереву.

2. Перейдите по правому поддереву.

3. Посетите корень.

Answer 3

Печать по заказу может быть выполнена с использованием рекурсии. Вы можете визуализировать себя из функции рекурсии ниже. Узел печатается после того, как обе функции над функцией print() возвращены. Попробуйте вручную проанализировать свое дерево по приведенному ниже коду на бумаге, и вы увидите, что результат верен. Первоначально визуализация такой функции рекурсии была бы сложной, но вы должны быть в состоянии визуализироваться, чтобы быть хорошим программистом, в любом случае, попробуйте.

void postorder(node)
{
   if(node=NULL)
      return;
   postorder(node.left);
   postorder(node.right);
   print(node);
}