Как я могу перебрать двоичное дерево без использования указателей или ссылок?

Question

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

int i;
for (i = 0; i < 10; ++i)
 printf("%i ", i % 2);

Он напрямую выводит список 0 1 0 1 0 1 0 1 0 1 без фактического сохранения списка в памяти.

Как можно сделать подобноес бинарными деревьями?

Пожалуйста, покажите способ реализации tree_iterator, new_root_tree_iterator и traverse_tree_iterator для следующего кода, где upper_boundary_of_tree - это что-то аналогичное числу 10 в примере списка и которое я не знаю, как определить.

У людей были проблемы с тем, что я подразумеваю под upper_boundary_of_tree.Верхняя граница дерева не будет представлена ​​числом 10. Я не знаю, как представить некоторую верхнюю границу дерева.Это часть вопроса.Верхняя граница дерева аналогична тому, как число 10 используется в приведенном выше коде списка, так как она выполняет ту же функцию, отмечая, где прекратить итерации, но это совершенно определенно не то же самое.

Если вам нужно, у вас также может быть функция free_tree_iterator.

tree_iterator i = new_root_tree_iterator();
while (traverse_tree_iterator(&i, upper_boundary_of_tree))
 foobar(i);

Это беспокоило меня некоторое время.

Answer 1

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

Другими словами, первый пример - эмуляция итерации по массиву из 10 элементов, которые являются нулями и единицами, один за другим. Итак, на каждой итерации вы прогнозируете значение на основе его индекса.

Если вы хотите вычислить индекс дочерних узлов в двоичном дереве, вы можете использовать heap формула распределения: 2n + 1 и 2n + 2, будет вычислять индекс левого и правого узлов соответственно, где n - это индекс на основе 0. На основе рассчитанного индекса вы можете эмулировать значение узла.

Answer 2

Чтобы напечатать нотацию для древовидной структуры без построения дерева, аналогично тому, как вы печатаете последовательность вместо построения списка, вы сначала должны решить, как будет выглядеть ваша нотация.

Можете ли вызапишите пример?

Например, Lisp-подобное обозначение?

((1 2) (3 4)) ;;это дерево

Кроме того, учитывая верхнюю границу 10, что означает, что будет десять пронумерованных листовых узлов, какой из множества возможных двоичных деревьев вы должны напечатать?

Прямой список - это вырожденное двоичное дерево, поэтому ваш простой цикл for в основном удовлетворяет задаче домашней работы.