//Программа формирует дерево из массива целых чисел и выводит его на экран
//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);
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); //Перемещение по правым поддеревьям
}
}
бинарное дерево С++
1)поменять тип данных на строку символов
2)сделать функцию нахождения в дереве узла с заданным значением ключевого признака
3)сделать функцию определения максимальной глубины дерева
4)сделать функцию определения кол-ва узлов и листьев дерева
5)обход дерева слева направо - левое поддерево,корень, правое поддерево.(у меня как-то не верно работает).
Помогите пожалуйста, горит((
Код:
Вот программа на С# - бинарное дерево с обходом в ширину, может кому пригодится..
http://www.fulcrumweb.com.ua/archives/2401