Обычное двоичное дерево.

Рубрика: C++, Дата: 7 April, 2013, Автор:
Tags:

Здорова ребятки!

Мы сейчас с вами попытаемся построить обычное двоичное дерево. У которого будут элементы расположены слева от корневого узла будут элементы меньше узлового, а справа больше. И так для каждого узла дерева. Слева от любого узла элемент будет меньше а справа больше.

Я тут господа смотрел код своего бинарного дерева, которое я делал когда то не так давно и решил не переделывать пока его, поэтому я вам скину его щас таким какой он есть. Он состоит из нескольких файлов. Там много их. Конечно он похож на гамнокод да и не похож мне так кажется оформлено паршиво, да правильно бы было переделать, но желания у меня нет это делать. Так что получайте какой есть.

Файл Tree.h:


//opredelenie wablona klacca Tree
#ifndef TREE_H
#define TREE_H

#include <iostream>
using std::cout;
using std::endl;
using std::cerr;
#include <cstdlib>
using std::exit;

#include <new>
#include "Treenode.h"
#include "Queue.h"

//opredelenie wablona klacca Tree
template<typename NODETYPE>class Tree
{
public:
	Tree();//konctryktor
	void insertNode(const NODETYPE &);
	void preOrderTraversal()const;
	void inOrderTraversal()const;
	void postOrderTraversal()const;
	//opredel9ek glybiny dereva
	void depth(int &);
	//vuvod cpicka v obratnom por9dke
	void printListBackward()const;
	void binaryTreeSearch(TreeNode<NODETYPE>*&, NODETYPE &);
	//ydalenie elementa
	void deleteNode(NODETYPE &);
	//obxod dvoichnogo dereva po yrovn9m
	void levelOrder()const;
	//vuvod na pechat6
	void outputTree();
private:
	TreeNode<NODETYPE> *rootPtr;
	
	//cervicnue fynksii	TreeNode<NODETYPE>* searchList();
	void insertNodeHelper(TreeNode<NODETYPE>**,const NODETYPE&);//
	void preOrderHelper(TreeNode<NODETYPE>*)const;
	void inOrderHelper(TreeNode<NODETYPE>*)const;
	void postOrderHelper(TreeNode<NODETYPE>*)const;
	int depthHelper(TreeNode<NODETYPE>*)const;
	void printListBackwardHelper(TreeNode<NODETYPE>*)const;
	TreeNode<NODETYPE>* searchListHelper(TreeNode<NODETYPE>*, NODETYPE &)const;
	void deleteNodeHelper(TreeNode<NODETYPE>**,NODETYPE &value);
	TreeNode<NODETYPE>* zamHelper(TreeNode<NODETYPE>*ptr);
	void outputTreeHelper(TreeNode<NODETYPE>*, int);

};//kones klacca Tree

//konctryktor
template<typename NODETYPE>
Tree<NODETYPE>::Tree()
{
	rootPtr=0;//ykazuvaet, chto derevo iznachal6no pycto
}//kones konctryktora Tree

//vctavit6 yzel v derevo
template<typename NODETYPE>
void Tree<NODETYPE>::insertNode(const NODETYPE &value)
{
	insertNodeHelper(&rootPtr,value);
}//kones fynksii insertNode

//cervicna9 fynksi9, vuzuvaetma9 insertNode; prinimaet ykazatel6
//na ykazatel6, chtobu fynksi9 mogla izmen9t6 znachenie ykazatel9
template<typename NODETYPE>
void Tree<NODETYPE>::insertNodeHelper(
	TreeNode<NODETYPE> **ptr, const NODETYPE &value)
{
	//podderevo pycto; cozdat6 novui TreeNode, coderjawii value
	if(*ptr==0)
		*ptr=new TreeNode<NODETYPE>(value);
	else //podderevo ne pycto
	{
		//vctavl9emue dannue men6we, chem dannue v tekywem yzle
		if(value<(*ptr)->data)
			insertNodeHelper(&((*ptr)->leftPtr),value);
		else
		{
			//vctavl9emue dannue bol6we, chem dannue v tekywem yzle
			if(value>(*ptr)->data)
				insertNodeHelper(&((*ptr)->rightPtr),value);
			else//dyblikatu znachenii dannux ignoriryyutc9
			{
				cout <<value<<" dup"<<endl;
				insertNodeHelper(&((*ptr)->rightPtr),value);//razrewaet dyblirovanie
			}
		}//kones else
	}//kones else
}//kones fynksii insertNodeHelper

