Составители:
60
Списочное представление двоичных деревьев основано на элементах,
соответствующих узлам дерева. Каждый элемент имеет поле данных и два
поля указателей. Один указатель используется для связывания элемента с
правым потомком, а другой – с левым. Листья имеют пустые указатели
потомков. При таком способе представления дерева обязательно следует
сохранять указатель на узел, являющийся корнем дерева:
type
PTree = ^TTree;
TTree = record
Data: TypeElement; {поле данных}
Left, Right: PTree; {указатели на левого и правого потомков}
end;
В виде массива проще всего представляется полное двоичное дере-
во, так как оно всегда имеет строго определенное число вершин на
каждом уровне. Вершины можно пронумеровать слева направо после-
довательно по уровням и использовать эти номера в качестве индексов
в одномерном массиве. Если число уровней дерева в процессе обработ-
ки не будет существенно изменяться, то такой способ представления
полного двоичного дерева будет значительно более экономичным, чем
любая списковая структура:
type
Tree: array[1..N] of TypeElement;
Адрес любой вершины в массиве вычисляется как
адрес = 2
k–1
+i–1,
где k – номер уровня вершины; i – номер на уровне k в полном двоич-
ном дереве. Адрес корня будет равен единице. Для любой вершины,
имеющей индекс j в массиве, можно вычислить адреса левого и право-
го потомков:
адрес_левого = 2*j
адрес_правого = 2*j+1
Главным недостатком статического способа представления двоично-
го дерева является то, что массив имеет фиксированную длину. Размер
массива выбирается исходя из максимально возможного количества уров-
ней двоичного дерева, и чем менее полным является дерево, тем менее
рационально используется память. Кроме того, недостатком являются
Страницы
- « первая
- ‹ предыдущая
- …
- 58
- 59
- 60
- 61
- 62
- …
- следующая ›
- последняя »
