Повернути наступний елемент у дереві

Задача

Написати функцію яка приймає вузол дерева і повертає наступний по порядку елемент. Кожен вузол має посилання на батьківський елемент.

Рішення

Обхід дерева з трьох елементів здійснюється по порядку правий-батьківський-лівий. Самим першим елементом відповідно має бути самий лівий під-елемент.

Якщо поточний елемент має правий дочірний елемент то повернемо самий лівий елемент правого під-елементу.

Інакше якщо поточний елемент є лівим під-елементом батьківського елементу то повертаємо батьківський елемент, а інакше робимо батьківський елемент поточним і продовжуємо йти вгору.

void next_tree_node(tree_item *t) { tree_item *result = NULL; if (t) { if (t->right) { for (t = t->right; t->left; t = t->left); result = t; } else { for (tree_item *parent = t->parent; parent; t = parent, parent = parent->parent) { if (parent->left = t) { result = parent; break; } } } } return result; }

Залишити відповідь

Зайти з допомогою: