рекурсивная печать двоичных элементов дерева

Я вернулся в K&R, чтобы прочитать одну главу, и заметил пример, который я ранее опустил. В этой главе рассматривается тип данных бинарного дерева. Я понимаю хранение новых записей в узлах, но функция печати дает путает меня. Почему печать левой части называется первой?

Будет ли это работать, если printf будет первой командой в функции, за которой следуют левая и правая?

Если нет-то почему?

/* treeprint: in-order print of tree p */
void treeprint(struct tnode *p)
{
    if (p != NULL) {
        treeprint(p->left);
        printf("%4d %sn", p->count, p->word);
        treeprint(p->right);
    }
}
3 4
binary-tree kernighan-and-ritchie

3 ответа:

Сначала нисходящая левая сторона, затем печать самого узла, затем нисходящая правая сторона-вот что делает эту операциюв порядке обхода дерева . Если вы переместите printf перед левым спуском, как вы предполагаете, это сделает его предзаказом. И если бы вы сделали оба спуска первыми, это было бы post-order. Все три возможности посещают все узлы, но в трех различных порядках.

Рассмотрим простое дерево

  *
 / \
a   +
   / \
  b   c

Если вы проходите это дерево в предварительном порядке, вы получаете

* a + b c

По порядку, 

a * b + c

Post-order, 

a b c + *
Какая из этих возможностей вам нужна, зависит от того, что вы делаете.
9

Конечно, это будет "работать". Вы просто получите другой порядок на выходе. Вы также можете распечатать узел после печати обоих дочерних узлов. (И представьте, что у вас есть дерево с несколькими детьми, а не только с двумя.)

Реальный вопрос заключается в том, подчиняются лизначения узлов дерева каким-либо специальным правилам и, следовательно, является ли какой-либо конкретный порядок обхода особенно значимым. Например, для бинарного дерева поиска лево-само-правый порядок выводит значения в порядке сортировки.
1

Вы можете пройти через бинарное дерево различными способами: предзаказ, в порядке и после заказа.

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

Таким образом, printf можно рассматривать как держатель места для других видов процедур/функций для работы с различными видами проблемы.

0