//nachat6 obxod dereva c operejayuwei vuborkoi
template<typename NODETYPE>
void Tree<NODETYPE>::preOrderTraversal() const
{
	preOrderHelper(rootPtr);
}//kones fynksii preOrderTraversal

//cervicna9 fynksi9 dl9 obxoda dereva c operejayuwei vuborkoi
template<typename NODETYPE>
void Tree<NODETYPE>::preOrderHelper(TreeNode<NODETYPE> *ptr)const
{
	if(ptr!=0)
	{
		cout <<ptr->data<<' ';//obrabotat6 yzel
		preOrderHelper(ptr->leftPtr);//oboiti levoe podderevo
		preOrderHelper(ptr->rightPtr);//oboiti pravoe podderevo
	}//kones if
}//kones fynksii preOrderHelper

//nachat6 obxod dereva c por9dkovoi vuborkoi
template<typename NODETYPE>
void Tree<NODETYPE>::inOrderTraversal()const
{
	inOrderHelper(rootPtr);
}//kones fynksii inOrderTraversal

//cervicna9 fynksi9 dl9 obxoda dereva c por9dkovoi vuborkoi
template<typename NODETYPE>
void Tree<NODETYPE>::inOrderHelper(TreeNode<NODETYPE> *ptr)const
{
	if(ptr!=0)
	{
		inOrderHelper(ptr->leftPtr);//oboiti levoe podderevo
		cout <<ptr->data<<' ';//obrabotat6 yzel
		inOrderHelper(ptr->rightPtr);//oboiti pravoe podderevo
	}//kones if
}//kones fynksii inOrderHelper

//nachat6 obxod dereva c otlojennoi vuborkoi
template<typename NODETYPE>
void Tree<NODETYPE>::postOrderTraversal()const
{
	postOrderHelper(rootPtr);
}//kones fynksii postOrderTraversal

//cervicna9 fynksi9 dl9 obxoda dereva c otlojennoi vuborkoi
template<typename NODETYPE>
void Tree<NODETYPE>::postOrderHelper(
TreeNode<NODETYPE> *ptr)const
{
	if(ptr!=0)
	{
		postOrderHelper(ptr->leftPtr);//oboiti levoe podderevo
		postOrderHelper(ptr->rightPtr);//oboiti pravoe podderevo
		cout <<ptr->data<<' ';//obrabotat6 yzel
	}//kones if
}//kones fynksii postOrderHelper

//___________________________________________________________________
//opredelenie glybinu dereva
template<typename NODETYPE>
void Tree<NODETYPE>::depth(int &max)
{
	//cout <<"max= "<<max<<endl;
	max=depthHelper(rootPtr);
}

//vcpomogatel6na9 fynkci9 vozvrachaet max
template<typename NODETYPE>
int Tree<NODETYPE>::depthHelper(TreeNode<NODETYPE> *ptr) const
{
	int uroven_Left, uroven_Right, uroven_val;

	if (ptr == 0)
		uroven_val = -1;// Глубина пустого дерева равна -1
	else
	{
		//naxodit makcimal6no levui uroven6
		uroven_Left = depthHelper(ptr->leftPtr);
		//naxodit max pravui yroven6
		uroven_Right = depthHelper(ptr->rightPtr);
		//sravnivaet yrovni i vozvrachaet max
		uroven_val  = 1 + ((uroven_Left > uroven_Right)?uroven_Left :uroven_Right);
	}
//	cout <<uroven_val;
	return uroven_val;
}

template<typename NODETYPE>
//vuvod cpicka v obratnom por9dke
void Tree<NODETYPE>::printListBackward()const
{
	printListBackwardHelper(rootPtr);
}

template<typename NODETYPE>
void Tree<NODETYPE>::printListBackwardHelper(TreeNode<NODETYPE> *ptr)const
{
	if(ptr!=0)
	{
		printListBackwardHelper(ptr->rightPtr);
		cout <<ptr->data<<' ';
		printListBackwardHelper(ptr->leftPtr);

	}
}

