Минимальная высота бинарного дерева

3.3. Бинарные деревья

3.3.1. Определение. Представления бинарных деревьев

Бинарное (двоичное) дерево — особый вид дерева, в котором каждый узел имеет не более двух поддеревьев, причем в случае одного поддерева следует различать левое и правое поддерево. При изображении бинарных деревьев левого и правого сына различают по наклону соединительной линии (влево или вправо). На рис.3.4 показаны два различных бинарных дерева. Интересно отметить, что если рассматривать данные структуры как обычные упорядоченные деревья, то они являются полностью идентичными (в упорядоченном дереве единственный сын всегда первый, т. е. левый потомок). Это говорит о том, что бинарные деревья не являются частным случаем упорядоченого дерева, а представляют собой особый вид деревьев.

Рис.3.5. Два различных бинарных дерева

Приведем формальное рекурсивное определение бинарного дерева [8].

Бинарное дерево — конечное множество узлов, которое является пустым или состоит из корня и двух непересекающихся бинарных деревьев, которые называются левым и правым поддеревьями данного корня.

Обратим внимание на то, что бинарное дерево может быть пустым, в отличие от обычного дерева, которое всегда содержит хотя бы один узел (однако лес может быть пустым).

Бинарное дерево может быть представлено и в форме скобочного выражения. Аналогично обычному корневому дереву, для бинарного дерева также возможен различный порядок перечисления узлов в скобочном представлении. Например, левое скобочное представление непустого бинарного дерева рекурсивно определяется так:

Иногда при записи левое и правое поддерево разделяют запятыми, но чаще пробелом.

Левое или правое поддерево или оба вместе (для листьев) могут быть пустыми, при этом для пустых деревьев часто используется специальное обозначение . Чтобы сократить запись, в ней разрешается опустить правое поддерево, если оно пустое, а для листьев опустить оба пустых поддерева (но нельзя опускать пустое левое поддерево, иначе по такой записи нельзя будет правильно восстановить изображение бинарного дерева!). Так, деревьям, изображенным на рис.3.5, соответствуют различные левые скобочные записи в сокращенной форме:

Бинарные деревья, у которых все узлы, кроме листьев, имеют сторого по два сына, называются строго бинарными. Деревья, изображенные на рис. 3.5, не являются строго бинарными.

3.3.2. Математические свойства бинарных деревьев

Бинарные деревья, как абстрактные математические объекты, обладают рядом интересных свойств, которые могут пригодиться при анализе различных алгоритмов, поэтому остановимся подробнее на этом вопросе.

На любом уровне n бинарное дерево может содержать от 1 до 2 n узлов. Число узлов, приходящееся на уровень, является показателем плотности дерева. На рис. 3.6 дерево А содержит 8 узлов при высоте 3, в то время как дерево B содержит 5 узлов при высоте 4.

Последний случай является особой формой, называемой вырожденным (degenerate) деревом, у которого есть единственный лист (e) и каждый внутренний узел имеет только одного сына. Вырожденное дерево можно считать аналогом линейного связного списка, его высота равна количеству узлов без единицы. Это максимально возможное значение для высоты бинарного дерева. В большинстве алгоритмов, использующих бинарные деревья, вырожденное дерево — наихудший случай при оценке производительности.

Рис.3.6. Бинарные деревья различной плотности

Наоборот, деревья с большой плотностью очень важны в качестве структур данных, так как они содержат пропорционально больше элементов вблизи корня, т.е. с более короткими путями от корня.

Наивысшей степенью плотности обладают полные бинарные деревья, которые имеют 2 k узов на каждом уровне k.

Рис.3.7. Полное и почти полное бинарные деревья

На рис. 3.7, а показано полное бинарное дерево высоты два. Обратим внимание на такие факты.

На нулевом уровне имеется 2 0 узлов, на первом — 2 1 , на втором — 2 2 и т.д. На первых k-1 уровнях количество узлов составляет

1 + 2 + 4 + . + 2 k-1 = 2 k -1

