Задача

Дано два дерева. Перше має дуже великий розмір (міліони елементів), інше – менший (сотні елементів). Треба написати функцію яка буде визначати чи є менше дерево піддеревом більшого.

Рішення 1

Для кожного елемента більшого дерева що містить значення еквівалентне значенню коріневого елемента меншого дерева перевіримо чи всі інші елементи також ідентичні.

 

// визначити чи дерева ідентичні bool match_tree(tree * r1, tree *r2) { if (r1 == NULL && r2 == NULL) return true; if (r1 == NULL || r2 == NULL) return false; if (r1->val != r2->val) return false; return match_tree(r1->left, r2->left) && match_tree(r1->right, r2->right); } // визначити чи другий параметр є піддеревом першого bool is_sub_tree(tree *r1, tree *r2) { if (!r2) return true; if (!r1) return false; if (r1->val == r2->val) return match_tree(r1, r2); return is_sub_tree(r1->left, r2) || is_sub_tree(r1->right, r2); }

Рішення 2

Можна для обох дерев побудувати рядок із значень їх елементів у порядку обхода inplace (лівий під-елемент->батьківський елемент->правий під-елемент). Після цього перевірити чи рядок для другого дерева є підрядком для першого дерева.

Задача

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

Дерево не є бінарним деревом пошуку.

Рішення

Для поточного елемента дерева (починаємо з корня) перевіряємо чи елементи обоє знаходяться у лівому/правому піддереві і якщо так то рекурсивно продовжуємо пошук у відповідному піддереві. Інакше поточний елемент є предком.

bool covers(tree *root, tree *p) { if (!root) return false; if (root == p) return true; return covers(root->left, p) || covers(root->right, p); } tree* common_ancestor(tree *root, tree *p, tree *q) { if (covers(root->left, p) && covers(root->left, q)) return common_ancestor(root->left, p, q); if (covers(root->right, p) && covers(root->right, q)) return common_ancestor(root->right, p, q); return root; }

Задача

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

Рішення

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

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

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

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; }

Задача

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

Рішення

Знаходимо найкоротшу і найдовшу гілки і порівнюємо їх.

size_t min_depth(tree_node *t) 
{
 if (t == NULL) return 0; 
 return min(min_depth(t->left), min_depth(t->right)) +1; 
} 

size_t max_depth(tree_node *t) 
{ 
if (t == NULL) return 0; 
return max(max_depth(t->left), maxn_depth(t->right)) +1; 
} 

bool is_tree_balanced(tree_node *t) 
{ 
return max_depth(t) - min_depth(t) <= 1; 
}