//fynksi9 poicka elementa v cpicke return ykazatel6 na yzel
template<typename NODETYPE>
void Tree<NODETYPE>::binaryTreeSearch(TreeNode<NODETYPE>*& ptr, NODETYPE &value)
{
	ptr=searchListHelper(rootPtr, value);
	//cout <<"d d d ptr= "<<ptr<<endl;
}

template<typename NODETYPE>
TreeNode<NODETYPE>* Tree<NODETYPE>::searchListHelper(TreeNode<NODETYPE>* ptr,NODETYPE &value)const
{
	TreeNode<NODETYPE>* serch=0;
	if(ptr!=0)
	{
		if(ptr->data==value)
		{
		//	cout <<"Nawli ptr->data= "<<ptr->data<<" ptr= "<<ptr<<endl;
			 serch=ptr;
		}
		else
		{
			if(serch==0)
				serch=searchListHelper(ptr->leftPtr,value);
			if(serch==0)
				serch=searchListHelper(ptr->rightPtr,value);
		}
		//cout <<"ptr= "<<ptr<<"value= "<<value<<"ptr->data= "<<ptr->data<<endl;
	}
	
	return serch;
}

//fynkci9 ydaleni9 elementa
template<typename NODETYPE>
void Tree<NODETYPE>::deleteNode(NODETYPE &value)
{
	/*if(rootPtr=0)
	{
		cerr <<"Owibka: poputka ydalit6 iz pyctogo dereva";
		exit(1);
	}*/
	if(rootPtr!=0)
	deleteNodeHelper(&rootPtr, value);//prinimaet ykazatel6 na ykazatel6
}

//vcpomogatel6na9 fynkci9 ydaleni9
template<typename NODETYPE>
void Tree<NODETYPE>::deleteNodeHelper(TreeNode<NODETYPE>**ptr, NODETYPE &value)
{
	//poisk elementa dl9 ydaleni9
	//cout <<"ptr= "<<ptr<<" value= "<<value<<" ptr->data= "<<(*ptr)->data<<endl;
	//при разыменовании указателя на указатель мы получаем просто указатель(*) на который указывал указатель на указатель(**) ( просто получаем память адресс указателя собственный )
	if(ptr!=0)
	{
		if((*ptr)->data==value)
		{
			cout <<"ELEMENT NAIDEN (*ptr)->data= "<<(*ptr)->data<<endl;
			// net potomok
			if((*ptr)->leftPtr==0&&(*ptr)->rightPtr==0)
			{
				cout <<"Net potomkov"<<endl;
				TreeNode<NODETYPE>* prom=*ptr;
				delete prom;//ydalenie lista
				//scout <<"ptr= "<<ptr<<" *ptr= "<<*ptr<<endl;
				*ptr=0;
			}
			//odin potomok
			else if(((*ptr)->leftPtr!=0&&(*ptr)->rightPtr==0)||
			    ((*ptr)->leftPtr==0&&(*ptr)->rightPtr!=0))
			{
				cout <<"Ect6 odin potomok "<<endl;
				cout <<"(*ptr)->data= "<<(*ptr)->data<<endl;
				TreeNode<NODETYPE>* prom;
				if((*ptr)->leftPtr!=0)
					prom=(*ptr)->leftPtr;
				else
					prom=(*ptr)->rightPtr;
				cout <<"prom= "<<prom->data<<endl;
				delete *ptr;//osvobojdenie pam9ti na kotoryyu on ykazuvaet
				*ptr=prom;
			}
			//yzel imee dva potomka
			else if((*ptr)->leftPtr!=0&&(*ptr)->rightPtr!=0)
			{
				//naxodim men6wee makcimal6noe
				TreeNode<NODETYPE>* zam;
				zam=zamHelper( (*ptr)->leftPtr );
				//element r9dom bez prava (rightPtr=0)
				cout <<"NAXODIM MEN6WEE MAKCIMAL6NOE ZNACHENIE"<<endl;
				if(zam->rightPtr!=0)
				{	
					if((zam->rightPtr)->leftPtr==0)
					{
						cout <<"ZAM NE IMEET POTOMKOV"<<endl;
						//ydal9em element
						cout <<(*ptr)->data<<' '<<zam->rightPtr->data<<endl;
						//ydal9ema9 oblact6
						TreeNode<NODETYPE>* prom=*ptr;
						//zamen9em danue
						//obnovl9em vetki zamen9emogo elementa
						zam->rightPtr->rightPtr=(*ptr)->rightPtr;
						zam->rightPtr->leftPtr=(*ptr)->leftPtr;
						*ptr=zam->rightPtr;
						//obnyl9em ykazatel6 na poclednii element
						zam->rightPtr=0;
						delete prom;
					}
					else if((zam->rightPtr)->leftPtr!=0)
					{
						cout <<"ECT6 POTOMOK CPRAVA"<<endl;
						//1. coxran9em yk na yzel kotorui doljen but6 ydalen vo
						// vremennoi peremennoi
						TreeNode<NODETYPE>* prom=*ptr;
						//2. yctanovit6 ykazatel6 v roditel6ckom po otnoweniyu k ydal9emomy
						*ptr=zam->rightPtr;
						//3. yctanovit6 ykazatel6 v roditel6ckom po otnoweniyu k 
						//zamechayuchemy, na levogo potomka zamechayuchego yzla
						zam->rightPtr=zam->rightPtr->leftPtr;
						cout <<zam->rightPtr->data<<endl;
						(*ptr)->leftPtr=prom->leftPtr;
						//4. yctanovit6 ykazatel6 na pravoe podderevo v zamechayuchem yzle na
						//pravoe podderevo ydal9emogo yzla
						(*ptr)->rightPtr=prom->rightPtr;
						//5. ydalit6 yzel na kotorui ykazuvaet vremennui ykazatel6
						delete prom;	
					}
				}
				else
				{
					cout <<"Srazy cleva"<<endl;
					cout <<"zam->data= "<<zam->data<<endl;
					//ydal9ema9 oblact6
					TreeNode<NODETYPE>* prom=*ptr;
					//zamen9em dannue
					//obnovl9em vetki zamen9emogo elementa
					zam->rightPtr=(*ptr)->rightPtr;
					*ptr=zam;
					delete prom;
					
				}
				
			}//konec yzel imeet dva potomka
		}//konec poicka elementa
		else
		{
			if((*ptr)->leftPtr!=0)
				deleteNodeHelper(&((*ptr)->leftPtr),value);
			if((*ptr)->rightPtr!=0)
				deleteNodeHelper(&(*ptr)->rightPtr,value);
		}
		//cout <<"ptr= "<<ptr<<" ptr->data= "<<ptr->data<<endl;
	}
}

