Найти глубину бинарного дерева

Деревья поиска

Дерево — одна из наиболее распространенных структур данных в программировании.

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

• Родитель вершины $v$ — вершина, из которой есть прямая ссылка в $v$.
• Дети (дочерние элементы, сын, дочь) вершины $v$ — вершины, в которые из $v$ есть прямая ссылка.
• Предки — родители родителей, их родители, и так далее.
• Потомки — дети детей, их дети, и так далее.
• Лист (терминальная вершина) — вершина, не имеющая детей.
• Поддерево — вершина дерева вместе со всеми её потомками.
• Степень вершины — количество её детей.
• Глубина вершины — расстояние от корня до неё.
• Высота дерева — максимальная из глубин всех вершин.

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

Деревья также используются в контексте графов.

Бинарные деревья поиска

Бинарное дерево поиска (англ. binary search tree, BST) — дерево, для которого выполняются следующие свойства:

• У каждой вершины не более двух детей.
• Все вершины обладают ключами, на которых определена операция сравнения (например, целые числа или строки).
• У всех вершин левого поддерева вершины $v$ ключи не больше, чем ключ $v$.
• У всех вершин правого поддерева вершины $v$ ключи больше, чем ключ $v$.
• Оба поддерева — левое и правое — являются двоичными деревьями поиска.

Более общим понятием являются обычные (не бинарные) деревья поиска — в них количество детей может быть больше двух, и при этом в «более левых» поддеревьях ключи должны быть меньше, чем «более правых». Пока что мы сконцентрируемся только на двоичных, потому что они проще.

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

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

Эта функция — как и многие другие основные, например, вставка или удаление элементов — работает в худшем случае за высоту дерева. Высота бинарного дерева в худшем случае может быть $O(n)$ («бамбук»), поэтому в эффективных реализациях поддерживаются некоторые инварианты, гарантирующую среднюю глубину вершины $O(\log n)$ и соответствующую стоимость основных операций. Такие деревья называются сбалансированными.

Источник

Бинарное дерево поиска (определить максимальную глубину)

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

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 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156

#include #include #include #include using namespace std; class TREE{ public: struct tree{ int data; int view;//для обхода дерева struct tree *Left; struct tree *Right; struct tree *Prev;//для стека }; struct tree *Work; struct tree *Root; void Create(int i); void PushTree(int i); void PrintTree(); void DeleteTree(); private: void CreateStack(void); struct tree *top; void PushStack(struct tree *a); void PopStack(); }; void TREE::CreateStack(void){ Root->Prev=NULL; top=Root; } void TREE::PushStack(struct tree *a){ a->Prev=top; top=a; } void TREE::PopStack(){ top=top->Prev; } void TREE::Create(int i){ Work=(struct tree*)malloc(sizeof(struct tree)); Work->Left=NULL; Work->Right=NULL; Work->data=i; Work->view=-1; Root=Work; } void TREE::PushTree(int i){ Work=Root; while(Work!=NULL){//Поиск листа для добавления if(iWork->data){ if(Work->Left==NULL){ break; } Work=Work->Left; } else{ if(Work->Right==NULL){ break; } Work=Work->Right; } } //Добавление нового узла if(iWork->data){//Левый сын Work->Left=(struct tree*)malloc(sizeof(struct tree)); Work=Work->Left; Work->Left=NULL; Work->Right=NULL; Work->data=i; Work->view=-1; } else{//Правый сын Work->Right=(struct tree*)malloc(sizeof(struct tree)); Work=Work->Right; Work->Left=NULL; Work->Right=NULL; Work->data=i; Work->view=-1; } } void CreateTree(TREE &BST){ srand(time(NULL)); int i; i=rand()%20+1; printf("%s%d","Data: ",i); BST.Create(i);//Создаем корень for(int j=0; j9; j++){//Остальные узлы i=rand()%20+1; BST.PushTree(i); printf("% d",i); } } void TREE::PrintTree(){ printf("\n\n"); CreateStack(); int i=0; while(top!=NULL){ while(top->Right!=NULL&&top->Right->view!=0){ PushStack(top->Right); i++; } if(top->view==-1){ for(int j=i; j>0; j--){ printf("\t"); } printf(" %d\n",top->data); top->view=0;//0-напечатана, -1-не напечатана } if(top->Left!=NULL&&top->Left->view==-1){ PushStack(top->Left); i++; continue; } PopStack(); i--; } } void TREE::DeleteTree(){ CreateStack(); int i=0; while(top!=NULL){ while(top->Right!=NULL){ Work=top; PushStack(top->Right); Work->Right=NULL; } if(top->Left!=NULL){ Work=top; PushStack(top->Left); Work->Left=NULL; continue; } if(top->Left==NULL&&top->Right==NULL){ Work=top; PopStack(); free(Work); } } } void main(){ TREE BST; CreateTree(BST); BST.PrintTree(); BST.DeleteTree(); }

