Представление деревьев в памяти.

Кроме деревьев и ордеревьев изучаются также упорядоченные деревья.

·
Определение. Расстояние от корня ордерева до вершины х называется уровнем этой вершины

(номером яруса )

 
 

 

 


1

 

 

2

 

 


Максимальный из уровней вершин называют глубиной дерева ( высотой дерева ).

Если на каждом уровне множество вершин упорядоченно, то ордерево называют упорядоченным

Пример. Один и тот же граф, но разные упорядоченные ордеревья.

               
     
 
   
 

 

 

Пример. Сколько существует а) ордеревьев; б) упорядоченных ордеревьев; в) деревьев

с четырьмя вершинами?

а)

                       
     
       
 
 
 
   
 
     
 
 
 
 
 

 


Линейное 4 шт.

ордерево

 

б)

                   
     
       
5 шт.
 
 
   
 

 

 


в)

 

       
   
2 шт.
 
 

 


Опр.Если каждая вершина ордерева имеет не более двух потомков, то ордерево называется бинарным.

                   
     
 
 
     
 

 


бинарное небинарное ( тринарное)

Для бинарного ордерева имеют смысл понятия левого и правого потомка.

 

Сопоставим корню бинарного ордерева пустое множество, а его потомкам – 0 и 1.

Левому потомку корня присвоим 0, а правому 1. Потомкам 0 присвоим 00 01, а потомкам 1 присвоим 10 и 11 и т.д.