//vozvrachaet ykazatel6 na krainii levui element
template<typename NODETYPE>
TreeNode<NODETYPE>* Tree<NODETYPE>::zamHelper(TreeNode<NODETYPE>*ptr)
{
	TreeNode<NODETYPE> *search=ptr;
	//cout <<"zPtr->data= "<<ptr->data<<endl;
	if(ptr->rightPtr!=0)
	{
		if((ptr->rightPtr)->rightPtr!=0)
		{
			cout <<"REK VUZOV"<<endl;	
			search=zamHelper(ptr->rightPtr);
		}
	}
	
	return search;
}

//obxod dvoichnogo dereva po yrovn9m
template<typename NODETYPE>
void Tree<NODETYPE>::levelOrder()const
{
	Queue<TreeNode<NODETYPE>*> que;
	// 1. pomectit6 kornevoi yzel v ochered6
	if(rootPtr!=0)
		que.enqueue(rootPtr);
	cout <<"rootPtr->data= "<<rootPtr->data<<endl;
	// 2. poka v ocheredi octayutc9 yzlu
	while(!que.isQueueEmpty())
	{
		TreeNode<NODETYPE>* ptr;
		//cout <<"Ne pycto"<<endl;
		//prochitat6 cledyyuchii yzel v ocheredi
		que.dequeue(ptr);
		//prochitat6 znachenie v yzle
		cout <<ptr->data<<' ';
		//ecli ykazatel6 na levogo potomka yzla ne NULL
		//pomectit6 levogo potomka v ochered6
		if(ptr->leftPtr!=0)
			que.enqueue(ptr->leftPtr);
		//ecli ykazatel6 na pravogo potomka ne NULL
		//pomectit6 pravogo potomka v ochered6
		if(ptr->rightPtr!=0)
			que.enqueue(ptr->rightPtr);
	}
}

