Нахождение высоты бинарного дерева

Найдите высоту бинарного дерева, представленного родительским массивом

Учитывая массив, представляющий отношения родитель-потомок в двоичном дереве, найдите высоту дерева, не строя его. Отношения между родителями и детьми определяются (A[i], i) для каждого индекса i в массиве A . Значение корневого узла будет i если -1 присутствует в индексе i в массиве.

Глубина “узла” — это общее количество ребер от узла до корневого узла дерева. Корень — это единственный узел, глубина которого равна 0.

Высота “узла” — это общее количество ребер на самом длинном пути от узла до листа. Высота “дерева” будет высотой его корневого узла или, что то же самое, глубиной его самого глубокого узла. Листовой узел будет иметь высоту 0.

• -1 присутствует в индексе 0, что означает, что корень бинарного дерева является узлом 0.
• 0 присутствует в индексах 1 и 2, что означает, что левый и правый потомки узла 0 — это 1 и 2.
• 1 присутствует в индексе 3, что означает, что левый или правый дочерний элемент узла 1 равен 3.
• 2 присутствует в индексах 4 и 5, что означает, что левый и правый потомки узла 2 — это 4 и 5.
• 4 присутствует в индексах 6 и 7, что означает, что левый и правый потомки узла 4 — это 6 и 7.

Соответствующее бинарное дерево:

Связанный пост:

Простым решением было бы построить двоичное дерево с использованием родительского массива, как показано в сообщении выше. После того, как дерево построено, рассчитайте его высоту. Временная сложность приведенного выше решения равна O(n) и требует O(n) дополнительное пространство, где n размер родительского массива. Однако, согласно ограничениям задачи, высота должна рассчитываться без построения дерева.

Идея состоит в том, чтобы вычислить глубину каждого узла, используя рекурсия и вернуть максимальную найденную глубину. Поскольку глубина узла — это общее количество ребер от узла к корню, нам нужно проследить путь узла к корневому узлу, используя отношение родитель-потомок. Мы можем сделать это, рекурсивно обходя родительский массив. Алгоритм может быть реализован следующим образом на C, Java и Python:

C

результат:

The height of the binary tree is 3

Java

результат:

The height of the binary tree is 3

Python

результат:

The height of the binary tree is 3

Временная сложность приведенного выше решения равна O(n 2 ) , куда n это общее количество узлов в бинарном дереве. Вспомогательное пространство, необходимое программе, равно O(h) для стека вызовов, где h это высота дерева.

Обратите внимание, что findDepth() рутина имеет оптимальное основание поскольку его можно рекурсивно разбить на более мелкие подпрограммы, т.е. findDepth(i) = 1 + findDepth(parent[i]) . Он также демонстрирует перекрывающиеся подзадачи так как одна и та же подзадача решается снова и снова.

Мы знаем, что задачи, имеющие оптимальную подструктуру и перекрывающиеся подзадачи, могут быть решены с помощью динамического программирования. Ниже приведена реализация динамического программирования на C, Java и Python, где решения подзадач памятка, а не вычисляется повторно. Решение использует вспомогательный массив для хранения глубины каждого узла.

Источник

Высота двоичного дерева в C/C++

Высота бинарного дерева определяется как максимальная глубина любого конечного узла от корневого узла. То есть это длина самого длинного пути от корневого узла до любого конечного узла.

Давайте рассмотрим приведенное ниже двоичное дерево.

Поскольку листовые узлы, соответствующие максимальной глубине, равны 40 и 50, чтобы найти высоту, мы просто находим количество ребер от корневого узла до любого из этих двух узлов, что равно 3.

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

Логика для нахождения высоты двоичного дерева в C++

Давайте теперь решим логику определения высоты и сначала напишем наш псевдокод.

Мы будем использовать рекурсию по дереву, чтобы найти высоту. (Концепции см. в статье Википедии)

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

Теперь мы можем применить определение высоты к поддеревьям.

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

Поскольку высота дерева равна максимальной высоте поддерева + 1, мы продолжаем делать это, пока поддерево не станет NULL , а его высота равна 0.

В этот момент наша функция окончательно завершится, и

Давайте напишем функцию tree_height() , которая вычисляет высоту.

// Find height of a tree, defined by the root node int tree_height(Node* root) < if (root == NULL) return 0; else < // Find the height of left, right subtrees left_height = tree_height(root->left); right_height = tree_height(root->right); // Find max(subtree_height) + 1 to get the height of the tree return max(left_height, right_height) + 1; > 

