3.05.2. Корневое дерево

Корневое дерево Есть специальный способ представления (изображения) дерева. Выбирается некоторая вершина, которая именуется «корнем дерева». При изображении все вершины располагают по ярусам, следующим образом. На нулевом ярусе располагается корень дерева (см. рис.). на 1 ярусе располагают все вершины дерева, смежные с корнем; затем на 2 ярусе — все вершины, смежные с вершинами 1-го яруса; на 3-ем — вершины, смежные с с вершинами 2-го яруса и так далее.

Каждому корневому дереву ставится в соответствие его бинарный Код, который строится в процессе полного обхода дерева. Обход начинается с корня и заканчивается корнем. Обход осуществляется слева направо, т. е. сначала проходится левая ветвь, затем следующая и так далее, в конце — самая правая. При обходе необходимо подниматься по ветви (см. следующий рис.) до тех пор, пока это возможно. Затем по ветви опускаются до тех пор, пока не появится возможность продолжить подъем по еще не пройденной ветви. При подъеме с одного яруса на следующий в код дерева записывается 1, при опускании с яруса на ярус — 0. Так дерево на рисунке имеет код (11101101000011011011000100).

Легко видеть, что код дерева обладает следующими свойствами:

· длина кода дерева порядка Равна ;

· число нулей равно числу единиц;

· если обрубить код на каком-либо месте, то число единиц на участке от начала кода до данного места не меньше числа нулей на этом участке (разность между этим количеством совпадает с ярусом, на котором прерван обход).

Обратно, по всякому бинарному набору, обладающему этими свойствами, можно построить корневое дерево, код которого совпадает с данным набором.

< Предыдущая		Следующая >