//vovod dvoichnogo dereva na pechat6
template<typename NODETYPE>
void Tree<NODETYPE>::outputTree()
{
	outputTreeHelper(rootPtr,0);
}

template<typename NODETYPE>
void Tree<NODETYPE>::outputTreeHelper(TreeNode<NODETYPE>*ptr, int totalSpaces) 
{
	//cout <<ptr->data<<' '<<totalSpaces<<endl;
	// poka ykazatel6 na tekychii yzel ne nylevoi
	if(ptr->rightPtr!=0)
	{
		// rekyrcivno vuzvat6 fynkciyu c pravum poddrerevom tekywego yzla
		// i totalSpacec+5

			outputTreeHelper(ptr->rightPtr,totalSpaces+5);
	}
	//vocpol6zovatc9 operatorom for dl9 vuvoda probelov
	for(int i=0;i<totalSpaces;i++)
		cout <<' ';
	//vuvecti znachenie v tekywem yzle
	cout <<ptr->data<<endl;
	
	//yctanovit6 ykazatel6 tekywego yzla na levoe podderevo tekychego yzla
	//yctanovit6 znachenie totalSpaces na 5
	if(ptr->leftPtr!=0)
	{
		outputTreeHelper(ptr->leftPtr,totalSpaces+5);
	}
}

#endif

Файл Treenode.h:


//Opredelenie wablona klacca TreeNode
#ifndef TREENODE_H
#define TREENODE_H

//oprejayuwee ob69vlenie klacca Tree
template<typename NODETYPE>class Tree;

//opredelenie wablona klacca TreeNode
template<typename NODETYPE>
class TreeNode
{
friend class Tree<NODETYPE>;

public:
	//konctryktor
	TreeNode(const NODETYPE &d)
	:leftPtr(0),//ykazatel6 na levoe podderevo
	data(d),//dannue yzla
	rightPtr(0)//ykazatel6 na pravoe podderemo
	{
		//pyctoe telo
	}//kones konctryktora TreeNode
	
	//vozvratit6 kopiyu dannux yzla
	NODETYPE getData()const
	{
		return data;
	}//kones fynksii getData
private:
	TreeNode<NODETYPE> *leftPtr;//ydazatel6 na levoe podderevo
	NODETYPE data;
	TreeNode<NODETYPE> *rightPtr;//ykazatel6 na pravoe podderevo
};//kones klacca TreeNode

#endif

Файл Queu.h:


//opredelenie wablona klacca Queue, proizvodnogo ot List
#ifndef QUEUE_H
#define QUEUE_H

#include "List.h"//opredelenie klacca List

template<typename QUEUETYPE>
class Queue : private List<QUEUETYPE>
{
public:
	//enqueue vuzuvaet fynksiyu insertAtBack kacca List
	void enqueue(const QUEUETYPE &data)
	{
		insertAtBack(data);
	}//kones fynksii enqueue
	
	//dequeue vuzuvaet fynksiyu removeFromFront klacca List
	
	bool dequeue(QUEUETYPE &data)
	{
		return removeFromFront(data);
	}//kones fynksii dequeue
	
	//isQueueEmpty vuzuvaet fynksiyu isEmpty klacca List
	
	bool isQueueEmpty()const
	{
		return List<QUEUETYPE>::isEmpty();
	}//kones fynksii isQueueEmpty
	
	//printQueue vuzuvaet fynksiyu print klacca List
	
	void printQueue() const
	{
		List<QUEUETYPE>::print();
	}//kones fynksii printQueue
};//kones klacca Queue

#endif

Файл List.h:


//Opredelenie wablona klassa List
#ifndef LIST_H
#define LIST_H

#include <iostream>
using std::cout;
using std::cerr;
#include <cstdlib>
using std::exit;

#include "Listnode.h"//opredelit6 klass ListNode
//zaranee ob69vlenie wablona chtobu mojno bulo ob69vit6 dryjectvennoct6
template<typename NODETYPE>class IndexedList;

