називаються піддеревами даного дерева. p> Це визначення є рекурсивним. Якщо коротко, то дерево це безліч, що складається з кореня і приєднаних до нього піддерев, які теж є деревами. Дерево визначається через саме себе. Однак дане визначення осмислено, так як рекурсія кінцева. Кожне піддерево містить менше вузлів, ніж її утримує дерево. Зрештою, ми приходимо до піддерев, що містить всього один вузол, а це вже зрозуміло, що таке. br/>В
Рис. 3. Дерево. br/>
На рис. 3 показано дерево з сімома вузлами. Хоча звичайні дерева ростуть знизу вгору, малювати їх прийнято навпаки. При малюванні схеми від руки такий спосіб, очевидно, зручніше. Через цієї неузгодженості іноді виникає плутанина, коли говорять про те, що один з вузлів знаходиться над або під іншим. З цієї причини зручніше користуватися термінологією, що вживається при описі генеалогічних дерев, називаючи ближчі до кореня вузли предками, а більш далекі нащадками. p> Вузли, що не містять піддерев, називаються кінцевими вузлами або листям. Безліч не перетинаються дерев називається лісом. Наприклад, ліс утворюють піддерева, що виходять з одного вузла. p> Графічно дерево можна зобразити і деякими іншими способами. Деякі з них представлені на рис. 4. Згідно з визначенням дерево являє собою систему вкладених множин, де ці безлічі або не перетинаються або повністю утримуються одне в іншому. Такі безлічі можна зобразити як області на площині (рис. 4а). На рис. 4б вкладені безлічі розташовуються не так на площині, а витягнуті в одну лінію. Рис. 4б також можна розглядати як схему деякої алгебраїчної формули, яка містить вкладені дужки. Рис. 4в дає ще один популярний спосіб зображення деревовидної структури у вигляді уступчатого списку. br/>В
Рис. 4. Інші способи зображення деревовидних структур: (а) вкладені безлічі; (б) вкладені дужки; (в) уступчастий список. br/>
уступчастих список має очевидну подібність зі способом форматування програмного коду. Дійсно, програма, написана в рамках парадигми структурного програмування, може бути представлена ​​як дерево, що складається з вкладених один в одного конструкцій. p> Також можна провести аналогію між уступчатим списком і зовнішнім виглядом змістів в книгах, де розділи містять підрозділи, ті в свою чергу поподраздели і т.д. Традиційний спосіб нумерації таких розділів (розділ 1, підрозділи 1.1 і 1.2, подподраздел 1.1.2 і т.п.) називається десятковою системою Дьюї. У застосуванні до дерева на рис. 3 і 4 ця система дасть:
. A; 1.1 B; 1.2 C; 1.2.1 D; 1.2.2 E; 1.2.3 F; 1.2.3.1 G;
.2 Проходження дерев
рекурсивний алгоритм програмування арифметичний
У всіх алгоритмах, пов'язаних з деревовидними структурами незмінно зустрічається одна і та ж ідея, а саме ідея проходження або обходу дерева. Це - такий спосіб відвідування вузлів дерева, при якому кожен вузол проходиться точно один раз. При цьому виходить лінійна розстановка вузлів дерева. З...
