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

  • Автор темы inek
  • Дата начала
I

inek

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

Написать программу, которая находит в заданном непустом бинарном дереве длину (количество ветвей) пути от корня до ближайшей вершины с заданным элементом 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;
}
Количество ветвей считает, но надо чтобы он выдавал путь до БЛИЖАЙШЕЙ вершины с заданным значением! Помогите дополнить! Заранее спасибо!!!