binkerfa.h

Binary search tree sample

/*********************************************************
*	INCLUDES
*********************************************************/
#ifndef BINKERFA_H
#define BINKERFA_H

#include <iostream>
#include <string>
#include <ostream>

using namespace std;

/*********************************************************
*	INTERNAL STRUCTURES
*********************************************************/

template <class T>
class Tree
{
	private:
		class Node
		{
			public:
				T value;
				Node* parent;
				Node* left_ch;
				Node* right_ch;
				Node ();			
				Node (T a);		
		};

		Node* root;
		Node* tmp;	

	public:
		Tree();					
		~Tree();					
		void Insert (T a);			
		void Delete (T a);			
		void InOrder (Node* i);		
		void PostOrder (Node* i);	
		void PreOrder (Node* i);		
		bool Search (T a);			
		void menu ();				
};

/*********************************************************
*	FUNCTIONS
*********************************************************/


/* --------------------------------------------------
| Description : NODE KONSTRUKTOR
| Parameters  : -
| Returns     : -
\--------------------------------------------------- */
template <class T>
Tree<T>::Node::Node()
{
	parent = 0;
	left_ch = 0;
	right_ch = 0;
}


/* --------------------------------------------------
| Description : NODE KONSTRUKTOR
| Parameters  : -
| Returns     : -
\--------------------------------------------------- */
template <class T>
Tree<T>::Node::Node (T a)
{
	parent = 0;
	left_ch = 0;
	right_ch = 0;
	value = a;
}


/* --------------------------------------------------
| Description : TREE KONSTRUKTOR
| Parameters  : -
| Returns     : -
\--------------------------------------------------- */
template <class T>
Tree<T>::Tree()
{
	root = 0;
	tmp = 0;
}


/* --------------------------------------------------
| Description : TREE DESTRUKTOR
| Parameters  : -
| Returns     : -
\--------------------------------------------------- */
template <class T>
Tree<T>::~Tree()
{}


/* --------------------------------------------------
| Description : A f黦gv閚y inorder sorrendben bej醨ja a f醫, 閟 ki韗ja annak elemeit;
| Parameters  : Node* i
| Returns     : -
\--------------------------------------------------- */
template <class T>
void Tree<T>::InOrder (Node* i)
{
	if (i -> left_ch != 0)
	{
		InOrder (i -> left_ch);
	}
	cout<< i -> value << endl;
	if (i -> right_ch != 0)
	{
		InOrder (i -> right_ch);
	}
}


/* --------------------------------------------------
| Description : A f黦gv閚y postorder sorrendben bej醨ja a f醫, 閟 ki韗ja annak elemeit
| Parameters  : Node* i
| Returns     : -
\--------------------------------------------------- */
template <class T>
void Tree<T>::PostOrder (Node* i)
{
	if (i -> left_ch != 0)
	{
		PostOrder (i -> left_ch);
	}
	if (i -> right_ch != 0)
	{
		PostOrder (i -> right_ch);
	}
	cout<< i -> value << endl;
}


/* --------------------------------------------------
| Description : A f黦gv閚y preorder sorrendben bej醨ja a f醫, 閟 ki韗ja annak elemeit
| Parameters  : Node* i
| Returns     : -
\--------------------------------------------------- */
template <class T>
void Tree<T>::PreOrder (Node* i)
{
	cout<< i -> value << endl;
	if (i -> left_ch != 0)
	{
		PreOrder (i -> left_ch);
	}
	if (i -> right_ch != 0)
	{
		PreOrder (i -> right_ch);
	}
}


/* --------------------------------------------------
| Description : 鷍 elemet sz鷕 be a f醔a az elem 閞t閗閚ek megfelel鮡n
| Parameters  : T a
| Returns     : -
\--------------------------------------------------- */
template <class T>
void Tree<T>::Insert (T a)
{
	Node* i = root;
	Node* n = new Node (a);	//鷍 elem l閠rehoz醩a
	
	if (root == 0)		//ha m間 黵es a fa, akkor az 鷍 elemre r後ll韙ja a root pointert
	{
		root = n;
	}
	else
	{
		while (i -> left_ch != 0 || i -> right_ch != 0)	//a ciklus addig megy, am韌 nem tal醠 "falevelet"
		{
			if (a == i -> value)	//ha a besz鷕ni k韛醤t elem m醨 benn van a f醔an, a ciklus le醠l
				break;

			if (a < i -> value && i -> left_ch != 0)	//ha az 鷍 elem kisebb az aktu醠isn醠, 閟 van bal elem, balra megy tov醔b
				i = i -> left_ch;

			else if (a < i -> value && i -> left_ch == 0)	//ha az 鷍 elem kisebb az aktu醠isn醠, 閟 nincs bal elem, 
				break;								//a ciklus meg醠l

			else if (a > i -> value && i -> right_ch == 0)	//ha az 鷍 elem nagyobb az aktu醠isn醠, 閟 nincs jobb elem, 
				break;								//a ciklus meg醠l

			else if (a > i -> value && i -> right_ch != 0)	//ha az 鷍 elem nagyobb az aktu醠isn醠, 閟 van jobb elem,
				i = i -> right_ch;						//jobbra megy tov醔b
		}

		if (a < i -> value)			//ha az 鷍 elem kisebb az aktu醠isn醠, annak bal mutat骿醫 醠l韙ja r