ВУЗ:
Составители:
72
определяется структура дерева, отражающего логическую структуру данных, а
затем уже полученное дерево приводится к бинарному. При этом поступают
следующим образом. Для каждого порождающего узла уничтожаются все исхо-
дящие из него ребра, кроме самого левого. Все «оторвавшиеся» порожденные
узлы того же уровня связываются с левым порожденным узлом указателями «на
подобный». Рис. 5.21
иллюстрирует представление произвольной древовидной
структуры в виде двоичного дерева с помощью указателей на порожденные и
подобные элементы структуры.
В двоичном дереве направлениям может быть поставлен определенный
логический смысл. Например, часто принимают, что левое направление ведет к
узлу, в котором размещена запись с меньшим значением ключа, чем у записи в
порождающем узле
, а правое направление ведет к узлу с записью, имеющей
больший ключ. В качестве примера построим такое дерево, указывая лишь зна-
чения ключей записей. Пусть записи подаются на обработку в такой последова-
тельности: 21,7, 33, 38, 19, 100, 36, 63, 180, 51, 290, 260, 286. Первая запись по-
мещается в корень дерева, остальные пристраиваются в соответствии с приня-
той логикой направлений. В результате
получится дерево, изображенное на рис.
5.22.
Рис. 5.21. Представление произвольного дерева в виде двоичного дерева
Поиск в таком дереве записи с нужным значением ключа осуществля-
ется по правилу: если искомый ключ меньше ключа данного узла, то продви-
гаться следует влево от данного узла, в противном случае – вправо от
данного
узла.
9
6 7 11 125
1310
4
8
3
2
1
10
6 7 11 12
139 4
8
3
2
1
5
Указатели на порожденные
элементы
Указатели на подобные
элементы
Страницы
- « первая
- ‹ предыдущая
- …
- 70
- 71
- 72
- 73
- 74
- …
- следующая ›
- последняя »
