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

Тема в разделе "C/C++/C#", создана пользователем inek, 4 июн 2012.

  1. inek

    inek Гость

    Задача: Разработать шаблон класса для работы с двоичным деревом поиска. Реализовать следующие действия
    • добавление элемента в дерево;
    • удаление элемента из дерева;
    • обход дерева (для печати элементов и т.д.);
    • поиск в дереве.
    Найти количество элементов на заданной глубине
    .
    Шаблон реализовала:
    Код (C++):
    #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))/ Заранее спасибо!
     
Загрузка...

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