Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 89 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

. Практикум по курсу «Алгоритмизация и программирование». Часть 2
Глава 3. Нелинейные структуры данных
Раздел 6. Деревья
Еще одним из наиболее важных видов динамических структур данных яв-
ляются деревья. Существует большое количество видов деревьев – свобод-
ные, ориентированные, упорядоченные, бинарные деревья, В-деревья. В дан-
ном разделе будут рассматриваться только бинарные деревья. Формально би-
нарное дерево можно представить в виде набора узлов (вершин), один из ко-
торых называется корнем дерева, а остальные узлы образуют два непересе-
кающихся подмножества, каждое из которых также образует дерево (рис. 6.1).
Узлы соединены между собой дугами. От каждого узла бинарного дерева мо-
жет исходить две дуги к левому и правому узлам. При этом начальный узел
называется родительским, два других узла – его потомками.
Рис. 6.1. Вид бинарного дерева.
На рис. 6.1 узел «17» является корнем дерева – узлом, у которого нет
узла-родителя. Остальные узлы образуют два непересекающихся подмноже-
ства, называемых левым и правым поддеревьями. Узлы «6» и «20» являются
потомками узла «17».
В свою очередь, каждое поддерево также является деревом, например,
корнем левого поддерева является узел «6», который имеет двух потомков
(рис. 6.2).
89
            .       Практикум по курсу «Алгоритмизация и программирование». Часть 2
                        Глава 3. Нелинейные структуры данных

                                                        Раздел 6. Деревья

    Еще одним из наиболее важных видов динамических структур данных яв-
ляются деревья. Существует большое количество видов деревьев – свобод-
ные, ориентированные, упорядоченные, бинарные деревья, В-деревья. В дан-
ном разделе будут рассматриваться только бинарные деревья. Формально би-
нарное дерево можно представить в виде набора узлов (вершин), один из ко-
торых называется корнем дерева, а остальные узлы образуют два непересе-
кающихся подмножества, каждое из которых также образует дерево (рис. 6.1).
Узлы соединены между собой дугами. От каждого узла бинарного дерева мо-
жет исходить две дуги к левому и правому узлам. При этом начальный узел
называется родительским, два других узла – его потомками.




                         Рис. 6.1. Вид бинарного дерева.


    На рис. 6.1 узел «17» является корнем дерева – узлом, у которого нет
узла-родителя. Остальные узлы образуют два непересекающихся подмноже-
ства, называемых левым и правым поддеревьями. Узлы «6» и «20» являются
потомками узла «17».
    В свою очередь, каждое поддерево также является деревом, например,
корнем левого поддерева является узел «6», который имеет двух потомков
(рис. 6.2).




                                      89

Страницы