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

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

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

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