template<typename NODETYPE>
class List
{
	//friend class IndexedList<NODETYPE>;
public:
	List();//konctryktor
	~List();//dectryktor
	void insertAtFront(const NODETYPE &);
	void insertAtBack(const NODETYPE &);
	bool removeFromFront(NODETYPE &);
	bool removeFromBack(NODETYPE &);
	bool isEmpty() const;
	void print() const;
	void searchList(ListNode<NODETYPE>*&,NODETYPE &)const;
	void insertAtAny(const NODETYPE &,int);
	void removeFromAny(NODETYPE &,int);
private:
	ListNode<NODETYPE> *firstPtr;//ykazatel6 na pervui yzel
	ListNode<NODETYPE> *lastPtr;//ykazatel6 na poclednii yzel
	
	//cervisna9 fynksi9 dl9 vudeleni9 pam9ti novogo yzla
	ListNode<NODETYPE> *getNewNode(const NODETYPE &);
	ListNode<NODETYPE> *searchListHelper(ListNode<NODETYPE>*ptr,NODETYPE &value)const;
	ListNode<NODETYPE> *insertAtAnyHelper(ListNode<NODETYPE>*,int &);
	ListNode<NODETYPE> *removeFromAnyHelper(ListNode<NODETYPE>*,int &);
};//konec klassa List
///////////////////////////////////////////////////////////////////////////////////

//konstryktor po ymolchaniyu
template<typename NODETYPE>
List<NODETYPE>::List()
:firstPtr(0),lastPtr(0)
{
	//pystoe telo
}//konec konctryktora List

//dectryktor
template<typename NODETYPE>
List<NODETYPE>::~List()
{
	if(!isEmpty())//cpisok ne pyst
	{
		cout <<"Destroying nodes ...\n";
		
		ListNode<NODETYPE> *currentPtr=firstPtr;
		ListNode<NODETYPE> *tempPtr;
		
		while(currentPtr!=0)//ydalit6 octavwies9 yzlu
		{
			tempPtr=currentPtr;
		//	cout <<tempPtr->data<<'\n';
			currentPtr=currentPtr->nextPtr;
			delete tempPtr;
		}//kones while
	}//konec if
	
	cout <<"All nodes destroyed\n\n";
}//konec dectryktora List

//vctavit6 yzel v nachalo cpicka
template<typename NODETYPE>
void List<NODETYPE>::insertAtFront(const NODETYPE &value)
{
	ListNode<NODETYPE> *newPtr=getNewNode(value);//novui yzel
	
	if(isEmpty())//cpicok pyst
		firstPtr=lastPtr=newPtr;//cpicok imeet vcego odin yzel
	else //List is not empty
	{
		newPtr->nextPtr=firstPtr;//novui ykazatel6 na predudywii
		firstPtr=newPtr;//napravit6 firstPtr na novui yzel
	}//konec else
}//konec fynksii insertAtFront

//vctavit6 yzel v nachalo cpicka
template<typename NODETYPE>
void List<NODETYPE>::insertAtBack(const NODETYPE &value)
{
	ListNode<NODETYPE> *newPtr=getNewNode(value);//novui yzel
	
	if(isEmpty())//cpicok pyct
		firstPtr=lastPtr=newPtr;//cpicok imeet vcego odin yzel
	else//cpisok ne pyct
	{
		lastPtr->nextPtr=newPtr;//obnovit6 buvwii poslednii yzel
		lastPtr=newPtr;//novui poslednii yzel
	}//konec else
}//kones fynksii insertAtBack

//ydalit6 yzel iz nachala cpicka
template<typename NODETYPE>
bool List<NODETYPE>::removeFromFront(NODETYPE &value)
{
	if(isEmpty())//cpicok pyct
		return false;//neydachnoe ydalenie
	else
	{
		ListNode<NODETYPE> *tempPtr=firstPtr;//dl9 ydaleni9
		
		if(firstPtr==lastPtr)
			firstPtr=lastPtr=0;//pocle ydaleni9 yzlov net
		else
			firstPtr=firstPtr->nextPtr;//napravit6 na buvwii 2-i yzel
			
		value=tempPtr->data;//vozvratit6 ydal9emue dannue
		delete tempPtr;//ocvobodit6 ydalennui pervui yzel
		return true;//ydachnoe ydaleni
	}//konec else
}//konec fynksii removeFromFront

