Бинарное дерево количество листьев

Python алгоритмы

Блог про алгоритмы и все что с ними связано. Основной инструмент реализации — Python.

Дай 10 !)

суббота, 30 июля 2011 г.

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

Бинарное дерево представляет собой структуру, в которой каждый узел (или вершина) имеет не более двух узлов-потомков и в точности одного родителя. Самый верхний узел дерева является единственным узлом без родителей; он называется корневым узлом. Бинарное дерево
с N узлами имеет не меньше [log₂N + 1] уровней (при максимально плотной упаковке узлов).
Если уровни дерева занумеровать, считая что корень лежит на уровне 1, то на уровне с номером К лежит 2 К-1 узел. У полного бинарного дерева с j уровнями (занумерованными от 1 до j) все листья лежат на уровне с номером j, и у каждого узла на уровнях с первого по j — 1
в точности два непосредственных потомка. В полном бинарном дереве с j уровнями 2 j — 1 узел.
*-Нравится статья? Кликни по рекламе! 🙂

Бинарные деревья поиска обычно применяются для реализации множеств и ассоциативных массивов. И применяются для быстрого поиска информации. Например в статье Двоичный (бинарный) поиск элемента в массиве мы искали во встроенной в Python структуре данных, типа list, а могли реализовать бинарное дерево. Двоичные деревья, как и связные списки, являются рекурсивными структурами.
Различные реализации одного и того же бинарного дерева

• полное(расширенное) бинарное дерево — каждый узел, за исключением листьев, имеет по 2 дочерних узла;
• идеальное бинарное дерево — это полное бинарное дерево, в котором все листья находятся на одной высоте;
• сбалансированное бинарное дерево — это бинарное дерево, в котором высота 2-х поддеревьев для каждого узла отличается не более чем на 1. Глубина такого дерева вычисляется как двоичный логарифм log(n), где n — общее число узлов;
• вырожденное дерево — дерево, в котором каждый узел имеет всего один дочерний узел, фактически это связный список;
• бинарное поисковое дерево (BST) — бинарное дерево, в котором для каждого узла выполняется условие: все узлы в левом поддереве меньше, и все узлы в правом поддереве больше данного узла.

1. сконструировать бинарное дерево таким образом, чтобы сумма путей была минимальной, так как это сокращает время вычислений для различных алгоритмов.
2. сконструировать полное расширенное бинарное дерево таким образом, чтобы сумма произведений путей от корневого узла до листьев на значение листового узла была минимальной.

2 3 5 7 11 13 17 19 23 29 31 37 41 5 5 7 11 13 17 19 23 29 31 37 41 10 7 11 13 17 19 23 29 31 37 41 17 24 17 19 23 29 31 37 41 24 34 19 23 29 31 37 41 24 34 42 29 31 37 41 42 53 65 37 41 42 53 65 78 95 65 78 95 143 238

Более полную статью, по кодам Хаффмана читай в моей более ранней статье.

Реализация:
До этого, в своих статьях я показывал силу функционального программирования Python.
Теперь, пришло время, показать ООП в действии, создав новую структуру данных Tree, состоящую из других структур, типа Node.
Сразу скажу, что код взят с сайта IBM с минимальными изменениями и дополнениями. С моей точки зрения данный класс является недееспособным с точки зрения добавления элементов,по причине того, что мы сами должны строить дерево, помня структуру у себя в голове, а ведь мы можем и ошибиться. И позже я напишу так, как мне кажется верным, где добавление элемента является рекурсивным проходом по дереву и поиску подходящего места. А пока, разберем, что есть:

class node: def __init__(self, data = None, left = None, right = None): self.data = data self.left = left self.right = right def __str__(self): return 'Node ['+str(self.data)+']' #/* класс, описывающий само дерево */ class Tree: def __init__(self): self.root = None #корень дерева # /* функция для добавления узла в дерево */ def newNode(self, data): return node(data,None,None)

Дальше, все функции расширяют класс Tree.

Высота бинарного дерева
Для определения высоты дерева потребуется пройти от корня сначала по левому поддереву, потом по правому, сравнить две этих высоты и выбрать максимальное значение. И не забыть к получившемуся значению прибавить единицу (корневой элемент). Мы реализуем её в привычном уже нам рекурсивном виде.

# /* функция для вычисления высоты дерева */ def height(self,node): if node==None: return 0 else: lheight = self.height(node.left) rheight = self.height(node.right) if lheight > rheight: return(lheight+1) else: return(rheight+1)

«Зеркальное» отражение бинарного дерева
Когда два дерева являются зеркальным отражением друг друга, то говорится, что они симметричны. Для получения «зеркальной» копии дерева сначала выполняется проверка на наличие у корня дерева дочерних узлов, и если эти узлы есть, то они меняются местами. Потом эти же действия рекурсивно повторяются для левого и правого дочерних узлов. Если существует только один дочерний узел, тогда можно переходить на один уровень ниже по дереву и продолжать.

# /* функция для зеркального отражения дерева */ def mirrorTree(self, node): if node.left and node.right: node.left,node.right=node.right,node.left self.mirrorTree(node.right) self.mirrorTree(node.left) else: if node.left==None and node.right: return self.mirrorTree(node.right) if node.right==None and node.left: return self.mirrorTree(node.left)

Проверка наличия узла в бинарном дереве
Нужно только учесть, что данная функция не работает для зеркального отображения дерева!

