24.09.2008Деревья1 Структуры и алгоритмы обработки данных, 1 Лекция 5 ДЕРЕВЬЯ 1.Определения дерева, леса, бинарного дерева. Скобочное представление 2.Спецификация. - презентация

1 Деревья1 Структуры и алгоритмы обработки данных, 1 Лекция 5 ДЕРЕВЬЯ 1.Определения дерева, леса, бинарного дерева. Скобочное представление 2.Спецификация дерева, леса, бинарного дерева 3.Естественное соответствие бинарного дерева и леса 4.Обходы бинарных деревьев и леса

2 Деревья2 В курсе «Дискретная математика»: Дерево – связный граф, не содержащий циклов. 1. Определения дерева, леса, бинарного дерева. Скобочное представление

3 Деревья3 a dbc hjfg k ei Дерево – конечное множество Т, состоящее из одного или более узлов, таких, что а) имеется один специально обозначенный узел, называемый корнем данного дерева; б) остальные узлы (исключая корень) содержатся в m 0 попарно не пересекающихся множествах Т 1, Т 2,..., Т m, каждое из которых, в свою очередь, является деревом. Деревья Т 1, Т 2,..., Т m называются поддеревьями данного дерева. Определение (рекурсивное)

4 Деревья4 Дерево T = (корень, T 1, T 2, …, T m ) Терминология: узел, лист, отец, сын, брат, предок, потомок Уровень узла (рекурсивно): 1)корень имеет уровень 1; 2)другие узлы имеют уровень, на единицу больший их уровня в содержащем их поддереве этого корня. где T i – поддерево корня дерева T, такое, что a T i. a dbc hjfg k ei

5 Деревья5 Если в определении дерева существен порядок перечисления поддеревьев Т 1, Т 2,..., Т m, то дерево называют упорядоченным и говорят о «первом» (Т 1 ), «втором» (Т 2 ) и т. д. поддеревьях данного корня (старший брат и т.п.). В терминологии теории графов это «конечное ориентированное (корневое) упорядоченное дерево». Лес – это множество (обычно упорядоченное), состоящее из некоторого (быть может, равного нулю) числа непересекающихся деревьев. Тогда пункт б) определения дерева: б) узлы дерева, за исключением корня, образуют лес. Дерево T = (корень, лес поддеревьев)

6 Деревья6 Представление дерева: a а b i b i j j c ch h d de e f fk k g g а б а – в виде уступчатого списка; б – в виде «упрощенного» уступчатого списка

7 Деревья7 Скобочное представление дерева и леса: ::= пусто |, ::= ( ). ( 0 a ( 1 b ( 2 i 2 ) ( 2 j 2 ) 1 ) ( 1 c ( 2 h 2 ) 1 ) ( 1 d ( 2 e 2 ) ( 2 f ( 3 k 3 ) 2 ) ( 2 g 2 ) 1 ) 0 ) a dbc hjfg k ei

8 Деревья8 Бинарные деревья Бинарное дерево конечное множество узлов, которое либо пусто, либо состоит из корня и двух непересекающихся бинарных деревьев, называемых правым поддеревом и левым поддеревом. a b a b (a (b ) ) ( a (b )) Скобочное представление бинарного дерева (БД): ::= |, ::=, ::= ( ).

9 Деревья9 (a (b (d Λ (h Λ Λ)) (e Λ Λ)) (c (f (i Λ Λ) (j Λ Λ)) (g Λ (k (l Λ Λ) Λ)))) Правила упрощения скобочной записи БД : 1. ( ) ( ), 2. ( ) ( ) (a (b (d (h)) (e)) (c (f (i) (j)) (g (k (l))))) a cb fd h e j g ik l

10 Деревья10 2. Спецификация дерева, леса, бинарного дерева Tree of α = Tree (α) Tree (α) ::= ( Корень(α), Forest (α) ) Forest (α) ::= L_list (Tree (α)) Базовые операцииАксиомы 1) Root: Tree α; 2) Listing: Tree Forest; 3) ConsTree: α Forest Tree А 1 ) Root (ConsTree (u, f)) = u; А 2 ) Listing (ConsTree (u, f)) = f; А 3 ) ConsTree (Root (t), Listing (t)) = t, ( u: α; f: Forest (α); t: Tree (α))

11 Деревья11 Функциональная спецификация структуры данных бинарного дерева BinaryTree (α) BT (α) Базовые функцииАксиомы 1) Root: NonNullBT α; 2) Left: NonNullBT BT; 3) Right: NonNullBT BT; 4) ConsBT: α BT BT NonNullBT; 5) Null: BT Boolean; 6) : BT A 1 ) Null ( ) = true; A 1 ') Null (b) = false; A 2 ) Null (ConsBT (u, b1, b2)) = false; A 3 ) Root (ConsBT (u, b1, b2)) = u; A 4 ) Left (ConsBT (u, b1, b2)) = b1; A 5 ) Right (ConsBT (u, b1, b2)) = b2; A 6 ) ConsBT (Root (b), Left (b), Right (b)) = b ( u: α, b: NonNullBT (α), b1, b2: BT (α))

