Нахождение местоположения родительского узла в двоичном дереве
Поэтому мне нужна помощь, чтобы придумать выражение, которое всегда даст мне местоположение родительского узла ребенка в двоичном дереве. Вот пример задачи, которую мой учитель поставит на нашем экзамене:
«Рассмотрим полное двоичное дерево с ровно 10000 узлов, реализованное с массивом, начинающимся с индекса 0. Массив заполняется по порядку путем извлечения элементов из дерева по одному уровню за раз слева направо. Предположим, что у узла хранится его значение в местоположении 4999. Где значение хранится для родителя этого узла? «
Мой учитель не сказал нам, как решить такую проблему. Она просто сказала: «Нарисуй бинарное дерево и найди узор». Я так и сделал, но ничего не смог придумать! пожалуйста помоги. Благодарю.
Решение
Следующее полностью использует целочисленное деление. То есть дробные остатки отбрасываются. Для любого заданного индекса узла N, дети этого узла всегда будут в местах 2N+1 а также 2(N+1) в том же массиве.
Следовательно, Родитель любого узла N > 0 в таком массиве всегда будет по индексу (N-1)/2,
Примеры для родителей:
Parent 0: children 1,2
Parent 1: children 3,4
Parent 2: children 5,6
Parent 3: children 7,8
etc...
Примеры от ребенка к родителю:
Child 8 : Parent = (8-1)/2 = 7/2 = 3
Child 7 : Parent = (7-1)/2 = 6/2 = 3
Child 6 : Parent = (6-1)/2 = 5/2 = 2
Child 5 : Parent = (5-1)/2 = 4/2 = 2
Итак, для вашей проблемы:
(4999-1)/2 = 4998/2 = 2499
Примечание: помните об этом, так как вы будете использовать его широко когда вы начинаете кодировать алгоритмы сортировки кучи на основе массива.
Другие решения
Спасибо за вашу помощь, ребята. И я нашел ответ на свой вопрос!
Общий алгоритм поиска местоположения родительского узла:
[i + (root — 1)] / 2 где i — местоположение данного узла, а root — местоположение корня. Таким образом, в данной задаче выше корень начинается с позиции 0. Таким образом, уравнение для поиска родительского узла любого узла имеет вид [i + (0 — 1)] / 2 = (i — 1) / 2.Теперь допустим, что корень начался в позиции 3, тогда уравнение будет [i + (3 — 1)] / 2
= (я + 2) / 2 !!!! Это алгоритм, который мне был нужен. Большинство из вас помогли мне решить одну проблему, которую я предоставил, но мне действительно нужно общее решение для бинарного дерева, корень которого может начинаться с любых позиций; не только в нуле
Кажется, именно так элементы массива отображаются обратно в дерево на основе индексов массива.
0
1 2
3 4 5 6
Если так, то родительский индекс n я сидела floor( (n - 1) / 2 ) (за n != 0)
Если вы запишете log2 запрошенного числа (4999) и примете целую часть, это даст вам кратчайшую степень числа 2 от числа (12). Это 2 ^ 12 = 4096.
Родителем узлов между 4096 и 2 ^ 13 — 1 являются узлы между 2 ^ 11 и 2 ^ 12 — 1. И для каждой пары узлов в первом диапазоне у вас есть родительский узел во втором. Таким образом, вы можете отобразить их, взяв целую часть от половины разницы (4999 — 4096) и добавив ее в начало родительского диапазона (2048).
Таким образом, у вас будет этаж 903/2, и вы добавите его к 2048, получив 2499.
Обратите внимание, что я не сделал точный расчет, примите стратегию ответа, а не результаты.
Вы можете поместить этот алгоритм в математическое выражение, немного поработав.
Надеюсь, поможет!