ВУЗ:
Составители:
9
если непосредственный предок находится на уровне h, то его непосредственный
потомок лежит на уровне h + 1 .
Корень дерева находится на нулевом уровне.
Максимальный уровень какой-либо из вершин дерева называется его
глубиной или высотой. То есть глубина дерева определяется числом вершин в
самом длинном из путей от корня дерева до
листьев.
Количество ветвей, по которым нужно пройти от корня дерева до некото-
рой вершины, называется длиной пути до этой вершины.
Упорядоченное дерево – это дерево, у которого ветви, исходящие из каж-
дой вершины, упорядочены.
Замечание. Сама природа представления данных в компьютере устанав-
ливает точный порядок для всякого дерева, поэтому будем рассматривать
только
упорядоченные деревья.
2. ДВОИЧНЫЕ ДЕРЕВЬЯ
Особенно важную роль играют упорядоченные деревья второй степени. Их
называют двоичными или бинарными деревьями.
Определим двоичное дерево как конечное множество элементов – узлов,
которое или пусто, или состоит из корня и двух непересекающихся двоичных де-
ревьев, называемых левым и правым поддеревьями данного корня.
Заметим, что двоичное дерево
не является частным случаем дерева, хотя
эти два понятия связаны между собой. Основные отличия между ними:
1) Дерево никогда не бывает пустым, т.е. имеет, по меньшей мере, один
узел, а двоичное дерево может быть пустым.
2) Двоичное дерево - упорядоченное дерево, т.е. делается различие между
левым и правым поддеревом, даже
в том случае, когда узел имеет лишь одного
потомка. В графическом изображении дерева (рисунок 4) “наклон” ветвей важен.
Страницы
- « первая
- ‹ предыдущая
- …
- 5
- 6
- 7
- 8
- 9
- …
- следующая ›
- последняя »
