вопрос о дереве

Question

У меня есть вопрос, например, я хочу реализовать двоичное дерево с массивом, я хочу понять, что будут индексы для левого и правого дочерних элементов? Мой массив основан на 0, я хочу реализовать поиск в дереве с помощью массива, кто-нибудь может мне помочь?

Answer 1

Чтобы реализовать двоичное дерево в виде массива, вы должны поместить левый дочерний элемент для узла i в 2*i+1 и правый дочерний элемент в 2*i+2.

Так, например, имея 6 узлов, вот индексы соответствующего массива

          0
          |
      ---------
      |       |
   ---1--   --2--
   |     |  |    |
   3     4  5    6

Answer 2

левый ребенок = родитель * 2 + 1

правый ребенок = родитель * 2 + 2

Я предполагаю, что это домашнее задание, поэтому я дам вам понять алгоритм поиска.

Answer 3

Я думаю, что вы ищете кучу . Или, по крайней мере, вы используете дерево, когда структура массива недостаточна для ваших нужд, поэтому вы можете попытаться реализовать дерево внутри массива, но это не имеет особого смысла, поскольку каждый узел содержит ссылки на свои дочерние элементы без каких-либо индексов .

Но куча - это массив, который также можно рассматривать как двоичное дерево, посмотрите здесь . Это дерево в том смысле, что оно организует данные в виде дерева, но, не имея прямых ссылок на дочерние элементы, они могут быть выведены из позиции.