Итак, вы должны реализовать процедуру getIndex(int index)
, которая должна вернуть вам узел с этим индексом?
Если это так, вы ищете эффективный способ представления двоичного дерева. Вы можете перемещаться по дереву для каждого вызова getIndex
, но это не будет эффективным ...
Эффективным решения для хранения полного бинарного дерева в массиве из-за O (1) доступа к нему обеспечивает. Храните узел n в индексе n в массиве и его дочерние узлы с индексом 2*n
и (2*n) - 1
. Но здесь ограничения заключаются в том, что дерево должно быть полным, а размер массива не является переменным (если бинарное дерево становится слишком большим, должен быть сделан больший массив (обычно в два раза больше), и все элементы должны быть скопированы).
Это удобное решение, так как:
- узел доступа в O (1), но процедура, как
addNode()
стала бы амортизируется в O (1). (*)(*)
- Узел не должен помнить, что это дочерние узлы ->
this.left
становится this.left()
с реализацией left()
, представленной ниже.
A возможная реализация для left()
процедура.
static int[] binaryTreeArray = new int[maxTreeSize]; // BT of integers for example
...
public int left() { // returns integer or ... (type of your nodes)
return binaryTreeArray[(this.Index)*2]; // O(1)
}
(*)addNode()
-как процедура добавления узлов в O (1) (binaryTreeArray[index] = nodeValue;
) большую часть времени, но когда binaryTreeArray
полон он должен будет сделать больший массив, который, как правило, в два раза как большой (O (n) для копирования). Можно показать, что это имеет амортизированную стоимость O (1), но для этого ответа это не добавило значения.
Вы можете пройтись по дереву еще раз после того, как полностью его создали, или пытаетесь инициализировать этот индекс во время первого прохода при создании дерева? – NoseKnowsAll
Просто перемещайте свое дерево по слою. – talex
@NoseKnowsAll Мне нужно, чтобы это было сделано после того, как дерево полностью создано. – RK2015