Строка №3 оценивает условие завершения, когда размер поддерева равен 0 или когда корневой узел имеет значение NULL .

Строки 7 и 8 рекурсивно находят высоту левого и правого поддеревьев.

И, наконец, строка 11 возвращает максимальное значение из двух, возвращая высоту дерева.

Реализация на С/С++

Ниже приведена полная программа, показывающая, как строится двоичное дерево, а затем показана логика определения высоты в tree_height() .

#include #include typedef struct Node Node; // Define the Tree Node here struct Node < int value; // Pointers to the left and right children Node* left, *right; >; Node* init_tree(int data) < // Creates the tree and returns the // root node Node* root = (Node*) malloc (sizeof(Node)); root->left = root->right = NULL; root->value = data; return root; > Node* create_node(int data) < // Creates a new node Node* node = (Node*) malloc (sizeof(Node)); node->value = data; node->left = node->right = NULL; return node; > void free_tree(Node* root) < // Deallocates memory corresponding // to every node in the tree. Node* temp = root; if (!temp) return; free_tree(temp->left); free_tree(temp->right); if (!temp->left && !temp->right) < free(temp); return; >> int tree_height(Node* root) < // Get the height of the tree if (!root) return 0; else < // Find the height of both subtrees // and use the larger one int left_height = tree_height(root->left); int right_height = tree_height(root->right); if (left_height >= right_height) return left_height + 1; else return right_height + 1; > > int main() < // Program to demonstrate finding the height of a Binary Tree // Create the root node having a value of 10 Node* root = init_tree(10); // Insert nodes onto the tree root->left = create_node(20); root->right = create_node(30); root->left->left = create_node(40); root->left->right = create_node(50); // Find the height of the tree int height = tree_height(root); printf("Height of the Binary Tree: %d\n", height); // Free the tree! free_tree(root); return 0; > 

Все права защищены. © Linux-Console.net • 2019-2023

Источник

Вычисление высоты бинарного дерева поиска на С++

Никак не могу вывести нормально высоту дерева, уже второй день маюсь, подскажите пожалуйста, в чем проблема ?
Например : Высоту бинарного дерева с узлами f, e, a, c, d, f, b Выводит : 2, Хотя должно вывести : 5

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

#include "stdafx.h" #include #include #include using namespace std; struct Node { Node *l,*r; char x; }; void add(char x,Node *&MyTree) { if (NULL==MyTree) { MyTree=new Node; MyTree->x=x; MyTree->l=MyTree->r=NULL; } else { if (xMyTree->x) //Если нововведенный элемент x меньше чем элемент x из семечка дерева, уходим влево { if (MyTree->l!=NULL) add(x,MyTree->l); else { MyTree->l=new Node; MyTree->l->l=MyTree->l->r=NULL; MyTree->l->x=x; } } if (x>=MyTree->x) //Если нововведенный элемент x больше чем элемент x из семечка дерева, уходим вправо { if (MyTree->r!=NULL) add(x,MyTree->r); else { MyTree->r=new Node; MyTree->r->l=MyTree->r->r=NULL; MyTree->r->x=x; } } } } //Обход в инфиксном порядке void Show(Node *&tree) { if (NULL==tree) return; Show(tree->l); cout->x; Show(tree->r); } /*void Show(Node *&tree) // Обход в прямом порядке   if (NULL==tree) return; //Если дерева нет, выходим coutx  Show(tree->l); //Обошли левое поддерево Show(tree->r); //Обошли правое поддерево >*/ int lookup(Node *&tree) { int h1=0,h2=0; if (NULL==tree) {return 0; } if(tree->l){h1=lookup(tree->l);} if(tree->r){h1=lookup(tree->r);} return(max(h1,h2)+1); } void main() { setlocale(LC_ALL,"Russian"); int n,how_much; char x; Node *MyTree=NULL; cout  <"Сколько узлов будет в дереве ? (Введите кол-во узлов (min : 2))"  ; for(int menu=0;menu==0;) { cin >> n; if(n>1) {menu++;} else {cout  <"Введено неправильное кол-во узлов. Попробуйте еще."  ;} } for (int i=0;in;i++) { cout<"Vvedite element #" +1  <" : "; cin>>x; add(x,MyTree); } Show(MyTree); // Простой обход how_much=lookup(MyTree); cout  <" Высота данного бинарного дерева : "   ; getch (); }

Источник