В общем у меня есть двоичное дерево поиска с включением, сделаны функции создания узла\дерева, поиска, и обхода. никак не получается дописать следующее: 1)поменять тип данных на строку символов 2)сделать функцию нахождения в дереве узла с заданным значением ключевого признака 3)сделать функцию определения максимальной глубины дерева 4)сделать функцию определения кол-ва узлов и листьев дерева 5)обход дерева слева направо - левое поддерево,корень, правое поддерево.(у меня как-то не верно работает). Помогите пожалуйста, горит(( Код |
//Программа формирует дерево из массива целых чисел и выводит его на экран //root - корень дерева
#include <iostream.h>
struct Node{ int d; //Данные элемента Node *left; //Ссылка на левое поддерево Node *right; //Ссылка на правое поддерево };
Node *first(int d); //Формирование первого элемента Node *search_insert(Node *root,int d); //Поиск с включением void print_tree(Node *root,int l); //Обход дерева //-------------------------------------------
int main() { int b[]={10,25,20,6,21,8,1,30}; Node *root=first(b[0]); //Формируем корень дерева //Ищем место куда вставить и вставляем новые элементы for(int i=1;i<8;i++)search_insert(root,b[i]); print_tree(root,0); //вывод дерева на экран return 0; } //--------------------------------------------
//Формирование первого элемента
Node *first(int d){ Node *pv =new Node; //Создаём элемент pv->d=d; //Присваиваем значение элементу поля pv->left=0; //Ссылка на левое поддерево равна NULL pv->right=0; //Ссылка на правое поддерево равна NULL return pv; //Возвращаем адрес элемента } //---------------------------------------------
//Поиск с включением Node *search_insert(Node *root,int d){ Node*pv=root,*prev; bool found = false; //Переменная отвечающая за то что нашли ли элемент или нет /*Ниже приведён алгоритм поиска короче если нашли такой же элемент то мы его не вставляем в дерево выходим из функции возвратив адрес совпавшего элемента*/ while(pv&&!found){ prev=pv; //получаем адрес элемента от которого будем пускать корни if(d==pv->d)found=true; //совпадение выходим из цикла else if(d<pv->d)pv=pv->left; //Всовываемя в левое поддерево else pv=pv->right; //Всовываемя в правое поддерево //Выход из цикла осуществляется, тогда когда нашли свободный адрес : ссылку у дерева : для вставки нового узла */ } //--------------------------- /*Если совпало значение элемента со значением элемента который хотим вставить то выходим из функции возвращая адрес элемента с которым совпало */ if(found)return pv; //Создание нового узла Node *pnew =new Node; pnew->d=d; pnew->left=0; pnew->right=0; if(d<prev->d) //Присоединение к левому поддереву предка prev->left=pnew; else //присоединяем к правому поддереву предка prev->right=pnew; return pnew; } //--------------------------------------- //Обход дерева void print_tree(Node *p,int level){ if(p){ print_tree(p->left,level+1); //Перемещение по левым поддеревьям for(int i=0;i<level;i++)cout<<" "; cout<<p->d<<'\n'; //вывод значений дерева print_tree(p->right,level+1); //Перемещение по правым поддеревьям } }
|
|