Язык С++ и программирование на нем. Рейзлин В.И. - 153 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

155
При появлении числа 10 в качестве шестого элемента последова-
тельности к дереву не добавляется новой вершины, а значение F(10) из-
влекается из имеющейся вершины (рис. 9д).
Определим в программе построения последовательности кодов
следующую структуру:
struct node {
int num, code;
node* left, * right;
node (int n, int c, node *l, node *r){
num = n; code = c;
left = l; right = r;}
};
Объекты типа node являются структурами, в которых каждое из
полей left и right есть либо NULL, либо указатель на место в памяти,
отведенное с помощью new для объекта типа node. Дерево можно
представить в виде множества объектов типа node, связанных указате-
лями. Сами эти объекты будут вершинами дерева, а указатели на места
в памяти, отведенные для объектов типа node, – ребрами дерева. Если
при этом поле left (right) есть NULL, то это значит, что в дереве из
данной вершины не исходит ребро, направленное влево вниз (вправо
вниз). Изобразим на рис. 10 представление дерева, соответствующего
рис. 9д, в памяти ЭВМ:
8 F(8) 13 F(13)
NULL NULL 4 F(4) NULL NULL 14 F(14)
NULL NULL 10 F(10)
Рис. 10. Изображение дерева в памяти ЭВМ
Выполнение присваивания v = v->left ( v = v->right ) означает пе-
реход к вершине, расположенной непосредственно слева снизу (справа
снизу) от данной, если, конечно, соответствующее поле данной верши-
ны не есть NULL. Таким способом можно передвигаться от вершины к
вершине сверху вниз. Включение новой вершины в дерево представляет
собой изменение значений полей типа node* некоторых вершин данно-
го дерева.
Вместе с каждым деревом рассматривается переменная, значени-
ем которой является указатель на корень дерева. Если в дерево не вхо-

Страницы