Деревья

Тема в разделе "Общие вопросы по С и С++", создана пользователем ermackprogramis, 13 май 2011.

Статус темы:
Закрыта.
  1. ermackprogramis

    ermackprogramis Гость

    Добрый всем день, у меня возникла проблема с работой с деревьями. Нужно сделать так что бы пользователь мог вводить уровень дерева, а програма выдавала сколько на этом уровне элементов и выводила их на экран. Не знаю как это сделать.Пробовал много вариантов но никак не выходит.Помогите пожалуйста. Подскажите как это сделать. Вот код остальной програмы:
    Код (C++):
    #include <iostream>
    #include <conio.h>
    #include <stdlib.h>
    #include <vector>
    #include <iomanip>
    #include <math.h>

    using namespace std;

    struct node
    {
    int Key;
    node *Left;
    node *Right;
    };
    node *Tree; // указатель на корень дерева
    int n;
    int count=0;

    //==вершина дерева==
    node** GetTree()
    {
    return &Tree;
    }

    // прототипи функций
    void Search(int,node**);
    void BuildTree();
    void clean();
    void CleanTree(node **);
    void level(node **,int);

    void Bypass1();
    void Bypass_End(node **);
    void Bypass2();
    void Bypass_Left(node **);
    void Bypass3();
    void Bypass_Back(node **);

    void out_tree();
    void output(node**,int);

    void h();
    int Height(node**);
    void choose();

    void add();
    void Search2(int,node**);

    //==главная функция==
    int main()
    {
    while(true)
    {
    system("cls");

    // меню
    cout<<"      Menu"<<endl;
    cout<<"1. Create binary tree"<<endl;
    cout<<"2. Output binary tree"<<endl;
    cout<<"3. Elements on n level"<<endl;
    cout<<"4. Height of tree"<<endl;
    cout<<"5. Bypass binary tree"<<endl;
    cout<<"6. Add elements to tree"<<endl;
    cout<<"7. Delete"<<endl;
    cout<<"8. Exit"<<endl;

    switch((int)getch())
    {
    case 49: {BuildTree ();break;} // ввод дерева
    case 50: {out_tree();break;} // вывод дерева
    case 51: {system("cls");cout<<"Enter level of tree"<<endl;cin>>n;level(GetTree(),n);getch();break;}
    case 52: {h();break;} // высота дерева
    case 53: {choose();break;} // выбор обхода дерева
    case 54: {add();break;} // дополнения дерева
    case 55: {clean();break;} // очистка дерева
    case 56: {;break;}
    case 57: {exit(0);break;} // выход
    }
    }
    }

    //==создание дерева==
    void BuildTree ()
    {
    system("cls");
    int element; // ключ дерева

    cout<<"Enter elements(to finish press 0)"<<endl;
    cin>>element; // ввод элемента

    while (element!=0)
    {
    Search (element,&Tree); cin>>element;
    }
    }

    //==поиск вставки элемента==
    void Search (int x,node **p)
    // *p - указатель на корень дерева.
    {
    if (*p==NULL)
    {
    *p = new(node);
    (**p).Key = x;
    (**p).Left = NULL;
    (**p).Right = NULL;
    }
    else
    if(x<(**p).Key)
    {
    Search (x,&((**p).Left)); // занести в левое поддерево
    }
    else
    if(x>(**p).Key)
    {
    Search (x,&((**p).Right)); // занести в правое поддерево
    }
    }

    void out_tree()
    {
    system("cls");
    output(GetTree(),0);
    getch();
    }

    //==вывод дерева==
    void output (node **w,int l)
    {
    if(*w!=NULL)
    {
    output (&((**w).Right),l+1);
    for(int i=1; i<=l; i++) cout<<"  ";
    cout<<(**w).Key<<endl;
    output (&((**w).Left),l+1);
    }
    }

    //==элементи на n-ном уровне==
    void level(node **w,int l)
    {

    }

    //==выбор обхода дерева==
    void choose()
    {
    system("cls");

    // меню
    cout<<"1. Bypass Root->A->B"<<endl;
    cout<<"2. Bypass A->B->Root"<<endl;
    cout<<"3. Bypass A->Root->B"<<endl;
    cout<<"4. Exit"<<endl;

    switch((int)getch())
    {
    case 49: {Bypass1();break;}
    case 50: {Bypass2();break;}
    case 51: {Bypass3();break;}
    case 52: {exit(0);break;}
    }
    }

    //==обход дерева №1==
    void Bypass1()
    {
    system("cls");
    cout<<"Bypass Root->A->B"<<endl;
    Bypass_Left(GetTree());
    getch();
    }

    //==обход дерева с лева на право==
    void Bypass_Left(node **w)
    {
    if(*w!=NULL)
    {
    cout<<(**w).Key<<" ";
    Bypass_Left (&((**w).Left));
    Bypass_Left (&((**w).Right));
    }
    }

    //==обход дерева №2==
    void Bypass2()
    {
    system("cls");
    cout<<"Bypass A->B->Root"<<endl;
    Bypass_End(GetTree());
    getch();
    }

    //==обхід дерева з права на лево==
    void Bypass_End (node **w)
    {
    if(*w!=NULL)
    {
    Bypass_End (&((**w).Left));
    Bypass_End (&((**w).Right));
    cout<<(**w).Key<<" ";
    }
    }

    //==обход дерева №3==
    void Bypass3()
    {
    system("cls");
    cout<<"Bypass A->Root->B"<<endl;
    Bypass_Back(GetTree());
    getch();
    }

    //==обход дерева сверху в низ==
    void Bypass_Back (node **w)
    {
    if(*w!=NULL)
    {
    Bypass_Back (&((**w).Left));
    cout<<(**w).Key<<" ";
    Bypass_Back (&((**w).Right));
    }
    }

    //==дополнение дерева дерева==
    void add()
    {
    system("cls");
    int element;

    cout<<"Enter elements(to finish press 0)"<<endl;
    cin>>element;

    while (element!=0)
    {
    Search2(element,&Tree); cin>>element;
    }
    }

    //==поиск вставки элемента==
    void Search2(int x,node **p)
    // *p - покажчик на корінь дерева.
    {
    if(x<(**p).Key)
    {
    Search (x,&((**p).Left)); /
    }
    else
    if(x>(**p).Key)
    {
    Search (x,&((**p).Right));
    }
    }

    void clean()
    {
    system("cls");
    CleanTree(GetTree());
    cout<<"Done"<<endl;
    getch();
    }

    //==очистка дерева==
    void CleanTree (node **w)
    {
    if(*w!=NULL)
    {
    CleanTree (&((**w).Left));
    CleanTree (&((**w).Right));
    delete *w;
    }
    }

    void h()
    {
    system("cls");
    Height(GetTree());
    cout<<"Height of tree: "<<Height(GetTree())<<endl;
    getch();
    }

    //==высота дерева==
    int Height (node **w)
    {
    //if(*w==NULL)
    //{ cout<<"Tree is empty!!!"<<endl;break; }
    int h1,h2;
    if(*w==NULL) return (-1);
    else
    {
    h1=Height (&((**w).Left));
    h2=Height (&((**w).Right));
    if(h1>h2) return (1 + h1);
    else return (1 + h2);
    }
    }
     
  2. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    А корень - это какой уровень?
     
  3. ermackprogramis

    ermackprogramis Гость

    корень - это 0 уровень.
     
Загрузка...
Похожие Темы - Деревья
  1. TLandertinger
    Ответов:
    1
    Просмотров:
    1.285
  2. 123456789igor
    Ответов:
    0
    Просмотров:
    1.448
  3. fedotxxl
    Ответов:
    13
    Просмотров:
    5.493
Статус темы:
Закрыта.

Поделиться этой страницей