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

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

  1. inek

    inek Гость

    Задача: Разработать шаблон класса для работы с двоичным деревом поиска. Реализовать следующие действия
    добавление элемента в дерево;
    удаление элемента из дерева;
    обход дерева (для печати элементов и т.д.);
    поиск в дереве.

    Написать программу, которая находит в заданном непустом бинарном дереве длину (количество ветвей) пути от корня до ближайшей вершины с заданным элементом E.

    Шаблон реализовала:
    Код (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;}
    int 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>
    int BTree<T>::dn(Node *root1, int N, int i, int& kol)
    { bool fl=0;
    int m;
    m=kol;
    if (root1)
    {dn(root1->L,N,i+1,kol);
    if (root1->data==N)
    {kol=i;}
    dn(root1->R,N,i+1,kol);
    }
    }
    int main()
    {
    int n;
    double N;
    double a;
    BTree<double> *T = new BTree<double>();
    cout << "Enter N: ";
    cin >> n;
    while (--n > -1)
    {    cin >> a;
    T->addChild(a);
    }
    T->print(T->Get_F());
    cout<<"vvedite N"; cin>>N;
    int kol=0;
    T->dn(T->Get_F(), N, 0,kol);
    cout<<"kol= "<<kol;
    system("PAUSE");
    return EXIT_SUCCESS;
    }
    Количество ветвей считает, но надо чтобы он выдавал путь до БЛИЖАЙШЕЙ вершины с заданным значением! Помогите дополнить! Заранее спасибо!!!
     
Загрузка...

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