←предыдущая следующая→
... 15 16 17 18 19 20 21 22 23 24 25 26 27
return child[i]->data; }
T p;
for(i=0;i<size;i++) //поддерево
if(child[i]!=NULL)
{ p=child[i]->Get(pos);
if(p!=NULL) return p; }
return 0; }
void main()
{ Tree<int,5> a; //создание дерева с пятью потомками в вершине
a.Add(5); a.Add(11); a.Add(3); a.Add(15); //вставка элементов
int i=a.Get(2); } //взять элемент по номеру
//----------------------------------------------------------------------------
// 8. Двоичное дерево
// 1. Хранение указателей на обьекты
// 1. Включение элемента с сохранением упорядочености.
template <class T> class BTree
{ private:
BTree<T> *l,*r; //указатели на левое и правое поддеревья
T* data;
public:
void Add(T &a);
BTree();
~BTree(); };
template <class T> void BTree<T>::Add(T &a)
{ if(data==NULL) { data=new T; *data=a; return; } //вставка в текущий
if(a>*data)
{ if(r==NULL) r=new BTree<T>; r->Add(a); } else //в правый
{ if(l==NULL) l=new BTree<T>; l->Add(a); } } //в левый
template <class T> BTree<T>::BTree()
{ l=NULL; r=NULL; data=NULL; }//инициализация
template <class T> BTree<T>::~BTree()
{ if(data!=NULL) delete data; //удаление данных
if(l!=NULL) delete l; // -//- левого поддерева
if(r!=NULL) delete r; } // -//- правого поддерева
void main()
{ BTree<long> a; //двоичное дерево из long-ов
a.Add(10); a.Add(3); a.Add(210); a.Add(70); }
//----------------------------------------------------------------------------
// 8. Двоичное дерево
// 1. Хранение указателей на обьекты
// 2. Поиск и возвращение минимального об"екта.
template <class T> class BTree
{ private:
BTree<T> *l,*r; //указатели на левое и правое поддеревья
T* data;
public:
void Add(T &a);
T& Min();
BTree();
~BTree(); };
template <class T> void BTree<T>::Add(T &a)
{ if(data==NULL) { data=new T; *data=a; return; } //вставка в текущий
if(a>*data)
{ if(r==NULL) r=new BTree<T>; r->Add(a); } else //в правый
{ if(l==NULL) l=new BTree<T>; l->Add(a); } } //в левый
template <class T> T& BTree<T>::Min()
{ T* tmp=data,*tmp2;
if(l!=NULL) {tmp2=&l->Min(); if(*tmp2<*tmp) tmp=tmp2;} //поиск слева
if(r!=NULL) {tmp2=&r->Min(); if(*tmp2<*tmp) tmp=tmp2;} //поиск справа
return *tmp; }
template <class T> BTree<T>::BTree()
{ l=NULL; r=NULL; data=NULL; }//инициализация
template <class T> BTree<T>::~BTree()
{ if(data!=NULL) delete data; //удаление данных
if(l!=NULL) delete l; // -//- левого поддерева
if(r!=NULL) delete r; } // -//- правого поддерева
void main()
{ BTree<long> a; //двоичное дерево из long-ов
a.Add(10); a.Add(3); a.Add(210); a.Add(70);
long k=a.Min(); }
//----------------------------------------------------------------------------
// 8. Двоичное дерево
// 1. Хранение указателей на обьекты
// 3. Сортировка (любым методом).
template <class T> class BTree
{ private:
BTree<T> *l,*r; //указатели на левое и правое поддеревья
T* data;
public:
void Add(T &a);
void Sort();
BTree();
~BTree(); };
template <class T> void BTree<T>::Add(T &a)
{ if(data==NULL) { data=new T; *data=a; return; } //вставка в текущий
if(a>*data)
{ if(r==NULL) r=new BTree<T>; r->Add(a); } else //в правый
{ if(l==NULL) l=new BTree<T>; l->Add(a); } } //в левый
template <class T> void BTree<T>::Sort()
{ if(l!=NULL) l->Sort(); //сортировка левого поддерева
if(r!=NULL) r->Sort(); //сортировка правого поддерева
if(l!=NULL&&r!=NULL)
if(*l->data>*r->data){ BTree *t=l; l=r; r=t; } }// обмен
template <class T> BTree<T>::BTree()
{ l=NULL; r=NULL; data=NULL; }//инициализация
template <class T> BTree<T>::~BTree()
{ if(data!=NULL) delete data; //удаление данных
if(l!=NULL) delete l; // -//- левого поддерева
if(r!=NULL) delete r; } // -//- правого поддерева
void main()
{ BTree<long> a; //двоичное дерево из long-ов
a.Add(10); a.Add(3); a.Add(210); a.Add(70);
a.Sort();}
//----------------------------------------------------------------------------
// 8. Двоичное дерево
// 1. Хранение указателей на обьекты
// 4. Двоичный поиск на основе сравнения с внешним об"ектом-ключом
template <class T> class BTree
{ private:
BTree<T> *l,*r; //указатели на левое и правое поддеревья
T* data;
public:
void Add(T &a);
T* FindBin(T &key);
BTree();
~BTree(); };
template <class T> void BTree<T>::Add(T &a)
{ if(data==NULL) { data=new T; *data=a; return; } //вставка в текущий
if(a>*data)
{ if(r==NULL) r=new BTree<T>; r->Add(a); } else //в правый
{ if(l==NULL) l=new BTree<T>; l->Add(a); } } //в левый
template <class T> T* BTree<T>::FindBin(T &key)
{ if(key==*data) return data; T* s=NULL;
if(l!=NULL&&key<*data) s=l->FindBin(key);
if(s!=NULL) return s;
if(r!=NULL&&key>*data) s=r->FindBin(key);
if(s!=NULL) return s;
return NULL; }
template <class T> BTree<T>::BTree()
{ l=NULL; r=NULL; data=NULL; }//инициализация
template <class T> BTree<T>::~BTree()
{ if(data!=NULL) delete data; //удаление данных
if(l!=NULL) delete l; // -//- левого поддерева
if(r!=NULL) delete r; } // -//- правого поддерева
void main()
{ BTree<long> a; //двоичное дерево из long-ов
a.Add(10); a.Add(3); a.Add(210); a.Add(70);
long j=*a.FindBin(210);}
//----------------------------------------------------------------------------
// 8. Двоичное дерево
// 1. Хранение указателей на обьекты
// 5. Включение элемента по номеру.
template
←предыдущая следующая→
... 15 16 17 18 19 20 21 22 23 24 25 26 27