//ydalit6 yzel iz konsa spiska
template<typename NODETYPE>
bool List<NODETYPE>::removeFromBack(NODETYPE &value)
{
	if(isEmpty())//cpicok pyst
		return false;//neydachnoe ydaleni
	else
	{
		ListNode<NODETYPE> *tempPtr=lastPtr;//dl9 ydaleni9
		
		if(firstPtr==lastPtr)//v cpicke odin element
			firstPtr=lastPtr=0;//posle ydaleni9 yzlov net
		else
		{
			ListNode<NODETYPE> *currentPtr=firstPtr;
			
			//locate second-to-last element
			while(currentPtr->nextPtr!=lastPtr)
				currentPtr=currentPtr->nextPtr;//pereiti k cledyyuchemy
			
			lastPtr=currentPtr;//ydalit6 poslednii yzel
			currentPtr->nextPtr=0;//teper6 eto poslednii yzel
		}//konec else
		
		value=tempPtr->data;//vozvratit6 dannue buvwego poslednego
		delete tempPtr;//ocvobodit6 buvwii poclednii yzel
		return true;//ydachnoe ydalenie
	}//konec else
}//konec fynksii removeFromBack

//cpicok pyct?
template<typename NODETYPE>
bool List<NODETYPE>::isEmpty() const
{
	return firstPtr==0;
}//konec fynksii isEmpty

//vozvratit6 ykazatel6 na vnov6 vudelennui yzel
template<typename NODETYPE>
ListNode<NODETYPE> *List<NODETYPE>::getNewNode(
const NODETYPE &value)
{
	return new ListNode<NODETYPE>(value);
}//konec fynksii getNewNode

//vuvecti coderjimoe cpicka
template<typename NODETYPE>
void List<NODETYPE>::print()const
{
	if(isEmpty())//cpicok pyst
	{
		cout <<"The list is empty\n\n";
		return;
	}//kones if
	
	ListNode<NODETYPE> *currentPtr=firstPtr;
	
	cout <<"The list is: ";
	
	while(currentPtr!=0)//polychit6 dannue elementa
	{
		cout <<currentPtr->data<<' ';
		currentPtr=currentPtr->nextPtr;
	}//konec while
	
	cout <<"\n\n";
}//kones fynksii print

//poick po cpicky
template<typename NODETYPE>
void List<NODETYPE>::searchList(ListNode<NODETYPE>*&ptr,NODETYPE &value)const
{
	ptr=searchListHelper(firstPtr,value);
}

//vcpomogatel6na9 fynkci9 dl9 poicka
template<typename NODETYPE>
ListNode<NODETYPE>* List<NODETYPE>::searchListHelper(ListNode<NODETYPE>*ptr,NODETYPE &value)const
{
	ListNode<NODETYPE>* search=0;
	if(ptr!=0)
	{
		if(value==ptr->data)
		{
			search=ptr;
		//	cout <<"naiden search= "<<search<<endl;
		}
		else
		{
			search=searchListHelper(ptr->nextPtr,value);
		}
		//cout <<"ptr= "<<ptr<<" ptr->data= "<<ptr->data<<" value= "<<value<<endl;
	}
	//cout <<"search= "<<search<<" value= "<<value<<' '<<search->data<<endl;
	return search;
}

template<typename NODETYPE>
//fynkci9 vctavki znacheni9 v proizvol6nom mecte klacca
void List<NODETYPE>::insertAtAny(const NODETYPE &value,int poz)
{
	ListNode<NODETYPE> *newPtr=getNewNode(value);//novui yzel
	
	if(isEmpty())//cpicok pyst
	{
		insertAtBack(value);
	}
	else if(poz==0)
	{
		insertAtFront(value);
	}
	else //List is not empty
	{
		ListNode<NODETYPE>* yk;
		yk=insertAtAnyHelper(firstPtr,poz);
		if(yk==lastPtr)
		{
			insertAtBack(value);//vctavl9em v konec
		}
		else
		{
			ListNode<NODETYPE>* prom=yk->nextPtr;//xranit ykazateli na prom
			yk->nextPtr=newPtr;//pricvaivaem pocle 2->0
			yk->nextPtr->nextPtr=prom;//ykazuvaem na cledywii yzel
		}
	}//konec else
}

