1. Набираем команду codeby webinar. Набираем команду для организации и проведения вебинаров. Подробнее ...

    Скрыть объявление
  2. Требуются разработчики и тестеры для проекта codebyOS. Требования для участия в проекте: Знание принципов работы ОС на базе Linux; Знание Bash; Крайне желательное знание CPP, Python, Lua; Навыки системного администрирования. Подробнее ...

    Скрыть объявление
  3. Получи 30.000 рублей. Для получения денег необходимо принять участие в конкурсе авторов codeby. С условиями и призами можно ознакомиться на этой странице ...

    Внимание! Регистрация авторов на конкурс закрыта.

    Скрыть объявление

С++: Шаблон Дерева

Тема в разделе "Вопросы новичков и не только", создана пользователем inek, 4 июн 2012.

  1. inek

    inek Гость

    Репутация:
    0
    Задача: Разработать шаблон класса для работы с двоичным деревом поиска. Реализовать следующие действия
    • добавление элемента в дерево;
    • удаление элемента из дерева;
    • обход дерева (для печати элементов и т.д.);
    • поиск в дереве.
    Найти количество элементов на заданной глубине
    .
    Шаблон реализовала:
    Код:
    #include <cstdlib>
    #include <iostream>
    #include <ctime>
    #include <string>
    
    using namespace std;
    
    template <typename T>
    class BTree
    {
    struct Node
    {
    T data;
    Node *L, *R;
    Node(T d, Node *left = 0, Node *right = 0):data(d), L(left), R(right) {}
    };
    Node *root;
    void insRec(Node* &r, T d)
    {
    if (!r)
    r = new Node(d,0,0);
    else
    if(d < r->data)
    insRec(r->L, d);
    else
    insRec(r->R, d);
    }
    
    void delRec(Node* &r, T d)
    {
    Node *P, *v;
    if (!r) 
    cout << "Element '"<< d <<"' not found..." << endl;
    else
    if (d < r->data) 
    delRec(r->L, d);
    else 
    if (d > r->data) 
    delRec(r->R, d);
    else 
    {
    P = r;
    if (!r->R) 
    r = r->L;
    else 
    if (!r->L) 
    r = r->R;
    else
    {
    v = r->L;
    if (v->R)
    {
    while (v->R->R) v = v->R; 
    r->data = v->R->data;
    P = v->R; 
    v->R = v->R->L;
    }
    else
    {
    r->data = v->data;
    P = v;
    r->L=r->L->L;
    }
    }
    delete P;
    }
    }
    
    bool findRec(Node* r, T d)
    {
    if (!r) 
    return false;
    else 
    if (d == r->data) 
    return true;
    else 
    if (d < r->data) 
    return findRec(r->L, d);
    else 
    return findRec(r->R, d);	
    }
    public:
    BTree(Node *r = 0):root(r){}
    ~BTree();
    void addChild(T d);
    void del(T d);
    void print(Node *root1);
    bool find(T d);
    Node *Get_F(){return root;}
    void dn(Node *root1, int N, int i, int kol);
    };
    
    template <typename T>
    void BTree<T>::addChild(T d) 
    { 
    insRec(root, d);	
    }
    
    template <typename T>
    void BTree<T>::del(T d) 
    { 
    delRec(root, d);	
    }
    
    template <typename T>
    void BTree<T>::print(Node *root1)
    {
    if (root1)
    {print(root1->L);
    cout << root1->data<< " ";
    print(root1->R);}
    }
    
    template <typename T>
    bool BTree<T>::find(T d)
    {
    return findRec(root, d);
    }
    template <typename T>
    void BTree<T>::dn(Node *root1, int N, int i, int kol)
    {
    if (root1)
    {
    dn(root1->L,N,i+1,kol);
    if (i==N) kol++;
    dn(root1->R,N,i+1,kol);
    }
    }
    int main()
    {
    int n,N,kol;
    int a;
    BTree<int> *T = new BTree<int>();
    cout << "Enter N: ";
    cin >> n;
    while (--n > -1)
    {	 cin >> a;
    T->addChild(a);
    }
    T->print(T->Get_F());
    cout<<"vvedite N"; cin>>N;
    
    T->dn(T->Get_F(), N, 0,0);
    cout<<"kol= "<<kol;
    system("PAUSE");
    return EXIT_SUCCESS;
    }

    Помогите найти ошибку в подсчете количества элементов (функция dn(Node *root1, int N, int i, int kol))/ Заранее спасибо!
     
Загрузка...

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