Максимальная глубина двоичного дерева
Для данного двоичного дерева найдите его максимальную глубину.
Максимальная глубина — это количество узлов на самом длинном пути от корневого узла до самого дальнего листового узла.
Для данного двоичного дерева [3,9,20, null, null, 15,7],
- Чтобы найти максимальную глубину двоичного дерева в целом, в каждом узле необходимо определить, какое из его левого и правого поддеревьев имеет большую глубину. Эта ситуация представляет собой идеальный случай для рекурсии.
- Когда дело доходит до рекурсии, определение базовых условий имеет первостепенное значение. В этой задаче один интуитивно понятный базовый случай — это достижение конечного узла. Другой базовый случай может быть, когда проверяемый узел равен нулю.
- Если узел равен нулю, то его глубина равна 0. Если это листовой узел, то его глубина (с учетом самого себя) равна 1. В противном случае, чтобы определить, какое из двух поддеревьев имеет большую глубину, мы рекурсивно вычисляем максимальная глубина левого и правого дочерних элементов и возвращает сумму 1 (для учета самого себя) и большую глубину поддерева.
- Корневой узел / дерево пустое.
- Деревья с перекосом влево / вправо.
- Дерево с одинаково глубокими левыми и правыми поддеревьями.
- Дерево, у которого одно поддерево глубже другого.
Анализ сложности:
Поскольку для вычисления глубины мы в конечном итоге посещаем каждый узел рекурсивно, поэтому временная сложность равна T O (n). Сложность пространства равна O (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 минуты
ребят, ну помогите кто нибудь, завтра сдавать, а в голове чёт пока ни одной идеи! =(
Источник
Нахождение глубины бинарного дерева
У меня возникли проблемы с пониманием этого 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 .
Источник
Сформировать бинарное дерево поиска и определить максимальную глубину дерева
Добрый день всем.
По задаче необходимо сформировать бинарное дерево поиска и определить максимальную глубину дерева.
Перед завершением программы освободить память.
Оно у меня явно не правильно работает
И не пойму как для него функцию удаления элементов написать
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
#include #include using namespace std; //Наша структура struct node { int info; //Информационное поле node *l, *r;//Левая и Правая часть дерева }; node * tree=NULL; //Объявляем переменную, тип которой структура Дерево /*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/ void push(int a,node **t) { if ((*t)==NULL) //Если дерева не существует { (*t)=new node; //Выделяем память (*t)->info=a; //Кладем в выделенное место аргумент a (*t)->l=(*t)->r=NULL; //Очищаем память для следующего роста return; //Заложили семечко, выходим } //Дерево есть if (a>(*t)->info) push(a,&(*t)->r); //Если аргумент а больше чем текущий элемент, кладем его вправо else push(a,&(*t)->l); //Иначе кладем его влево } /*ФУНКЦИЯ УДАЛЕНИЯ ЭЛЕМЕНТОВ ДЕРЕВA*/ void delete_node(){ if (t==NULL) return; //Если дерево пустое, то удалять нечего, выходим else //Иначе { //найти максимальный элемент } } /*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/ void print (node *t,int u) if (t==NULL) return; //Если дерево пустое, то отображать нечего, выходим else //Иначе { print(t->l,++u);//С помощью рекурсивного посещаем левое поддерево for (int i=0;iu;++i) cout<" print(t->r,++u); //С помощью рекурсии посещаем правое поддерево } /*Функция поиска максимального элемента*/ int getMaxDepth(node* tree, int depth) { if (tree == NULL) return depth; return max(getMaxDepth(tree->l, depth + 1), getMaxDepth(tree->r, depth + 1)); } int main(int argc, char *argv[]) { int n; //Количество элементов int s; //Число, передаваемое в дерево cout<"Vvod kol-vo elementov "; cin>>n; //Вводим количество элементов for (int i=0;in;++i) { cout<"Enter Digit:"; cin>>s; //Считываем элемент за элементом push(s,&tree); //И каждый кладем в дерево } cout<"Node\n"; print(tree,0); cout <"Max = "( tree, 0); getch(); return 0; } Бинарное дерево поиска (определить максимальную глубину)
Всем привет! Делаю лабу, написал основу, но не могу понять, как сделать последний пункт задания.
Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при.
Бинарное дерево поиска — улучшение «визуализации» дерева
Здравствуйте, есть программа, формирующая выводящая на экран бинарное дерево поиска, значения.
Рекурсия: определить, помещена ли строка в бинарное дерево поиска
Помогите пожалуйста исправить ошибку. Задание:"Разработать рекурсивную функцию, которая определяет.
Ирина197708, страшное сишное бинарное дерево, на С++ проще можно описать. Бог помощь.
Добавлено через 3 минуты
по мне так БДП самое простое из деревьев
Источник