12 Деревья12 Естественное соответствие бинарного дерева и леса Представление леса бинарным деревом: Пусть лес F типа Forest задан как список деревьев T i типа Tree (для i 1..m): F = (Т 1 Т 2... Т m ). Head (F) = Т 1 Tail (F) = (Т 2... Т m ). Head (F) = (Root (Head (F)), Listing (Head (F)) Лес F = совокупность трех частей: 1) корня первого дерева Root (Head (F)), 2) леса поддеревьев первого дерева Listing (Head (F)), 3) леса остальных деревьев Tail (F).

13 Деревья13 … Т1Т1 Т2Т2 Т3Т3 ТmТm лес F = (Т 1 Т 2... Т m ). БД(F)

14 Деревья14 = B(F) B(T 1 \r 1 ) r1r1 B(T 2 \r 2 ) B(T 3 \r 3 ) B(T m \r m ) r2r2 r3r3 rmrm r i = Root(T i )

15 Деревья15 Бинарное дерево B (F), представляющее лес F: B (F) if Null (F) then else ConsBT (Root (Head (F)), B (Listing (Head (F))), B (Tail (F))).

16 Деревья16 «Геометрическая» интерпретация a b e c d k i f g j a b e c d k i fg j a be c d ki f g j

17 Деревья17 Преобразование БД лес F (B) if Null (B) then Nil else Cons (ConsTree (Root (B), F (Left (B))), F (Right (B))). Самостоятельно дать «геометрическую» интерпретацию и графическое изображение преобразования БД лес в общем случае

18 Деревья18 procedure обходКЛП (b: BTree); {прямой} begin if not Null (b) then begin посетить (Root (b)); обходКЛП (Left (b)); обходКЛП (Right (b)); end end {обходКЛП}; 4. Обходы бинарных деревьев и леса Обходы БД

19 Деревья19 procedure обходЛКП (b: BTree);procedure обходЛПК (b: BTree); {обратный}{концевой} begin if not Null (b) then begin обходЛКП (Left (b)); обходЛПК (Left (b)); посетить (Root (b)); обходЛПК (Right (b)); обходЛКП (Right (b)); посетить ( Root (b)); end end{обходЛКП};end{обходЛПК}

20 Деревья20 Варианты терминологии 1) КЛП, ЛКП, ЛПК [14]; 2) прямой, обратный, концевой [10]; 3) прямой, симметричный, обратный [13]; 4) сверху вниз, слева направо, снизу вверх [5], [6]; 5) префиксный (PreOrder), инфиксный (InOrder), постфиксный (PostOrder) [5], [6].

21 Деревья21 Обход бинарного дерева, представляющего арифметическое выражение с бинарными операциями Арифметическое выражение (a + b) * c d / (e + f * g) – */ +c ba d+ *e fg 1) КЛП префиксная запись: * + a b c / d + e * f g ; 2) ЛКП инфиксная запись (без скобок): a + b * c d / e + f * g ; 3) ЛПК постфиксная запись: a b + c * d e f g * + /.

22 Деревья22 Обходы леса Прямой порядок: а) посетить корень первого дерева; б) пройти поддеревья первого дерева (в прямом порядке); в) пройти оставшиеся деревья леса (в прямом порядке). procedure PreOrder (F: Forest); {прямой} begin if not Null (F) then begin посетить (Root (Head (F)); PreOrder (Listing (Head (F))); PreOrder (Tail (F)); end end{PreOrder}

23 Деревья23 … Т1Т1 Т2Т2 Т3Т3 ТmТm лес F = (Т 1 Т 2... Т m ). БД(F) Соответствие обходов леса и бинарного дерева

24 Деревья24 Обратный порядок: а) пройти поддеревья первого дерева (в обратном порядке) Listing (Head (F)) ; б) посетить корень первого дерева Root (Head (F)) ; в) пройти оставшиеся деревья (в обратном порядке) Tail (F). Концевой порядок: а) пройти поддеревья первого дерева (в концевом порядке) Listing (Head (F)) ; б) пройти оставшиеся деревья (в концевом порядке) Tail (F) ; в) посетить корень первого дерева Root (Head (F)).

25 Деревья25 Примеры a b c d e f g h i j k l m n a d b e g c j c f j c h i k i l m n Лес: БД:

26 Деревья26 КЛП a b c d e f g h i j k l m n a d b e g c j f c h i k l m n (a (d) (e (j) (k)) (f (l))) (b (g) (h)) (c (i (m) (n))) КЛП: a d e j k f l b g h c i m n (a (d (e (j (k)) (f (l)) (b (g (h)) (c (i (m (n))))))

27 Деревья27 Замечания 1.Обход в глубину 2.Порядок престолонаследования (см. также - Агата Кристи)

28 Деревья28 ЛКП a b c d e f g h i j k l m n a d b e g c j f c h i k l m n (a (d) (e (j) (k)) (f (l))) (b (g) (h)) (c (i (m) (n))) ЛКП: d j k e l f a g h b m n i c (a (d (e (j (k)) (f (l)) (b (g (h)) (c (i (m (n))))))

29 Деревья29 Замечания 1.Обход БД слева направо 2.Обход в лесу – снизу вверх

30 Деревья30 ЛПК a b c d e f g h i j k l m n a d b e g c j f c h i k l m n (a (d) (e (j) (k)) (f (l))) (b (g) (h)) (c (i (m) (n))) ЛПК: k j l f e d h g n m i c b a (a (d (e (j (k)) (f (l)) (b (g (h)) (c (i (m (n))))))

31 Деревья31 КОНЕЦ ЛЕКЦИИ