Между деревьями общего вида (узел дерева может иметь более двух сыновей) и бинарными деревьями существует взаимно однозначное соответствие, поэтому бинарные деревья часто используют для представления деревьев общего вида. Для такого представления используют следующий алгоритм:
1. изображаем корень дерева;
2. по вертикали изображаем старшего сына этого корня;
3. по горизонтали вправо от этого узла представляем всех его братьев;
4. пп. 1, 2, 3 повторяем для всех его узлов.
Таким образом, получаем, что вертикальные ребра изображают левые поддеревья, а горизонтальные – правые.
Данный алгоритм можно распространить и для леса.
Теорема. Число бинарных деревьев с n вершинами можно выразить формулой: . Например, для n=3 имеем
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав!Последнее добавление