Двоичное дерево, представленное с использованием массива - PullRequest
Новая
       1

Двоичное дерево, представленное с использованием массива

9 голосов
/ 24 ноября 2011

Рассмотрим следующий массив, который, как утверждается, представлял двоичное дерево:

[1, 2, 5, 6, -1, 8, 11]

Учитывая, что индекс со значением -1 указывает на корневой элемент, у меня есть следующие вопросы:

а) Как это на самом деле представлено?

Должны ли мы следовать приведенным ниже формулам ( источник по этой ссылке ), чтобы выяснить дерево? Три простые формулы позволяют перейти от индекса родителя к индексу его потомков и наоборот: 

* if index(parent) = N, index(left child) = 2*N+1
* if index(parent) = N, index(right child) = 2*N+2
* if index(child) = N, index(parent) = (N-1)/2 (integer division with truncation)

Если мы используем приведенные выше формулы, то index (root) = 3, index (left child) = 7, чего не существует.

б) Важно ли знать, является ли оно полным двоичным деревом или нет?

Ответы [ 3 ]

14 голосов
/ 21 ноября 2013

N = 0 должен быть корневым узлом, поскольку по указанным правилам у него нет родителя. 0 нельзя создать ни из одного из выражений (2 * N + 1) или (2 * N + 2), при условии отсутствия отрицательного N.

Обратите внимание, индекс - это не значение, хранящееся в массиве, это место в массиве. Для [1, 2, 5, 6, -1, 8, 11] Индекс 0 = 1 Индекс 1 = 2 Индекс 2 = 5 и т. Д.

Если это полное дерево, то -1 - допустимое значение, а дерево - 

    1  
   /  \  
  2    5  
 / \  / \  
6 -1 8  11

-1 также может быть указателем «NULL», что указывает на отсутствие значения в этом узле.

Так что дерево будет выглядеть 

    1  
   / \  
  2   5  
 /   / \  
6   8  11
8 голосов
/ 24 ноября 2011

Учитывая массив, вы можете придумать множество способов, как этот массив может представлять двоичное дерево.Таким образом, нет никакого способа узнать, вам нужно обратиться к источнику этого массива (что бы это ни было).

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

И, да, вероятно, важно знать, должно ли это быть полное дерево или нет.

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

0 голосов
/ 24 ноября 2011

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

Вы не можете представить это в своем массиве: 

    A
   / \
  B   C
 /   / 
D   E

Но вы можете представить это 

    A
   / \
  B   C
 / \  
D   E

или это: 

    A
   / \
  B   C
     / \  
    D   E

(для последних 2k + 1 будет справа потомком и 2k + 2 слева потомком)

Вам нужно знать только количество узлов в трех.

...