Рекурсия: найти максимальный элемент в дереве
Нужно найти максимальный элемент в дереве, используя рекурсию. Вот сама функция. Подскажите, пожалуйста, почему не рабит.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
function FoundInTree(Tree: P_Node): integer; var t: P_Node; max:integer; begin t:= Tree; if t = nil then ShowMessage('Дерево пустое') else begin max:=t^.key; if max^.right.key then max:=FoundInTree(t^.right) else if max^.left.key then max:=FoundInTree(t^.left) end; FoundInTree:=max; end;
Найти максимальный элемент в двоичном дереве
Помогите решить задачку:найти максимальный элемент в двоичном дереве. Шаблон уже есть ,мне нужно.
Найти максимальный элемент в бинарном дереве
тип информационного поля int*, найти маскимальный элемент в дереве. (помогите, пожалуйста, нужен.
Найти в бинарном дереве максимальный элемент и количество его повторений
Найти максимальный элемент бинарного дерева и количество повторений максимального элемента в данном.
Найти максимальный элемент бинарного дерева и количество повторений максимального элемента в данном дереве
Здравствуйте. Дано задание : Найти максимальный элемент бинарного дерева и количество повторений.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
function FoundInTree(Tree: P_Node, max: integer): integer; var t: P_Node; begin t:= Tree; if t = nil then ShowMessage('Дерево пустое') else begin if max^.right.key then max:=FoundInTree(t^.right, max) else if max^.left.key then max:=FoundInTree(t^.left, max) end; FoundInTree:=max; end;
Попробуйте. Только при вызове во втором параметре пропишите an^.key или как там у вас корень обозначен.
В окне ошибок пишет ‘max’ might not have been initialized и указывает на строку
if max
а вылетает с ошибкой класса EAccessViolation.
такие же ошибки кстати и в моем варианте выскакивали.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
function FoundInTree(Tree: P_Node; max: integer): integer; var t: P_Node; begin t:= Tree; if t = nil then ShowMessage('Дерево пустое') else begin if max^.right.key then max:=FoundInTree(t^.right, max) else if max^.left.key then max:=FoundInTree(t^.left, max) end; FoundInTree:=max; end;
можно всю программу? желательно в архиве.
а то так не очень удобно. даже самой интересно стало, что там не так.
а это бинарное дерево? ну т.е. элементы там упорядочены — слева те, что меньше, а справа те, что больше?
Если Вы не проверяете существание объекта перед обращением к его члену, то и получаете исключение. Не забывайте, что элементы right и left в вашей структуре — это не объекты, а просто указатели на адрес в памяти, где должен располагаться настоящая структура с данными, поэтому при обращении к left^.key (у Вас, кстати «птички» везде пропущены) необходимо убедиться в том, что объект «left» существует
Короче, Ваш модуль может выглядеть примерно так:
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
unit Unit1; interface uses Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls; type TForm1 = class(TForm) ButtonFillTree: TButton; Memo1: TMemo; ButtonFind: TButton; Edit1: TEdit; Label1: TLabel; procedure ButtonFillTreeClick(Sender: TObject); procedure ButtonFindClick(Sender: TObject); procedure FormClose(Sender: TObject; var Action: TCloseAction); private public end; var Form1: TForm1; implementation type T_item = Integer; P_Node = ^T_Node; T_Node = record info: T_item; key: Integer; left, right: P_Node; end; var root: P_node; // вставка элемента в дерево procedure InsertInTree(var t: P_Node; k: Integer); begin if t = nil then begin // если найдено место для нового узла New(t); with t^ do begin left := nil; right := nil; key := k; end; end else if k = t^.key then InsertInTree(t^.left, k) else InsertInTree(t^.right, k); end; procedure ClearTree(var t: P_Node); begin if t^.left <> nil then ClearTree(t^.left); if t^.right <> nil then ClearTree(t^.right); Dispose(t); t := nil; end; procedure TForm1.ButtonFillTreeClick(Sender: TObject); var i,n,k: Integer; begin Memo1.Lines.Clear; //root := nil; Edit1.Text := Trim(Edit1.Text); if Edit1.Text = '' then ShowMessage('Введите размер') else begin if root <> nil then ClearTree(root); n := StrToInt(Edit1.Text); Randomize; for i := 1 to n do begin k := Random(50); Memo1.Lines.Add(Format('%d', [k])); InsertInTree(root, k); end; end; end; function FindMaxInTree(Tree: P_Node): P_Node; begin if (Tree^.right <> nil) then //and (Tree^.key < Tree^.right^.key) проверять излишне - справа только элементы с бОльшим ключомResult := FindMaxInTree(Tree^.right) else Result := Tree; end; procedure TForm1.ButtonFindClick(Sender: TObject); var max: P_Node; begin if root <> nil then begin max := FindMaxInTree(root); ShowMessage(Format('max=%d', [max^.key])); end; end; procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction); begin if root <> nil then ClearTree(root); end;
Источник
Найти максимальный элемент дерева
Здравствуйте. Помогите, пожалуйста, найти максимальный элемент в данной программе. Тут выводится несколько «узлов», т.е. дерево с помощью структуры и рекурсивной функции. Заранее спасибо.
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
#include #include struct treenode { int val; treenode* left; treenode* right; treenode(int a_val, treenode* a_left, treenode* a_right):val(a_val), left(a_left), right(a_right) { } }; void print(treenode* node, int node_count) { if (node != nullptr) { int counter = 0; while (counter node_count) { putchar(' '); counter++; } printf("%d\n", (*node).val); print((*node).left, node_count + 1); print((*node).right, node_count + 1); } } int main() { treenode* root = new treenode(2, new treenode(3, new treenode(10, new treenode(9, nullptr, nullptr), nullptr), new treenode(7, nullptr, nullptr)), new treenode(4, new treenode(8, nullptr, nullptr), new treenode(7, nullptr, nullptr))); print(root, 0); getchar(); } Источник
Поиск максимального элемента дерева
Найти максимальный элемент бинарного дерева и количество повторений максимального элемента в данном дереве
Здравствуйте. Дано задание : Найти максимальный элемент бинарного дерева и количество повторений.
Поиск максимального элемента
Нужна сделать поиск максимального элемента массива путем деления пополам не через рекурсию, а через.
Поиск максимального элемента массива
Всем вечер добрый Вот моя ситуация: дано два одномерных массива А и Б допустим как мне найти .
Поиск максимального элемента в файле
Доброго времеи суток. Не подскажие, как осуществить поиск максимального элемета из записаных в.
Сообщение было отмечено Oksik_ как решение
Решение
Что-то в этом коде мне не особо понятно. Может хотя бы скажете на какие номера строк нужно смотреть.
У меня есть код реализующий поиск по минимальному элементу. Аналогичным образом попыталась сделать поиск и по максимальному элементу, но не получилось.
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 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177
#include #include #include #include #include #include #include #include #include using namespace std; struct Node { int key; // полезные данные (ключ) Node *left, *right; // указатели на сыновей }; typedef Node *PNode; // указатель на вершину PNode MakeTree (int data[], int from, int n) { PNode Tree; int n1, n2; if ( n == 0 ) return NULL; // ограничение рекурсии Tree = new Node; // выделить память под вершину Tree->key = data[from]; // записать данные (ключ) n1 = n / 2; // размеры поддеревьев n2 = n - n1 - 1; Tree->left = MakeTree(data, from+1, n1); Tree->right = MakeTree(data, from+1+n1, n2); return Tree; } void PrintLKP(PNode Tree) { if ( ! Tree ) return; // пустое дерево - окончание рекурсии PrintLKP(Tree->left); // обход левого поддерева printf("%d ", Tree->key); // вывод информации о корне PrintLKP(Tree->right); // обход правого поддерева } void PrintKLP (PNode Tree) { if ( ! Tree ) return; // пустое дерево - окончание рекурсии printf("%d ", Tree->key); // вывод информации о корне PrintKLP(Tree->left); // обход левого поддерева PrintKLP(Tree->right); // обход правого поддерева } void PrintLPK (PNode Tree) { if ( ! Tree ) return; // пустое дерево - окончание рекурсии } void AddToTree (PNode &Tree, int data) // указатель на корень (ссылка) { if ( ! Tree ) { Tree = new Node; //создать новый узел Tree->key = data; Tree->left = NULL; Tree->right = NULL; return; } if ( data Tree->key ) // добавить в нужное поддерево AddToTree ( Tree->left, data ); else AddToTree ( Tree->right, data ); } int min (PNode &Tree) { if (!Tree->left)return Tree->key; Tree=Tree->left; int a=min(Tree); } int max (PNode &Tree) { if (!Tree->right)return Tree->key; Tree=Tree->right; int a=max(Tree); } PNode Search (PNode Tree, int what) { if ( ! Tree ) return NULL; // ключ не найден if ( what == Tree->key ) return Tree; // ключ найден if ( what Tree->key ) // искать в поддеревьях return Search ( Tree->left, what ); else return Search ( Tree->right, what ); } int main() { int n, i; int data[] = { 21, 8, 9, 11, 15, 19, 20, 21, 7 }; PNode Tree; // указатель на корень дерева n = sizeof(data) / sizeof(int); // размер массива Tree = MakeTree (data, 0, n); // использовать n элементов // начиная с номера 0 PrintLKP(Tree); cout <"\n"; PrintKLP(Tree); cout <"\n"; PrintLPK(Tree); cout <"\n"; PNode TreeSearch=0; for (i=0;in;i++) AddToTree(TreeSearch, data[i]); PrintLKP(TreeSearch); cout <"\n"; cout ( TreeSearch); cout <"\n"; cout ( TreeSearch); } PrintLPK(Tree->left); // обход левого поддерева PrintLPK(Tree->right); // обход правого поддерева printf("%d ", Tree->key); // вывод информации о корне } void AddToTree (PNode &Tree, int data) // указатель на корень (ссылка) { if ( ! Tree ) { Tree = new Node; //создать новый узел Tree->key = data; Tree->left = NULL; Tree->right = NULL; return; } if ( data Tree->key ) // добавить в нужное поддерево AddToTree ( Tree->left, data ); else AddToTree ( Tree->right, data ); } int min (PNode &Tree) { if (!Tree->left)return Tree->key; Tree=Tree->left; int a=min(Tree); } int max (PNode &Tree) { if (!Tree->right)return Tree->key; Tree=Tree->right; int a=max(Tree); } PNode Search (PNode Tree, int what) { if ( ! Tree ) return NULL; // ключ не найден if ( what == Tree->key ) return Tree; // ключ найден if ( what Tree->key ) // искать в поддеревьях return Search ( Tree->left, what ); else return Search ( Tree->right, what ); } int main() { int n, i; int data[] = { 21, 8, 9, 11, 15, 19, 20, 21, 7 }; PNode Tree; // указатель на корень дерева n = sizeof(data) / sizeof(int); // размер массива Tree = MakeTree (data, 0, n); // использовать n элементов // начиная с номера 0 PrintLKP(Tree); cout <"\n"; PrintKLP(Tree); cout <"\n"; PrintLPK(Tree); cout <"\n"; PNode TreeSearch=0; for (i=0;in;i++) AddToTree(TreeSearch, data[i]); PrintLKP(TreeSearch); cout <"\n"; cout ( TreeSearch); cout <"\n"; cout ( TreeSearch); } Источник