Дерево общего вида - C++

#include "stdafx.h"
#include <iostream>
 
using namespace std;
 
// Описание дерева
struct Info
{
    int Key;
    
};
// Создание дерева
 
struct Node
{
    Info data;
    Node *son;
    Node *brother;
};
 
Node *top=NULL;
Info *RetInfo = NULL, *DelInfo = NULL;
 
// Добавление элемента в дерево
Node *Add(Node *&top, int Key, int AddKey)
{
    
        top = new Node;
        top -> data.Key = Key;
        top -> brother = NULL;
        Node *p1 = top->son, *p2 =top->brother;
    
        if(p1==NULL)
        {
            p1=p2;
            p2=NULL;
        }
        top->son=Add(p1, Key, AddKey); 
        if(p1!=NULL)
            top->son->brother=Add(p2, Key, AddKey);
        return top;
    
}
//Вывод дерева на экран
void Display(Node *top, int lvl)
{
    lvl++;
    if(top==NULL) return;
    if(top!=NULL)
    {
        Display(top -> son,lvl);
        for(int i=1;i<=lvl*2;i++) cout << "  ";
        cout<<top->data.Key<<endl;
        //top=top->son;
        Display(top -> brother,lvl);
    }
    
}
 
// Поиск элемента в дереве
Info *Search(Node *&top, int SearchKey)
{
 
    if(top == NULL) return RetInfo;
    if(top -> data.Key == SearchKey) RetInfo = &(top -> data);
    else RetInfo = Search((top -> son), SearchKey);
    return RetInfo;
}
 
// Главная функция
void main()
{
    setlocale(LC_ALL,"Russian");
    
    int otv, SearchKey, lvl, Key, AddKey;
    do
    {
        cout << "Возможные действия:" << endl
            << "1. Добавить узел в дерево" << endl
            << "2. Вывести дерево на экран" << endl
            << "3. Поиск узла в дереве" << endl
            << "0. Выход" << endl
            << "Ваш выбор:";
        cin >> otv;
        cout << endl;
        system("cls");
        switch(otv)
        {
        case 1:
            cout << "Добавить узел:";
            cin >> Key;
            
            cin >> AddKey;
            cout << endl;
            Add(top, Key, AddKey);
            cout << "Узел добавлен." << endl << endl;
            break;
        case 2:
            if(top==NULL) cout << " Дерево пустое." << endl;
            else 
            {
            cout << "Содержимое дерева: " << endl;
            lvl=0;
            Display(top,lvl);
            }
            cout << endl << endl;
            break;
        case 3:
 
            if(top==NULL) cout << " Дерево пустое." << endl;
            else
            {
                cout << "Найти узел:";
                cin >> SearchKey;
                cout << endl;
                RetInfo = Search(top, SearchKey);
                if(RetInfo == NULL)
                    cout << "Элемент не найден." << endl;
                else
                    cout << "Элемент найден." << top -> data.Key << endl;
                RetInfo=NULL;
            }
            break;
        
        case 0:
            otv = 0;
            break;
        default:
            cout << "Недопустимое значение" << endl << endl;
            break;
        }
    }
    while(otv != 0);
}

#include "stdafx.h"
#include <conio.h>
#include <iostream>
 
using namespace  std;
 
struct Node;
 
struct List{
    List *next;//след. ссылка
    Node *node;//ссылка
};
struct Node{
    int s; //cимвол
    List *list;//ссылка на список
};
 
List *MakeSomeList();
Node *Add(int s, Node *root, int &f);
List *FindEmptyPointer(Node *root, List *&Empty);//поиск "пустого" указателя
void Search(Node *&root,int s, int i);//поиск символа в дереве
void Search(Node *&root,int s, int i)
{
    if(root -> s == s)
    {
        i ++;
        cout<<i;
    }
 
    if(root -> list -> node != NULL)
        return Search(root -> list -> node, s, i);
 
    if(root -> list -> next != NULL)
        return Search(root -> list -> next -> node, s, i);
 
}
 
void Display(Node *root, int lvl)
{
    lvl++;
    if(root==NULL) return;
    if(root!=NULL)
    {
        Display(root -> list -> next -> node,lvl);
        for(int i=1;i<=lvl*2;i++) 
            cout << "  ";
        cout<< root -> s <<endl;
    }
    Display(root -> list -> node,lvl);
}
 
List *MakeSomeList()
{
    List *p = new List;
    List *ptr = p;
    p -> node = NULL;
    for(int i=rand()%2+2;i>0;i--)// создание ссылок наследования узла 2-4
    {
        p -> next = new List;
        p -> next -> node = NULL;//инициализируем НУЛЕМ указатели на узлы
        p = p-> next;
    }
    p -> next = NULL;
    p -> node = NULL;
    return ptr;
}
 
Node *Add(int s, Node *&root,List *Empty)
{
    if(root==NULL)//если пустое дерево
    {
        root=new Node;
        root -> s = s;
        root -> list = MakeSomeList();
        return root;
    }
    List *p = FindEmptyPointer(root,Empty);//находим НУЛЕВУЮ ссылку в дереве,
    Empty = NULL;
    p -> node = new Node;// по ней создаем узел
    p -> node -> s = s;
    p -> node -> list = MakeSomeList();//и этому узлу приписываем список указателей
}
 
List *FindEmptyPointer(Node *root, List *&Empty)//поиск "пустого" указателя
{
    if(Empty != NULL)
        return Empty;
    if(root -> list -> node == NULL)
    {
        Empty = root -> list;
        return Empty;
    }
    if(root -> list -> node != NULL)
        return FindEmptyPointer(root -> list -> node, Empty);
    if(Empty != NULL)
        return Empty;
    if(root -> list -> next != NULL)
        return FindEmptyPointer(root -> list -> next -> node, Empty);
}
 
void main()
{
    setlocale(LC_ALL,"Russian");
    int s;
    int sw;
    int i=0, lvl=0;
    Node *root=NULL;
    List *Empty=NULL;
    do  {
 
        cout << "Возможные действия:" << endl
            << "1. Добавить узел в дерево" << endl
            << "2. Вывести дерево на экран" << endl
            << "3. Поиск узла в дереве" << endl
            << "0. Выход" << endl
            << "Ваш выбор:";
        cin>>sw;
        cout << endl;
        system("cls");
        switch(sw)
        {
        case 1: 
            {
                cout<<"\n\nВведите элемент>>";
                cin>>s;
                if(root==NULL)  root=Add(s,root,Empty);
                else Add(s,root,Empty);
                break;
            }
        case 2:
            {
                if(root==NULL) break;
                    Display(root,lvl);
                    break;
                
            }
            //case '3': DelSomeNode(root);break;
        case 3: 
            {
                cout<<"Введите символ для поиска>>";
                cin>>s;i=0; 
                Search(root,s,i);
                break;
            }
        }
 
    }while(sw!=0);
}