//vcpomogatel6na9 fynkci9 dl9 poicka mecta vctavki
template<typename NODETYPE>
ListNode<NODETYPE>* List<NODETYPE>::insertAtAnyHelper(ListNode<NODETYPE>*ptr,int &value)
{
	ListNode<NODETYPE>* search=ptr;
	value--;
	if(value!=0)
	{
		if(ptr->nextPtr!=0)
		{

			search=insertAtAnyHelper(ptr->nextPtr, value);
		}
		else
		{
			cerr <<"korotkii cpicok "<<value<<endl;
			exit(1);
		}
	}
	return search;
}

//fynkci9 ydal9et c lyubogo mecta
template<typename NODETYPE>
void List<NODETYPE>::removeFromAny(NODETYPE &value,int poz)
{
	if(isEmpty())//cpicok pyst
	{
		cout <<"cpicok pyct"<<endl;
	}
	else if(poz==0)
	{
		removeFromFront(value);
	}
	else
	{
		cout <<"poz= "<<poz<<endl;
		ListNode<NODETYPE>* yk;
		yk=insertAtAnyHelper(firstPtr,poz);
	/*	cout <<"yk->data= "<<yk->data<<endl;
		cout <<"yk->nextPtr->data= "<<yk->nextPtr->data<<endl;
		cout <<"yk->nextPtr->nextptr->data= "<<yk->nextPtr->nextPtr->data<<endl;*/
		if(yk==lastPtr)
		{
			removeFromBack(value);
		}
		else
		{
			ListNode<NODETYPE>* prom=yk->nextPtr;//ydal9ema9 oblact6
			yk->nextPtr=yk->nextPtr->nextPtr;
			value=prom->data;//vozvrat znacheni9
			delete prom;//ydalenie pam9ti
		}
		
	}
}

//vcpomogatel6na9 fynkci9 dl9 ydaleni9
template<typename NODETYPE>
ListNode<NODETYPE>* List<NODETYPE>::removeFromAnyHelper(ListNode<NODETYPE>*ptr,int &value)
{
	ListNode<NODETYPE>* search=ptr;
	value--;
	if(value!=0)
	{
		if(ptr->nextPtr!=0)
		{

			search=insertAtAnyHelper(ptr->nextPtr, value);
		}
		else
		{
			cerr <<"korotkii cpicok "<<value<<endl;
			exit(1);
		}
	}
	return search;
}

#endif

Файл ListNode.h:


//Opredelenie wablona klassa ListNode
#ifndef LISTNODE_H
#define LISTNODE_H

//Operejayuwee ob69vlenie klassa List neobxodimo, chtobu List
//mojno bulo ispol6zovat6 v ob69vlenii dryjestvennosti v ctroke 13
template<typename NODETYPE>class List;

template<typename NODETYPE>
class ListNode
{
friend class List<NODETYPE>;//cdelat6 List drygom
	
public:
	ListNode(const NODETYPE &);//konstryktor
	NODETYPE getData() const;//vozvratit6 dannue v yzle
private:
	NODETYPE data;//dannue
	ListNode<NODETYPE> *nextPtr;//cledyyuwii yzel v cpicke
};//koenc klassa ListNode

//konctryktor
template<typename NODETYPE>
ListNode<NODETYPE>::ListNode(const NODETYPE &info)
:data(info),nextPtr(0)
{
	//pystoe telo
}//konec konctryktora ListNode

//vozvratit6 kopiyu dannux v yzle
template<typename NODETYPE>
NODETYPE ListNode<NODETYPE>::getData() const
{
	return data;
}//konec fynksii getData

#endif

И сам исполняемый файл main.cpp;

//dvoichnoe derevo
#include <iostream>
using std::cout;
using std::endl;
#include <cstdlib>
using std::rand;
using std::srand;
#include <ctime>
using std::time;

#include "Tree.h"

int main()
{
	Tree<int> d;
	
	//zapoln9em derevo
	srand(time(0));
	for(int i=0;i<10;i++)
	{
		d.insertNode(1+rand()%50);
	}
	
	//vuvod na pechat6
	d.outputTree();
	
	return 0;
}

Да господа я было хотел его переделать сделать как, то компактнее, да долго это все возиться с ним, а тем более если мне это не сильно нужно, как бы сказать не первой важности.

[youtube]http://www.youtube.com/watch?v=1ERTC0WqQyw[/youtube]

rss