Добавлено через 32 минуты
ребят, ну помогите кто нибудь, завтра сдавать, а в голове чёт пока ни одной идеи! =(

Источник

Найти глубину бинарного дерева — C (СИ)

Всем привет. Нужно найти глубину бинарного дерева, пробовал разные способы отсюда и не только, не получается никак. При заданном способе вообще ничего не выводится. Прога написана частями на с++, т.к. брал некоторые куски из разных источников. Функция для определения глубины getMaxDepth

#define _CRT_SECURE_NO_WARNINGS # include # include # include # include # include //#include #define FALSE 0 #define TRUE 1 using namespace std; struct STree < int info; STree *Left, *Right; STree *Root; >; STree* List(int i); STree* Make(STree *Root); STree* Del(STree *Root, int key); void View(STree *t, int level); void Del_All(STree *t); int getMaxDepth(STree*t, int depth); STree *Search(STree *Root, int key); int main() < SetConsoleCP(1251); SetConsoleOutputCP(1251); STree *Root = NULL; int done = FALSE; char c; int key; while (!done) < printf("Меню:\n" "1) Создать дерево\n" "2) Добавить ключ\n" "3) Поиск по ключу\n" "4) Удаление по ключу\n" "5) Показать дерево\n" "6) Глубина дерева\n" "7) Завершение программы\n"); c = _getch(); switch (toupper(c)) < case '1': Root = Make(Root); break; case '2': Root = Make(Root); break; case '3': printf("\n\tВведите ключ\n"); cin >> key; Root = Search(Root, key); break; case’4′: printf(«\n\tВведите ключ\n»); cin >> key; Root = Del(Root,key); break; case ‘5’: View(Root, 0); break; case’6′: getMaxDepth(Root,0); break; case ‘7’: Del_All(Root); done = TRUE; break; default: printf(«\n\aНекорректный ввод!\n»); > > return 0; > STree* Make(STree *Root) < STree *Prev = NULL, *t; int b, find; if (Root == NULL) < printf("Создание дерева"); printf("\n\tВведите корень\n"); cin >> b; Root = List(b); > while (1) < printf("\nВведите следующую ветвть\n"); cin >> b; if (b<0) break; t = Root; find = 0; while (t && !find) < Prev = t; if (b == t->info) find = 1; else if (b < t->info) t = t->Left; else t = t->Right; > if (!find) < t = List(b); if (b < Prev->info) Prev->Left = t; else Prev->Right = t; > > return Root; > STree* List(int i) < STree *t = new STree; t->info = i; t->Left = t->Right = NULL; return t; > STree* Del(STree *Root, int key) < STree *Del, *Prev_Del, *R, *Prev_R; Del = Root; Prev_Del = NULL; while (Del != NULL &&Del->info != key) < Prev_Del = Del; if (Del->info > key) Del = Del->Left; else Del = Del->Right; > if (Del == NULL) < printf("\n\t\aКлюч не найден!\n"); return Root; >if (Del->Right == NULL) R = Del->Left; else if (Del->Left == NULL) R = Del->Right; else < Prev_R = Del; R = Del->Left; while (R->Right != NULL) < Prev_R = R; R = R->Right; > if (Prev_R == Del) R->Right = Del->Right; else < R->Right = Del->Right; Prev_R->Right = R->Left; R->Left = Prev_R; > > if (Del == Root) Root = R; else if (Del->info < Prev_Del->info) Prev_Del->Left = R; else Prev_Del->Right = R; cout info void View(STree *t, int level) < if (t) < View(t->Right, level + 1); for (int i = 0; iinfo Left, level + 1); > > void Del_All(STree *t) < if (t != NULL) < delete(t->Left); delete(t->Right); delete t; > > int getMaxDepth(STree*t, int depth) < if (t == NULL) return depth; else return max(getMaxDepth(t->Left, depth + 1), getMaxDepth(t->Right, depth + 1)); printf(«гЛУБИНА ДЕРЕВА %d»,depth); > STree *Search(STree *Root, int key) < STree *Del, *Prev_Del, *R, *Prev_R; Del = Root; Prev_Del = NULL; while (Del != NULL &&Del->info != key) < Prev_Del = Del; if (Del->info > key) Del = Del->Left; else Del = Del->Right; > if (Del == NULL) < printf("\n\t\aКлюч Не найден!\n"); return Root; >cout info

Источник

Нахождение глубины бинарного дерева

У меня возникли проблемы с пониманием этого maxdepth-кода. Любая помощь будет оценена по достоинству. Вот пример, который я привел.

int maxDepth(Node *&temp) < if(temp == NULL) return 0; else < int lchild = maxDepth(temp->left); int rchild = maxDepth(temp->right); if(lchild

> В основном, я понимаю, что функция рекурсивно вызывает себя (для каждого левого и правого случаев), пока не достигнет последнего узла. как только он это делает, он возвращает 0, затем 0 +1. то предыдущий узел равен 1 +1. затем следующий — 2 +1. если есть bst с 3 левыми дочерними элементами, int lchild вернет 3. а дополнительный + 1 — корень. Поэтому мой вопрос заключается в том, откуда все эти +1. он возвращает 0 на последнем узле, но почему он возвращает 0 +1 и т.д., когда он идет вверх по левым/правым дочерним узлам? Я не понимаю, почему. Я знаю, что это так, но почему?

8 ответов

Помните, что в бинарных деревьях узел имеет не более 2-х детей (слева и справа)

Это рекурсивный алгоритм, поэтому он называет себя снова и снова.

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

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

Он погружается в два поддерева (temp-> влево и temp-> вправо) и повторяет операцию до тех пор, пока не достигнет узлов без детей. в этот момент он будет вызывать maxDepth слева и справа, который будет null и возвращает 0, а затем начнет возвращать цепочку вызовов.

Поэтому, если у вас есть цепочка из трех узлов (скажем, root-left1-left2), она перейдет влево2 и вызовет maxDepth (слева) и maxDepth (справа). каждый из них возвращает 0 (они равны нулю). то он возвращается влево2. он сравнивается, оба равны 0, поэтому больший из них, конечно, равен 0. он возвращает 0 + 1. то мы находимся налево1 — повторяет, обнаруживает, что 1 является большим из его правых справа (возможно, они одинаковы или не имеют права ребенка), поэтому он возвращает 1 + 1. теперь мы находимся у корня, то же самое, он возвращает 2 + 1 = 3, что является глубиной.

Рассмотрим эту часть (большего дерева):

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

Очевидно, указатель на A не является NULL , поэтому код должен:

• call maxDepth для каждого из детей A (левая и правая ветки). A->right — B , но A->left явно NULL (поскольку A не имеет левой ветки)
• сравните их, выберите наибольшее значение
• вернуть это выбранное значение + 1 (поскольку сам A берет уровень, не так ли?)

Теперь мы рассмотрим, как maxDepth(NULL) и maxDepth(B) .

Первое довольно легко: первая проверка сделает maxDepth возвращение 0. Если другой ребенок были NULL тоже, как глубина будет равна (0), и мы должны возвращать 0 + 1 для A сам.

Но B не пуст; он не имеет ветвей, хотя, поэтому (как мы заметили) его глубина равна 1 (наибольшая из 0 для NULL на обеих частях + 1 для самого B ).

Теперь вернитесь к A maxDepth его левой ветки ( NULL ) равен 0, maxDepth его правой ветки равно 1. Максимум из них равен 1, и мы должны добавить 1 для самого A , поэтому он 2.

Дело в том, что те же самые шаги должны быть выполнены, когда A является лишь частью большего дерева; результат этого вычисления (2) будет использоваться на более высоких уровнях вызовов maxDepth .

Источник