Построить идеально сбалансированное дерево. Напечатать. Определить высоту дерева.
Code
Бинарное дерево назовается идеально сбалансированным, если для каждой его вершины количество вершин в левом и правом поддереве различаются не более чем на 1.
Алгоритм построения идеально сбалансированного дерева при известном числе вершин n лучше всего формулируется с помощью рекурсии.
При этом необходимо лишь учесть, что для достижения минимальной высоты при заданном числе вершин, нужно располагать
максимально возможное число вершин на всех уровнях, кроме самого нижнего. Это можно сделать очень просто, если распределять
все поступающие в дерево вершины поровну (по возможности) слева и справа от каждой вершины.
Т.о. суть алгоритма следующая:
1) взять одну вершину в качестве корня.
2) построить левое поддерево с nl = n / 2 вершинами тем же способом.
3) построить правое поддерево с nr = n - nl - 1 вершинами тем же способом.
Вывод проще всего тоже организовать рекурсивно.
Причем корень выведем слева, правый подузел сверху, левый снизу
Одновременно с выводом на экран найдем и высоту дерева.
#include<iostream.h>
struct node //структура, описывающая узел
{
int Key; //ключ
node *Left; //указатель на левый узел
node *Right; //на правывй
};
class TREE //класс, описывающий наше дерево
{
private:
node *root; //указатель на корень дерева
int hight; //высота дерева
public:
TREE()
{
root = NULL;//инициализация корня
hight = 0; //высота=0
}
node **GetRoot()
{
return &root;
}
int GetHight()
{
return (hight);
}
node *Tree (int, node **); //построение поддерева, начиная с указанного узла
void TreeOut (node **, int);//вывод на экран, начиная с заданного узла и с заданным уровнем
};
void main ()
{
TREE tr; //класс дерева
int n;
//приглашение на ввод количества узлов
cout<<"Enter nodes count = ";
//введем число узлов
cin>>n;
//приглашение на ввод ключей
cout<<"Enter keys..."<<endl;
//вводим ключи и одновременно строим дерево
//параметры - число узлов и корневой узел
tr.Tree (n,tr.GetRoot());
//выводим на экран дерево
//параметры - корневой узел и уровень вывода 0
tr.TreeOut (tr.GetRoot(),0);
//выводим высоту дерева
cout<<endl<<"Tree hight = "<<tr.GetHight()<<endl;
}
//Построение идеально сбалансированного
// дерева с n вершинами.
// *pNode - указатель на узел, к которому добавляем подуровни
node *TREE::Tree (int n,node **pNode)
{
node *curr; //указатель на текущий узел
int x; //переменная для ввода очередного ключа
int nl; //число узлов левого поддерева
int nr; //число узлов правого поддерева
if (n==0) //если поддеревьев нет,
*pNode = NULL; // то обнуляем адрес "родителя" (выход из рекурсии)
else
{
nl = n/2; //пусть число узлов слева равно половине
nr = n - nl - 1;//оставшиеся будут справа
cin>>x; //вводим ключ
curr = new(node); //создаем узел
(*curr).Key = x; //сохраняем введенный ключ
//строим рекурсивно левое поддерево
Tree (nl,&((*curr).Left));
//строим рекурсивно правое поддерево
Tree (nr,&((*curr).Right));
*pNode = curr; //сохраним адрес созданного узла
}
return (*pNode); //функция должна вернуть node
}
//Изображение бинарного дерева, заданного указателем *pNode на экране дисплея.
//level - уровень узла. Необходим для вывода соотвествующего количества пробелов
//для удобства корень выведем слева, левый узел ниже, правый - выше
//выводим рекурсивно
//одновременно вычисляем высоту дерева, как максимальный уровень подузла
void TREE::TreeOut (node **pNode, int level)
{
if (level > hight) //вычисляем высоту, как максимальный уровень узла
hight = level;
if (*pNode!=NULL) //выводим, пока есть поддеревья
{
//выводим правое поддерево
TreeOut (&((**pNode).Right),level+1);
//выведем соответствующее уровню количество пробелов
for (int i=1; i<=level; i++)
cout<<" ";
cout<<(**pNode).Key<<endl; //ключ узла
//ниже выводем левое поддерево
TreeOut (&((**pNode).Left),level+1);
}
}