Число уровней бинарного дерева

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. Может быть полезным Обходы бинарных деревьев

Источник

Число уровней бинарного дерева

При написании программы построения, вывода на экран и подсчета числа уровней в бинарном дереве возникли проблемы с подсчетом уровней, причем подсчет уровней реализован не для структурированного дерева, а следующего типа (Вид слева, корень дерева = 5):

#ifndef TEST2_H_INCLUDED
#define TEST2_H_INCLUDED

typedef struct _node *TreeNode;
typedef struct _root Tree;

struct _root
TreeNode root;
>;

struct _node
double data;
TreeNode left;
TreeNode right;
>;

void CreateTree(Tree*);
void Insert(Tree*, double);
void Print(Tree*);
int Depth(Tree*);

int main() int n;
double x;
Tree t;
CreateTree(&t);

case 3:
printf ("Depth of tree is: %d\n", Depth(&t));
printf("%d\n",h2);
printf("%d\n",h1);
h3=h2=h1=0;
break;

case 0:
n = -1;
break;
default:
printf("Nothing\n");
break;
>
>
return 0;
>

typedef struct _node *TreeNode;
typedef struct _root Tree;

struct _root
TreeNode root;
>;

struct _node
double data;
TreeNode left;
TreeNode right;
>;

TreeNode malloc_node() TreeNode n = (TreeNode)malloc(sizeof(struct _node));
n->left = n->right = NULL; // -> обращение к указателю
return n;
>

void CreateTree(Tree *t) t->root = NULL;
>

void ins(TreeNode *t, double k)

void Insert(Tree *t, double k) if(!t->root) t->root = malloc_node();
t->root->data = k;
>else ins(&(t->root), k);
>
>

void _print(TreeNode t, int tab) if(t) _print(t->right, tab + 2);
int i;
for(i = 0; i < tab; i++)putchar(' ');
>
i = 0;
printf("%.0f\n", t->data);
_print(t->left, tab + 2);
>
>

void Print(Tree *t) _print(t->root, 0);
>

int h1=0, h2=0, h3=0;
int Depth1(TreeNode *t)
if (t==NULL) h3=0;

int Depth(Tree *t) if(t->root) Depth1(&(t->root));
if (h1>h2) h3=h1;
else h3=h2;
return h3;
>

Красным выделена часть реализации подсчета числа уровней в бинарном дереве.

Подробнее о работе программы и о проблеме:
меню:
по значению "1" - построение дерева
по значению "2" - распечатать дерево
по значению "3" - подсчет уровней дерева, начиная с "0" уровня

______8
____7
__6
5
__4
то, подсчет числа узлов будет равен:
3 уровня (right)
1 уровень (left), что будет правильным
, но если добавить 2 и 3, то получился след. дерево:

______8
____7
__6
5
__4
_____3
____2
и число уровней будет:
4
2
т.е. при оптимизации дерева, новое значение добавляется к right.

Сталкивался кто-нибудь с такой проблемой или реализовывал похожий метод?
Нужна помощь, ребят!

Источник