# /* функция для проверки наличия узла */ def lookup(self, node, target): if node == None:return 0 else: if target == node.data: return 1 else: if target < node.data: return self.lookup(node.left, target) else: return self.lookup(node.right, target)

Ширина бинарного дерева
Под шириной дерева понимается максимальное количество узлов, которые расположены на одной высоте. Чтобы определить ширину дерева, достаточно просто добавить счетчик в уже рассмотренный алгоритм для определения высоты дерева.

# /* функция для вычисления ширины дерева */ def getMaxWidth(self,root): maxWdth = 0 i = 1 width = 0 ; h = self.height(root) while( i < h): width = self.getWidth(root, i) if(width >maxWdth): maxWdth = width; i +=1 return maxWdth; def getWidth(self, root, level): if root == None: return 0 if level == 1: return 1 elif level > 1: return self.getWidth(root.left, level-1) + self.getWidth(root.right, level-1)

# /* функция для распечатки элементов на определенном уровне дерева */ def printGivenLevel(self, root, level): if root == None: return if level == 1: print ("%d " % root.data) elif level > 1: self.printGivenLevel(root.left, level-1); self.printGivenLevel(root.right, level-1); # /* функция для распечатки дерева */ def printLevelOrder(self, root): h = self.height(self.root) i=1 while(i<=h): self.printGivenLevel(self.root, i) i +=1

def sameTree(a, b): if a==None and b==None: return 1 elif a and b: return( a.data == b.data and sameTree(a.left, b.left) and sameTree(a.right, b.right) ) return 0

Количество узлов в бинарном дереве
Вычислить количество узлов в бинарном дереве также можно с помощью рекурсии.
Хотя с точки зрения производительности и принципов ООП, правильнее встроить счетчик в сам объект.

def size(node): if node==None:return 0; return(size(node.left) + 1 + size(node.right));

Немножко о производительности
Я протестировал наш класс на поиск. К сожалению, данная его реализация проиграла бинарному поиску по списку, описанному ранее. Я тестировал, запуская в 100000 цикле поиска элемента со значением 5 и результат нашего класса
400003 function calls (100003 primitive calls) in 3.481 seconds
против
200003 function calls in 1.791 seconds
Я считаю, что причина в рекурсивном исполнении данного метода + реализации на Python, а не Си)

1. Дж. Макконнелл - Основы современных алгоритмов.
2. Структуры данных: бинарные деревья. Часть 1
3. Работа со структурами данных в языках Си и Python: Часть 6. Двоичные деревья
4. Может быть полезным Обходы бинарных деревьев

Источник

Бинарное дерево: посчитать количество листьев

Нужно построить бинарное дерево типа *char. В этом бинарном дереве найти количество листьев (листья, как я понимаю, это элементы, которые не содержат потомков). Попробовал написать, но выводится какая-то каша-малаша. Не совсем понимаю принцип работы этого дерева. Был бы очень благодарен за помощь
С односвязными и двусвязными списками было как-то проще.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

#include #include using namespace std; struct point { char *key;//информационное поле point *left;//адрес левого поддерева point *right;//адрес правого поддерева }; //добавление элемента d в дерево поиска Корень Левое поддерево Правое поддерево //построение идеально сбалансированного дерева point* Tree(int n, point* beg) { point*r; int nl, nr; if (n == 0) { beg = NULL; return beg; } nl = n / 2; nr = n - nl - 1; r = new point; char s[50]; cout  "Слово: "; cin >> s; r->key = new char[strlen(s) + 1]; r->left = Tree(nl, r->left); r->right = Tree(nr, r->right); beg = r; return beg; } void treeprint(point *beg) { if (beg != NULL) { treeprint(beg->left); cout  beg->key  endl; treeprint(beg->right); } } int main() { setlocale(LC_ALL, "russian"); srand(time(NULL)); int n = 0, k = 0; point *beg = nullptr; do { cout  "1. Создать бинарное дерево\n"; cout  "2. Показать бинарное дерево\n"; cout  "3. Выход\n"; cin >> k; switch (k) { case 1: cout  "Введите количество элементов"  endl; cin >> n; beg = Tree(n, beg); cout  endl; break; case 2: treeprint(beg); cout  endl; break; } } while (k != 3); system("pause"); return 0; }

Источник

13.3. Алгоритмы работы с деревьями

А1. Вычисление суммы значений информационных полей элементов

Алгоритм реализован в виде функции, возвращающей значение суммы информационных полей всех элементов. Тривиальным считается случай, когда очередной узел – пустой, и, следовательно, не имеет информационного поля.

function Sum(Root : PNode) : integer;

if Root=Nil then

Sum := Root^.Data + Sum(Root^.left)

Для нетривиального случая результат вычисляется как значение информационного элемента в корне (Root^.Data) плюс суммы информационных полей левого и правого поддеревьев.

А выражение Sum(Root^.left)представляет собой рекурсивный вызов левого поддерева для данного корня Root.

А2. Подсчет количества узлов в бинарном дереве

function NumElem(Tree:PNode):integer;

if Tree = Nil then

А3. Подсчет количества листьев бинарного дерева

function Number(Tree:PNode):integer;

if Tree = Nil then

else if (Tree^.left=Nil) and (Tree^.right=Nil) then

Number := Number(Tree^.left) + Number(Tree^.right);

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

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

А4. Алгоритмы просмотра дерева

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

а. Просмотр дерева слева – направо

procedure ViewLR(Root:PNode); Left – Right >

if Root<>Nil then

вывод на печать, в файл и др.>

Источник