На уровне k количество узлов 2 k , т. е. ровно на один больше.

Из этого следует, что в полном бинарном дереве количество внутренних узлов на единицу меньше количества листьев. Зная количество листьев, легко определить и высоту h полного бинарного дерева:

h=log ₂ n, где n — количество листьев

h= log ₂ (N+1)-1, где N —количество узлов полного бинарного дерева.

Для полного бинарного дерева приведенные формулы дают точное значение, сответствующее минимальному значению высоты при таком количестве узлов. Если количество узлов дерева такое, что невозможно построить полное бинарное дерево, для получения бинарного дерева минимально возможной высоты необходимо заполнять все уровни дерева, кроме последнего, максимально возможным количеством узлов. Если оставшиеся узлы располагать на последнем уровне по порядку, начиная слева, то полученное таким образом бинарное дерево называют почти полным. На рис. 3.7, б изображено пости полное бинарное дерево.

Полные и почти полные бинарные деревья обладают еще одним интересным свойством — если их узлы нумеровать, начиная с единицы, сверху вниз и слева направо, то левому сыну всегда будет соответствовать код, в два раза больше кода его родителя, а правому сыну — код, на единицу больший, чем код код левого сына (рис.3.8). Номер корня всегда равен 1, его левый потомок получает номер 2, правый — номер 3. Левый потомок узла 2 получит номер 4, а правый — 5, левый потомок узла 3 получит номер 6, правый — 7 и т.д. Такая схема нумерации используется при представлении деревьев с помощью массивов. К этой теме мы еще вернемся.

Рис.3.8. Нумерация узлов полного или почти полного бинарного дерева

По такой схеме можно нумеровать и узлы бинарных деревьев, которые не являются почти полными, поскольку в этом случае гарантируется уникальность каждого номера, если в процессе работы к дереву добавляются новые листья. Используя такой способ нумерации, можно реализовать древовидную структуру на основе массива. Такая реализация будет приведена в главе 4.

После анализа основных свойств бинарных деревьев можно снова вернуться к упорядоченным деревьям и лесам и проанализировать соответствие между этими структурами и бинарным деревом.

Источник

Алгоритм формирования бинарного дерева минимальной высоты

Если в упорядоченной последовательности есть элементы, то создать корень и записать в него средний элемент последовательности, для первой части элементов последовательности (от первого до среднего элемента) построить левое поддерево, а для второй (от среднего до последнего) — правое поддерево.

БД, в котором относительно каждой вершины дерева количество вершин в левом и правом поддеревьях может отличаться максимум на единицу, называется идеально сбалансированным.

Сформировать идеально сбалансированное БД для заданной упорядоченной по возрастанию последовательности неповторяющихся элементов можно с помощью итеративного алгоритма. Средний элемент последовательности будет корнем БД и он разбивает последовательность на две части — левую и правую. Левое поддерево корня строится из левой части последовательности, а правое — из правой части точно также, как и БД для всей последовательности. Поэтому границы вновь образующихся последовательностей и адрес корня будем хранить в стеке.

Итеративный алгоритм формирования сбалансированного бинарного дерева

1. Создать корень, занести в него значение среднего элемента последовательности. Адрес корня, границы правой и левой части последовательности занести в стек.

2. Пока стек не пуст, извлечь из стека границы левой, правой части последовательности и адрес корня.

Если левой части нет, то нет левого поддерева для корня, иначе создать корень левого поддерева (левого сына), записать в него значение среднего элемента левой части, адрес левого сына и границы левой и правой части занести в стек.

Если правой части нет, то нет правого поддерева для корня, иначе создать корень правого поддерева (правого сына), записать в него значение среднего элемента правой части, адрес правого сына и границы левой и правой части занести в стек.

Представление алгебраических выражений бинарными деревьями

