#arrays #data-structures #binary-tree
#массивы #структуры данных #двоичное дерево
Вопрос:
Итак, я исследовал двоичные деревья, и мне было интересно, какую стандартную систему вы бы использовали для преобразования двоичного дерева для хранения в массив? Таким образом, это была бы система, которая гарантировала бы, что никакие 2 узла дерева не сопоставляются с одним и тем же индексом массива.
Комментарии:
1.geeksforgeeks.org/binary-tree-array-implementation/….
2. @AkshayBande Спасибо, но я не уверен относительно того, как я обосновываю, почему это правильно, так почему это гарантирует, что никакие два узла дерева не сопоставляются с одним и тем же индексом массива.
Ответ №1:
В двоичном дереве у каждого узла будет два дочерних узла, мы можем использовать это свойство для представления его с помощью массива.
В представлении массива будут некоторые пустые индексы, если дерево не является полным двоичным деревом.
Если массив основан на индексе 1, то каждый узел имеет своего левого дочернего элемента в позиции 2i и правого дочернего элемента в позиции 2i 1.
Для индексирования на основе 0 левый дочерний элемент расположен в 2i 1, а правый дочерний элемент — в 2i 2.
Поскольку левый и правый индексы вычисляются таким образом, они не будут перекрываться.