Знайти найменшу глибину листкового вузла в bst - двійково-пошуковому дереві, глибині

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

Відповіді:

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

Дивіться, наприклад, псевдо-код у моя відповідь на "Ширина першого поглиблення по-перше" просто додайте ще одну умову до циклу while.

BTW - Це ви отримаєте a лист з мінімальною глибиною, оскільки на цій глибині їх може бути більше. Отримати повний набір листя мінімальної глибини трохи складніше. Я здогадуюсь піти з ітеративна стратегія поглиблення.

Дізнайтеся, на якому рівні цей вузол.

Три варіанти:

Спершу знайдіть вузол та пошукайте дерево. Це звучить марно, але цей другий пошук вимагає відвідування лише стільки вузлів, скільки рівень, і це дійсно швидко.

По черзі ви можете відстежувати, як ви йдете. Ви використовуєте три лічильники levelCounter, thisLevelCounter і nextLevelCounter. Кожен раз, коли ви більше переходите на новий вузол, ви декрементуєте thisLevelCounter, і коли вона дорівнює нулю, ви перейшли на рівень так само

levelCounter++
thisLevelCounter = nextLevelCounter
nextLevelCounter = 0

Кожен раз, коли ви додаєте дочірній вузол до списку пошуку, збільшуйте його nextLevelCounter. Кожен раз, коли ви зберігаєте нове збільшення дочірнього вузла nextLevelCounter

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

Ось версія коду (сподіваюсь, я не пропустив перевірку помилок):

void min_leaf(node_t *t, int *min, int lev, node_t **n) {
if (!t) {
return;
}

if (lev > *min) {
printf("Back from %d at lev %d, min: %d already foundn",
t->key,
lev,
*min);
return;
}

if (!t->left && !t->right) {
if (*min > lev) {
*min = lev;
*n = t;
}
} else {
min_leaf(t->left, min, lev+1, n);
min_leaf(t->right, min, lev+1, n);
}
}

void bst_print_min_leaf(bst_t* bst) {
int min = 10000; /* Replace it with some really large number */
node_t *minn = NULL;

min_leaf(bst->root, &min, 0, &minn); /*level: root is level 0 */
if (minn) printf("min leaf is at depth: %d: (%p:%d)n", min, minn, minn->key);
}