Представлення дерев

Для дерев, так само як і для графів, найзрозумілішим і найпростішим для людини є графічний спосіб подання дерева, хоча ці способи не придатні для опрацювання дерев на комп’ютері.

Зазвичай кореневі дерева на рисунку зображають у вигляді сукупності точок, з’єднаних між собою лініями, причому корінь є найвищою вершиною на рисунку (рис.2.1), його сини знаходяться нижче від нього, онуки – ще нижче, і т.д.

Рис 2.1. Відображення частини династії київських князів у вигляді лісу дерев

При графічному відображенні бінарних берев (m -арних рідко) також часто грає роль положення вузла, для того щоби відрізняти лівого та правого сина. Наприклад, дерева зображені на рис 2.2. є різними, оскільки у першому випадку маємо справу з деревом, корінь якого яке має порожнього праве піддерево, а у другому – праве порожнє піддерево.

.

Рис 2.2. Відображення двох різних бінарних дерев, для яких порядок синів має значення

Деревовидну структуру можна представляти іншими способами (рис.2.3).

a) б)

Рис 2.3. Графічні способи подання дерева а) вкладеними множинами б) з використанням відступу

Дерево можна відображати у вигляді, подібному до алгебраїчної формули, за допомогою дужок. Цей метод чимось подібний до методу відображення за допомогою вкладених множин, якщо літери, які позначають множини, виписати в один ряд. Наприклад, дерево відображене на рис 2.3, можна подати у вигляді (A(B(E, F), C (D))). Нумерація розділів у книжці чи дослідницькій роботі також є одним із способів представлення деревовидної структури. Її називають десятковою системою Д’юї, по аналогії с класичною схемою у бібліотеках. Для дерева розглянутого вище, вона матиме такий вигляд 1 A; 1.1 B, 1.1.1 E; 1.1.2 F 1.2 С; 1.2.1 D.

Розглянуті способи можна застосовувати і до лісу дерев, а не лише одного дерева.

Розглянемо інші способи зберігання дерев у комп’ютері. Оскільки дерево є графом, то для нього можна застосовувати способи зберігання графів. Але матриця інцидентності та матриця суміжності дерева будуть заповнені в основному нулями, і ці способи для них є малоефективними. Щодо спску суміжності та списку ребер можна сказати що ці способи є ефективними, якщо вважати дерево орієнтованим графом у якому дуги спрямовані від кореня до листків.

Розглянемо список суміжності дерева, розглянутого у прикладах вище.

Легко зауважити, що список у лівій частині буде містити батька, а у правій – його синів. Очевидно, що права частина міститиме список елементів, довжина якого наперед невідома, хіба за заданого обмеження на кількість синів у внутрішніх вершинах дерева.

Цю проблему можна вирішити, якщо розглядати дерево як орієнтований граф від листків до батька, то ми отримаємо наступний список суміжності

Цей спосіб зручний для табличного подання інформації і часто використовується у базах даних. Існує інший спосіб подання, який надає змогу подавати m-арні дерева у вигляді бінарних, який подає інформацію у дереві за допомогою таблиці із 3-ох колонок – Вершина, Лівий син, Брат.

Приклад. Розглянемо ліс з 2 дерев.

Приведемо його до бінарного вигляду, переставивши зв'язки між вершинами, поставивши зв’язки лише між батьком та лівим сином і правим братом. Можна корені двох дерев вважати синами вершини з порожньою назвою.

Таким чином, результуюче дерево буде бінарним і його можна відредагувати, нахиливши під кутом 45 градусів.

Якщо подати інформацію у таблиці відповідно отримаємо

Ще одною причиною для приведення m -арного до бінарного є простий рекурсивний вигляд бінарного дерева, кожна вершина якого задається таким самим об’єктом у пам’яті комп’ютера, що зумовлює просту обробку дерев. Наприклад, бінарне дерево можна задати відповідною структурою об’єктів

Кожен з об’ктів має дані (в нашому випадку назву вершини), а також посилання на синів.

Бінарні дерева також можуть бути збережені у масиві. Такий метод є ефективний щодо економії пам'яті і швидкості доступу. В такому представленні, якщо вершина має порядковий номер k, то її діти знаходяться за індексами 2k+1 та 2k+2, а батьківська вершина за індексом (k-1)/2. R – корінь дерева завжди поміщають на початок масиву і він матиме індекс рівний нулю. Для дерева висотою h максимальна кількість елементів у масиві буде рівна 2^h-1.

Приклад. Розглянемо дерево

Масив елементів у дереві

Частина елементів масиву буде порожньою, але не зважаючи на це економія відбудеться за рахунок того, що ми зберігаємо лише дані масиву, а зв’язки між елементами обчислюються за допомогою індексів, і не потребують збереження.