Поиск в бинарном дереве.

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

Напишите функцию которая выполняет поиск в бинарном дереве с узлами содержащими char*. Если находиться узел содержащий hellow, то вызов fined(“hellow”) возвращает указатель на этот узел. Для индикации того факта, что никакой узел не найден, используйте исключение.

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

Переделал я дерево под нашу задачу вод код самого дерева файл Tree1.h:

//ob69vlenie dvoichnogo dereva
#ifndef TREE1_H
#define TREE1_H
#include <string>
using std::string;
#include <cstring>
using std::strlen;
using std::strcpy;

struct TreeNode1
{
	char* data;
	TreeNode1 *leftPtr;
	TreeNode1 *rightPtr;
	//konctryktor preobrazovani9
	TreeNode1(char* s)
	{
		data=new char[strlen(s)+1];
		strcpy(data,s);
	}
	
	//ocvobojdenie recyrcov
	~TreeNode1()//при вызове освобождаем ресурс
	{
		delete data;
	}
};

class Tree1
{
	TreeNode1 *rootPtr;
	void insertNodeHelper(char*,TreeNode1 **ptr);
	void outputTreeHelper(TreeNode1*, int);
	TreeNode1* searchListHelper(TreeNode1* ptr,char* value1)const;
public:
	class Except//icklyuchenie ecli yzel ne naiden
	{
	public:
		string s;
		Except(string ss):s(ss){}
		Except():s("nety"){}
		string getS(){return s;}
	};
	//konctryktor po ymolchaniyu
	Tree1();
	
	//dobavlenie yzla
	void insertNode(char*);
	
	//vuvod na pechat6
	void outputTree();
	
	//poick elementa v dereve
	char* binaryTreeSearch(char* value1);
};

#endif

файл Tree1.cpp:

//opredelenie klacca Tree1
#include <cstdlib>
using std::exit;
#include <cstring>
using std::strcmp;

#include "Tree1.h"

//konctryktor po ymolchaniyu
Tree1::Tree1()
{
	rootPtr=0;
}

//dobavlenie yzla
void Tree1::insertNode(char* s)
{
	insertNodeHelper(s, &rootPtr);
}

//dobavit6 element v dvoichnoe derevo
void Tree1::insertNodeHelper(char* s, TreeNode1 **ptr)
{
	//podderevo pycto; cozdat6 novui TreeNode, coderjawii value
	if(*ptr==0)
		*ptr=new TreeNode1(s);
	else //podderevo ne pycto
	{
		//vctavl9emue dannue men6we, chem dannue v tekywem yzle
		if(s[0]<(*ptr)->data[0])
			insertNodeHelper(s,&((*ptr)->leftPtr));
		else
		{
			//vctavl9emue dannue bol6we, chem dannue v tekywem yzle
			if(s[0]>(*ptr)->data[0])
				insertNodeHelper(s,&((*ptr)->rightPtr));
			else//dyblikatu znachenii dannux ignoriryyutc9
			{
				cout <<s<<" dup"<<endl;
				insertNodeHelper(s,&((*ptr)->rightPtr));//razrewaet dyblirovanie
			}
		}//kones else
	}//kones else
}

//vovod dvoichnogo dereva na pechat6
void Tree1::outputTree()
{
	outputTreeHelper(rootPtr,0);
}

//vuvod dereva
void Tree1::outputTreeHelper(TreeNode1*ptr, int totalSpaces) 
{
	//cout <<ptr->data<<' '<<totalSpaces<<endl;
	// poka ykazatel6 na tekychii yzel ne nylevoi
	if(ptr!=0)
	{
		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);
		}
	}
}

//poick elementa v dereve
char* Tree1::binaryTreeSearch(char* value1)
{
	TreeNode1* ptr=searchListHelper(rootPtr, value1);
	if(ptr==0)//generaci9 icklyucheni9
		throw Except(value1);
		
	return ptr->data;
}
//pick help fynkci9
TreeNode1* Tree1::searchListHelper(TreeNode1* ptr,char* value1)const
{
	TreeNode1* serch=0;
	if(ptr!=0)
	{
		if(strcmp(ptr->data,value1)==0) //nawli
		{
		//	cout <<"Nawli ptr->data= "<<ptr->data<<" ptr= "<<ptr<<endl;
			 serch=ptr;
		}
		else
		{
			if(serch==0)
				serch=searchListHelper(ptr->leftPtr,value1);
			if(serch==0)
				serch=searchListHelper(ptr->rightPtr,value1);
		}
		//cout <<"ptr= "<<ptr<<"value= "<<value<<"ptr->data= "<<ptr->data<<endl;
	}
	
	return serch;
}

и сам файл main.cpp:

//poick v binarnom dvoichnom dereve
#include <iostream>
using std::cout;
using std::endl;

#include "Tree1.cpp"

int main()
{
	try
	{
		Tree1 d;
		char s3[]="figy";
		char s[]="hellow";
	
		d.insertNode(s);
	
		char s1[]="world";
		d.insertNode(s1);
	
		char s2[]="gacpada";
		d.insertNode(s2);
	
		d.outputTree();
	
		cout <<d.binaryTreeSearch(s3)<<endl;
	}
	catch(Tree1::Except& a)
	{
		cout <<"ne naiden element "<<a.getS()<<endl;
	}
	return 0;
}

Как я создал исключение? Да я просто в классе Tree1 создал вложенный тип Except и все получил и вызвал оператор trow которому передал объект Except(value1) с именем не найденного элемента и все, а дальше перехватил исключение в блоке try и обработал catch(Tree1::Except& a) и все. Я другого просто способа обработки исключений не знаю, так что делаю так как знаю, да и в задаче дополнительного ни какого условия не было. 🙂

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

rss