Сайт студентов ИАТЭ специальности ИС

#include <iostream.h>
#include <conio.h>
#include <limits.h> [color=gray][i]// Библиотека необходимая для работы переменной INT_MAX[/i][/color]

struct node{
int key;
node *left, *right;
};
node*buildTree (int n)
{if (n==0)return 0;
else
{node *t=new node;
cout<<"\n Vvedite ocherednoe chislo \n";
cin>>t->key;
int nl = n/2, nr = n-1 -nl;
t->left=buildTree (nl);
t->right=buildTree (nr);
return t;
}
}
void output (node *t, int k) [color=gray][i]// Описание функции вывода[/i][/color]
{if (t!=0)
{output(t->right, k+5); [color=gray][i]// k+5 - расстояние между узлами[/i][/color]
for (int i=0; i<k; i++)
cout<<' ';
cout<<t->key<<"\n \n";
output (t->left, k+5);
}
}
int summa (node *t) [color=gray][i]// Функция нахождения суммы отрицательных элементов[/i][/color]
{int s;
if (t==0) return 0;
else
{if (t->key<0) [color=gray][i]// Если заменить (t->key<0) на (t->key>0), то будет поиск суммы положительных элементов[/i][/color]
s=t->key; else==0;
return (s+summa (t->left) + summa (t->right));
}
}
int kol (node *t) [color=gray][i]// Функция нахождения количества отрицательных элементов[/i][/color]
{int kl;
if (t==0) return 0;
else
{if(t->key<0)kl=1; else kl=0;
return (kl+kol(t->left)+kol(t->right));
}
}
int max (node *t) [color=gray][i]// Функция нахождения максимального элемента[/i][/color]
{int b,r;
if (t==0) return -INT_MAX;
else
{b=max(t->left);
if(t->key>b)b=t->key;
r=max(t->right);
if(r>b)b=r;
return b;
}
}
void main ()
{int n;
clrscr;
cout<<"\n Vvedite n \n";
cin>>n;
node *T=buildTree (n);
cout<<"\n Ishodnoe derevo \n"; [color=gray][i]//Вывод исходного дерева с суммой[/i][/color]
output (T,1);
int s=summa (T);
cout<<"\n Kolvo otricatelnih = "<<kl<<endl; [color=gray][i]// Вывод количества отрицательных элементов[/i][/color]
int maximum = max (T);
cout<<"\n maximalnii element = "<<maximum<<endl; [color=gray][i]// Вывод максимального элемента[/i][/color]
getch ();
}

Бинарное дерево назовается идеально сбалансированным, если для каждой его вершины количество вершин в левом и правом поддереве различаются не более чем на 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);
   }
}