Найти всех двойников в данном целочисленном бинарном дереве

//Программа формирует дерево из массива целых чисел и выводит его на экран
//root - корень дерева
#include <iostream>
#include <conio.h>
using namespace std;
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);            //вывод дерева на экран
        getch();
        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->right,level+1);          //Перемещение по правым поддеревьям     
                for(int i=0;i<level;i++)cout<<"   ";
                cout<<p->d<<'\n';                      //вывод значений дерева
                  print_tree(p->left,level+1);           //Перемещение по левым поддеревьям
                
     }
}

#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
//Наша структура
struct node
{
    int info; //Информационное поле
    node *l, *r;//Левая и Правая часть дерева
};
 
node * tree=NULL; //Объявляем переменную, тип которой структура Дерево
 
/*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/
void push(int a,node **t)
{
    if ((*t)==NULL) //Если дерева не существует
    {
        (*t)=new node; //Выделяем память
        (*t)->info=a; //Кладем в выделенное место аргумент a
        (*t)->l=(*t)->r=NULL; //Очищаем память для следующего роста
        return; //Заложили семечко, выходим
    }
       //Дерево есть
        if (a>(*t)->info) push(a,&(*t)->r); //Если аргумент а больше чем текущий элемент, кладем его вправо
        else push(a,&(*t)->l); //Иначе кладем его влево
}
 
/*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/
void print (node *t,int u) 
{
    if (t==NULL) return; //Если дерево пустое, то отображать нечего, выходим
    else //Иначе
    {
    print(t->l,++u);//С помощью рекурсивного посещаем левое поддерево
    for (int i=0;i<u;++i) cout<<"|";
    cout<<t->info<<endl; //И показываем элемент
    u--;
    }
    print(t->r,++u); //С помощью рекурсии посещаем правое поддерево
}
 
void main ()
{   
    int n; //Количество элементов
    int s; //Число, передаваемое в дерево
    cout<<"введите количество элементов  ";
    cin>>n; //Вводим количество элементов
 
    for (int i=0;i<n;++i)
    {
    cout<<"введите число  ";
    cin>>s; //Считываем элемент за элементом
   
    push(s,&tree); //И каждый кладем в дерево
    }
    cout<<"ваше дерево\n";
    print(tree,0);
    getch();       
}

#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <clocale>
using namespace std;
//Наша структура
struct node
{
    int d;//элементы дерева
    node *l, *r;//Левая и Правая часть дерева
};
 
void MakeSubTrees(node *leaf)
{
    node *Top;int key;
    cout<<"введите текущий узел";
    cin>>leaf->d;
    cout<<"он имеет левое поддерево?";
    cin>>key;
    if (key==1)
    {
        (Top)=new node;
        leaf->l=Top;
        MakeSubTrees(Top);
    }
    else
        leaf->l=NULL;
    cout<<"он имеет правое поддерево?";
    cin>>key;
    if (key==1)
    {
        (Top)=new node;
        leaf->r=Top;
        MakeSubTrees(Top);
    }
    else
        leaf->r=NULL;
}
 
void MakeTree(node **Top)
{
    (*Top)=new node;
    MakeSubTrees(*Top);
}
 
int High(node *Top)
{ 
    int Highleft,Highright,H;
    if (Top==NULL)
        H=0;
    else
    {
        Highleft=High(Top->l);
        Highright=High(Top->r);
        if (Highleft>Highright)
            H=Highleft+1;
        else
        H=Highright+1;
    }
    return H;
}
void WayHoriz(node *Top,int level)
{
    if (Top!=NULL)
        if (level==1)
            cout<<Top->d;
        else
        {
            WayHoriz(Top->l,level-1);
            WayHoriz(Top->r,level-1);
        }
}
void ViewTree(node Top)
{
    int i,HighTree;
    HighTree=High(&Top);
    for (int i=0;i<HighTree;i++)
    {
        WayHoriz(&Top, i);
    }
}
void main()
{
    setlocale(LC_CTYPE, "Russian");
    node *Top;
    MakeTree(&Top);
    ViewTree(*Top);
    getch();
    return;
}

//назовем пару различных вершин дерева двойниками,если их значения и уровни совпадают.найти 
//всех двойников в данном целочисленном бинарном дереве
#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <clocale>
using namespace std;
 
struct node
{
    int d;//элементы дерева
    node *l, *r;//Левая и Правая часть дерева
};
 
//создание поддерева
void MakeSubTrees(node *leaf)
{
    node *Top;int key;
    cout<<"введите текущий узел"<<endl;
    cin>>leaf->d;
    cout<<leaf->d<<" имеет левое поддерево?"<<endl;
    cin>>key;
    if (key==1)
    {
        (Top)=new node;
        leaf->l=Top;
        MakeSubTrees(Top);
    }
    else
        leaf->l=NULL;
    cout<<leaf->d<<" имеет правое поддерево?"<<endl;
    cin>>key;
    if (key==1)
    {
        (Top)=new node;
        leaf->r=Top;
        MakeSubTrees(Top);
    }
    else
        leaf->r=NULL;
}
 
//создание дерева
void MakeTree(node **Top)
{
    (*Top)=new node;
    MakeSubTrees(*Top);
}
 
void ViewTree(node *Top,int level)
{
    if (Top){
        ViewTree(Top->l,level+1);
        for (int i=0;i<level;i++)
            cout<<"   ";
        cout<<Top->d<<endl;
        ViewTree(Top->r,level+1);
    }
}
 
void main()
{
    setlocale(LC_CTYPE, "Russian");
    node *Top;
    MakeTree(&Top);
    ViewTree(Top,0);
    getch();
    return;
}

void WayUpDown(node *Top)
{ 
    if (Top==NULL)
        return;
    cout<<Top->d;
    WayUpDown(Top->l);
    WayUpDown(Top->r);
}

#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#include <clocale>
using namespace std;
 
struct node
{
    int d;//элементы дерева
    node *l, *r, *p;//Левая и Правая часть дерева
};
 
struct leaf
{
    node* nd;
    int level;
};
 
leaf* plf = NULL;
 
//создание поддерева
void MakeSubTrees(node *leaf)
{
    node *Node;int key;
    cout<<"введите текущий узел"<<endl;
    cin>>leaf->d;
    cout<<leaf->d<<" имеет левое поддерево?"<<endl;
    cin>>key;
    if (key==1)
    {
        (Node)=new node;
        Node->p = leaf;
        leaf->l=Node;
        MakeSubTrees(Node);
    }
    else
        leaf->l=NULL;
    cout<<leaf->d<<" имеет правое поддерево?"<<endl;
    cin>>key;
    if (key==1)
    {
        (Node)=new node;
        Node->p = leaf;
        leaf->r=Node;
        MakeSubTrees(Node);
    }
    else
        leaf->r=NULL;
}
 
//создание дерева
void MakeTree(node **Top)
{
    (*Top)=new node;
    (*Top)->p = NULL;
    MakeSubTrees(*Top);
 
    printf("\n");
}
 
void WayUpDown(node *Top)
{ 
    if (Top==NULL)
        return;
    
    static int n = 0;
    int level = 0; node* tmp = Top;
    while (tmp->p != NULL) 
    {
        tmp = tmp->p;
        level++;
    }
    
    if (plf == NULL)
        plf = (leaf*)malloc(sizeof(leaf) + 4);
 
    plf[n].level = level;
    plf[n++].nd = Top;
 
    plf = (leaf*)realloc(plf,(sizeof(leaf) + 4) * (n + 1));
 
    WayUpDown(Top->l);
    WayUpDown(Top->r);
} 
 
int MaxLevel(leaf* plf)
{
    int max = 0;
    for (int i = 0; plf[i].level >= 0; i++)
        max = (plf[i].level > plf[max].level) ? i : max;
    return (plf[max].level >= 0) ? plf[max].level : -1;
}
 
void Normalize(leaf* plf)
{
    for (int i = 0; plf[i].level >= 0; i++)
    {
        int r = i, count = 0;
        for (int t = 0; plf[t].level >= 0; t++)
            if ((plf[t].level == plf[i].level) && 
                (plf[t].nd->d == plf[i].nd->d) && (i != t))
                count = count + 1;
 
        while(plf[r].level >= 0 && count <= 0)
         { plf[r] = plf[r+1]; r++; }
 
        if (count <= 0) i--;
    }
}
 
void ViewTwins(leaf* plf)
{
    int len = MaxLevel(plf); Normalize(plf);
    for (int level = 0; level <= len; level++)
    {
        cout<<"Уровень ("<<level<<"): ";
        for (int i = 0; plf[i].level >= 0; i++)
            if (plf[i].level == level)
                cout<<plf[i].nd->d<<" ";
 
        cout<<endl;
    }
}
 
void ViewTree(node *Top,int level)
{
    if (Top){
        ViewTree(Top->l,level+1);
        for (int i=0;i<level;i++)
            cout<<"   ";
        cout<<Top->d<<endl;
        ViewTree(Top->r,level+1);
    }
}
 
void main()
{
    setlocale(LC_CTYPE, "Russian");
    node *Top;
    MakeTree(&Top);
    //ViewTree(Top,0);
    WayUpDown(Top);
    ViewTwins(plf);
    _getch();
    return;
}

#include <iostream>
#include <iomanip>
#include <locale.h>
#include <fstream>
using namespace std;
 
struct tree
{
    int info;
    tree *left, *right;
};
 
//Прототипы
tree * MakeTree(int level);                                 //Создает бинарное дерево
tree * MakeTreeAuto(int level, ifstream & in);              //Создает бинарное дерево из файла
void PrintTree(tree * root, int level);                     //Выводит бинарное дерево на экран
void FindClone(tree * root);                                //Находит элементы-двойники
void SearchClone(tree * root, int level, int SearchLevel,   //Поиск двойников по уровням
                    int & TempPosition, int *LevelValues);
int MaxLevel(tree * root, int level);                       //Вычисляет максимальный уровень бинарного дерева
void SrchInArr(int * LevelValues, int TempPosition);        //Поиск двойников по массиву
 
void main()
{
    setlocale(LC_ALL,"Russian");
    tree * root;    //Инициализуем дерево
 
    cout << "1)Ввести новое дерево" << endl;
    cout << "2)Загрузить дерево A" << endl;
    cout << "3)Загрузить дерево B" << endl;
    cout << "4)Загрузить дерево C" << endl;
    int Select;
    cin >> Select;
 
    switch(Select)
    {
    case 1: 
        {
            root = MakeTree(0); //Создаем и заполняем бинарное дерево
            break;
        }
    case 2:
        {
            ifstream in;        //Поток in будем использовать для чтения
            in.open("1.txt");   //Открываем файл для чтения
            root = MakeTreeAuto(0,in);
            break;
        }
    case 3:
        {
            ifstream in;        //Поток in будем использовать для чтения
            in.open("2.txt");   //Открываем файл для чтения
            root = MakeTreeAuto(0,in);
            break;
        }
    case 4:
        {
            ifstream in;        //Поток in будем использовать для чтения
            in.open("3.txt");   //Открываем файл для чтения
            root = MakeTreeAuto(0,in);
            break;
        }
    default: return;    //Если выбор неверный - завершаем программу
    }
 
    cout << "Исходное дерево:" << endl;
    PrintTree(root, 0);
 
    cout << "Максимальный уровень " << MaxLevel(root, 0) << endl;
 
    FindClone(root);
 
    system("pause");
    return;
}
 
//Создает бинарное дерево(из файла)
tree * MakeTreeAuto(int level, ifstream & in)
{
    int c;      //Переменная для хранения текущего значения
    in >> c;    //Считываем из файла число(или переходим на следующее через пробел)
    if (c)      //Если это число не ноль то создаем ветвь
    {
        tree * p = new tree;
        p -> info = c;          //Присваиваем это значение ветви
 
        p -> left = MakeTreeAuto (level + 1, in);   //Создаем правое поддерево
 
        p -> right = MakeTreeAuto (level + 1, in);  //Создаем левое поддерево
 
        return p;
    }
    else
        return NULL;
}
 
//Создает бинарное дерево
tree * MakeTree(int level)
{
    char c;
    cout << setw(4*level) << "" << "Создать вершину? (y/n)" << endl;
    cin >> c;
 
    if (c == 'y')
    {
        tree * p = new tree;
        cout << setw(4*level) << "" << "Введите значение вершины" << endl;
        cin >> p -> info;
 
        cout << setw(4*level) << "" << "Левое поддерево вершины " << p -> info << endl;
        p -> left = MakeTree (level + 1);
 
        cout << setw(4*level) << "" << "Правое поддерево вершины " << p -> info << endl;
        p -> right = MakeTree (level + 1);
 
        return p;
    }
    else
        return NULL;
}
 
//Выводит бинарное дерево на экран
void PrintTree(tree * root, int level)
{
    if (root)
    {
        PrintTree(root -> left,level+1);
        cout <<setw(4*level)<< root -> info << endl;
        PrintTree(root -> right, level+1);
    }
    return;
}
 
//Вычисляет максимальный уровень бинарного дерева
int MaxLevel(tree * root, int level)
{
    if (root)
    {
        int left = MaxLevel(root -> left, level +1);    //Просматриваем левое поддерево
        int right = MaxLevel(root -> right, level +1);  //Просматриваем правое поддерево
        return max(left,right);                         //Возвращаем наибольшее значение уровня
    }
    else
        return level-1;
}
 
//Находит элементы-двойники
void FindClone(tree * root)
{
    if (root)
    {
        for (int i = 0; i <= MaxLevel(root,0); i++) //Проходим циклом от корня дерева до максимального уровня
        {
            int *LevelValues = new int[50]; //Значения текущего уровня(не более 50-ти)
            int TempPosition = 0;           //Текущая позиция в массиве значений
            SearchClone(root, 0, i, TempPosition, LevelValues);
            cout << "Элементы находящиеся на " << i << "-м уровне:" <<endl;
            for(int j = 0; j < TempPosition; j++)
                cout << LevelValues[j]<< " ";
            cout << endl;
            SrchInArr(LevelValues,TempPosition);
        }
    }
    return;
}
 
//Поиск клонов по уровням
void SearchClone(tree * root, int level, int SearchLevel , int & TempPosition, int *LevelValues)
{
    if (root)
    {
        if (level <= SearchLevel)   //Если этот уровень не больше, чем искомый
        {
            if (level == SearchLevel)
            {
                LevelValues[TempPosition] = root -> info;
                //cout << "Нашел элемент " << level << "-го уровня: " << root -> info << endl;  //!!ДЛЯ ОТЛАДКИ!!
                TempPosition ++;
            }
            else
            {
                SearchClone(root->left, level+1, SearchLevel, TempPosition, LevelValues);
                SearchClone(root->right, level+1, SearchLevel, TempPosition, LevelValues);
            }
        }
        else
            return;
    }
    return;
}
 
//Поиск двойников по массиву
void SrchInArr(int * LevelValues, int TempPosition)
{
    bool Check = false; //Наличие двойников
    int Temp;           //Текущий элемент массива
    for (int i = 0; i < TempPosition-1; i++)
    {
        Temp = LevelValues[i];
        for (int j = i+1; j < TempPosition; j++)
            if (Temp == LevelValues[j])
            {
                cout << "Найден двойник: " << Temp << endl;
                Check = true;
            }
    }
    if (!Check)
        cout << "Двойники не найдены" << endl;
 
    return;
}