Учитывая отсортированный массив, напишите программу, чтобы найти двоичное дерево поиска с минимальной глубиной, что это за глубина?Глубина дерева двоичного поиска
Я знаю, как преобразовать массив в сбалансированный BST, но как сделать функцию для создания BST с минимальной глубиной?
1) Сборка полного двоичного дерева с высотой h (h - минимальное число, такое как 2^h - 1> = количество элементов в вашем массиве). В этот момент вы можете просто игнорировать входной массив. Очевидно, что это дерево имеет минимальную глубину (любое дерево с меньшей глубиной просто не может иметь достаточно узлов для хранения всех элементов массива).
2) Теперь вы можете заполнить это дерево элементами массива с помощью простого рекурсивного подхода:
i) Заполните левое вспомогательное дерево.
ii) Поместите наименьшее неиспользованное число в текущий узел.
iii) Заполните правое поддерево.
Не забудьте удалить 2^h - 1 - n листья перед началом обхода (где n - размер входного массива) (этот шаг необходим, потому что размер полного дерева составляет 2^h - 1, но в массиве всего n элементов).
O(n) Реализация этого алгоритма довольно напряженная (вы можете явно построить дерево, удалить дополнительные листья и затем пересечь его, потому что число узлов в дереве равно O(n)).
извините за поздний ответ, спасибо вам очень. Можно ли показать, как будет выглядеть функция C для вышеупомянутой реализации? Я новичок в c, и мне не удается его реализовать. – overflow
Вам нужно всего лишь найти глубину, или вам нужно найти дерево? –
@ AD.Net Нет. Это что-то вроде log (array.length) (возможно, +1). – kraskevich
@ пользователь2040251, конечно, спасибо. Я пытался только с 6-7 номерами, пропустил половину каждого подмассива –