Матрица смежности двоичного дерева глубиной 4 в С

Question

Как будет выглядеть матрица смежности двоичного дерева глубины 4 в C? Глубина узла определяется как его расстояние от корня.

Я знаю, что а на глубине ноль е на глубине 2

             a
          /     \ 
         b       c
       / \      /  \ 
      d  e      f   g
    / \ / \    / \ / \ 
   h  i j k   l  m n  o



  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
  a b c d e f g h i j k l m n o
a   1 1 0 0 0 0 0 0 0 0 0 0 0 0
b 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0
c 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0
d 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0
e 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0
f 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0
g 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1
h 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
i 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 
j 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
k 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
l 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
m 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
n 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
o 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0

Answer 1

Просто наблюдение. В целом верно.

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

a = 1; b = 2; c = 3 ....

Для любого узла x -> i Это дети будут 2*i и 2*i + 1 И его родитель будет floor(i/2)

В вашем случае вы можете просто жестко закодировать его, так как у вас есть только глубина = 4