Деревья
Конечное корневое дерево
![](../../../../img/tex/0/0/0/000b3670b74ec4c1c9978736730ae40f.png)
![](../../../../img/tex/4/6/5/465e85a58cc38d3a16507157a0030baa.png)
поддеревьев
![](../../../../img/tex/8/0/5/805bb1cd9158746146eb89be932af183.png)
![](image/04-01.jpg)
Рис. 4.1.
Дерево с 11 узлами, помеченными буквами от
![](../../../../img/tex/3/9/b/39bfa1adef805e1f98298e189c2c0b65.png)
![](../../../../img/tex/2/8/4/28448eddf2dc49e717ec17777dc15890.png)
![](../../../../img/tex/f/0/1/f01d347fc7bed08e75ee641fc7520d7a.png)
![](../../../../img/tex/3/9/b/39bfa1adef805e1f98298e189c2c0b65.png)
В первой лекции уже было использовано дерево - при изучении необходимого числа взвешиваний в задаче о фальшивой монете с
![](../../../../img/tex/a/7/4/a7466f63abf1057fc1e10136891431ed.png)
В описании соотношений между узлами дерева используем терминологию, принятую в генеалогических деревьях. Так, говорят, что в дереве или поддереве все узлы являются потомками его корня, и наоборот, корень есть предок всех своих потомков. Корень именуют отцом корней его поддеревьев, которые в свою очередь будут сыновьями корня. Например, на рис. 4.1 узел
![](../../../../img/tex/3/9/b/39bfa1adef805e1f98298e189c2c0b65.png)
![](../../../../img/tex/9/c/d/9cdb2f4c06d9ecc084575314fa650d14.png)
![](../../../../img/tex/a/c/a/aca9a6f97bbb2536a408190944e39b7a.png)
![](../../../../img/tex/f/d/f/fdfea8b8d0f6f6089f6a75529761bde4.png)
![](../../../../img/tex/a/c/a/aca9a6f97bbb2536a408190944e39b7a.png)
![](../../../../img/tex/d/8/1/d81eb779c37ec37c3a10ffb96fe8cd61.png)
Все рассматриваемые нами деревья будут упорядочены, то есть для них будет важен относительный порядок поддеревьев каждого узла. Таким образом, деревья считаются различными.
![](image/04-02.jpg)
Рис. 4.2. Различные деревья
Определим лес как упорядоченное множество деревьев; в связи с этим можно перефразировать определение дерева: дерево есть непустое множество узлов, такое, что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы образуют лес с
поддеревьями корня. Важной разновидностью корневых деревьев является класс бинарных деревьев. Бинарное дерево
![](../../../../img/tex/0/0/0/000b3670b74ec4c1c9978736730ae40f.png)
![](../../../../img/tex/c/5/b/c5b5d84267eb3cf575255fba08f7d08f.png)
![](../../../../img/tex/2/5/3/25378e78bbf7976e0d3f526c06e4d167.png)
Бинарные деревья не являются подмножеством множества деревьев, они полностью отличаются по своей структуре, поскольку два следующих рисунка не изображают одно и то же бинарное дерево.
![](image/04-03.jpg)
Рис. 4.3. Различные бинарные деревья
Как деревья, однако, они не отличаются от дерева, изображенного на рис. 4.4.
![](image/04-04.jpg)
Рис. 4.4. Не бинарное дерево
Различие между деревом и бинарным деревом состоит в том, что дерево не может быть пустым, а каждый узел дерева может иметь произвольное число поддеревьев; в то же время, бинарное дерево может быть пустым. Каждая из вершин бинарного дерева может иметь 0, 1 или 2 поддерева, и существует различие между левым и правым поддеревьями.