Любое алгебраическое выражение, которое содержит переменные, константы, знаки операций и скобки можно представить в виде бинарного дерева, в котором знак операции помещается в корне, первый операнд — в левом поддереве, а второй операнд — в правом. Скобки при этом опускаются. В результате все константы и переменные окажутся в листьях, а знаки операций — во внутренних вершинах. БД алгебраического выражения a + 5 * b * (3 + c * d) представлено на рис.28.

Источник

минимальная высота бинарного дерева?

Я задаю этот вопрос после прочтения следующего поста:

На самом деле я хочу, чтобы мой алгоритм возвращал 4, если входные данные для двоичного дерева следующие: 100, 50, 70, 60.

но приведенный ниже код возвращает только 1, потому что он не различает лист [left == NULL && right == NULL] и узел только с одним дочерним элементом.

int minDepth(TreeNode root) < if (root == null) < return 0; >return 1 + Math.min(minDepth(root.left), minDepth(root.right)); > 

Никто не объяснил, что нам делать, если мы хотим, чтобы результат был равен 4 вместо 1.

Может кто-нибудь показать мне код, который возвращает 4 вместо 1?

Я думаю, что я выбрал неправильные значения выборки выше, и люди запутываются в том, что я на самом деле ищу !! Итак, переформулируем мои вопросы ниже:

Предположим, что любой узел может иметь 0,1 или 2 дочерних элемента. Пожалуйста, рассмотрите этот пример ввода — 100, 50, 150, 30, 70, 200, 20, 40, 60, 80, 10. Теперь я хочу, чтобы моя функция возвращала высоту как 3 [100-> 150-> 200]. Я называю эту ветку [100-> 150-> 200] минимальной высотой дерева. Я могу ошибаться в аналогии с минимальной высотой, НО все, что я хочу, это вернуть 3.

 100 / \\ / \\ 50 150 / \ \\ 30 70 200 / \ / \ 20 40 60 80 / 10 

И мне нужно выяснить кратчайшее расстояние между корневым узлом и листовым узлом [100-> 150-> 200] = 3.

struct node < struct node* left; int data; struct node* right; >; void add(struct node** root, int data) < if(*root == NULL) < (*root) = (struct node*)malloc(sizeof(node)); (*root)->left = NULL; (*root)->right = NULL; (*root)->data = data; > else < if(data < (*root)->data ) add(&(*root)->left, data); else add(&(*root)->right, data); > > void inorder(struct node* root) < if(root == NULL) return; inorder(root->left); coutdataright); > int minDepth(struct node* root) < if (root == NULL) < return 0; >return 1 + min(minDepth(root->left), minDepth(root->right)); > int main() < struct node* root = NULL; add(&root, 100); add(&root, 50); add(&root, 150); add(&root, 30); add(&root, 70); add(&root, 200); add(&root, 20); add(&root, 40); add(&root, 60); add(&root, 80); add(&root, 10); inorder(root); cout

Решение

Мне кажется, что вы хотите знать размер дерева, а не его высоту.

Поэтому вместо того, чтобы выбирать наименьшую высоту из двух поддеревьев под корнем (функция minDepth), вы хотите суммировать их размеры.

Следующая функция добавляет единицу к размеру каждого из левого и правого поддеревьев, если узел не является нулевым (на самом деле он вообще не был бы узлом и не должен учитываться).

int sizeOfTree(TreeNode root) < if (root == nulll) return 1 + sizeOfTree(root.left) + sizeOfTree(root.right); > 

Рекурсивно это найдет количество узлов в вашем дереве (также известное как его размер).

РЕДАКТИРОВАТЬ: После того, как вопрос был рассмотрен, я думаю, что это то, что вы хотите:

int shortestBranch(TreeNode root) < if (root == null) if (root.left == null && root.right == null) < return 1; >else if (root.left == null) < return 1 + shortestBranch(root.right); >else if (root.right == null) < return 1 + shortestBranch(root.left); >else < return 1 + Math.min(shortestBranch(root.right), shortestBranch(root.left)); >> 

Другие решения

int minDepth( TreeNode root )

Источник