查找 -- 二叉树查找法[anank].cpp

包含了二叉树查找法

/******************************************************************************************************
** Program Name : Searching Operations From Binary Search Tree
** Author       : Lu Jian Hua
** Time         : 2007-6-2
*******************************************************************************************************/

#include <iostream>
using namespace std ;

const int LEFT  = 0 ;				
const int RIGHT = 1 ;

/*-------------------------------------Class Node ( Node Of BTree )----------------START--------------------*/
class Node													// Node of tree
{
public:
	char c ;												// data  portion
	Node *L_Child ;											// left  child 
	Node *R_Child ;											// right child 
	Node *next ;
	Node() : c(0), L_Child(NULL), R_Child(NULL)	{}
	Node(char ch) : c(ch), L_Child(NULL), R_Child(NULL), next(NULL) {}
} ;
/*-------------------------------------Class Node ( Node Of BTree )-----------------END---------------------*/


/*--------------------------------------Class Stack---------------------------------START-------------------*/
class Stack
{
public:
	Stack(int max_size) ;					// constructor
	Node*  GetTopValue() const ;			// get the top value of stack
	void Push(Node* value) ;				// push
	Node*  Pop() ;							// pop
	void Init() ;							// initialize the stack
	bool IsEmpty() ;						// is empty ?
private:
	enum { MAX_SIZE = 100 } ;
	int top ;
	Node* element[MAX_SIZE] ;
} ;


Stack::Stack(int max_size) : top(-1) {}

Node* Stack::GetTopValue() const
{
	if (top < 0)
	{
		return 0 ;
	}

	return element[top] ;
}

void Stack::Push(Node* value)				// Operation:push a element into stack
{
	if (top >= MAX_SIZE-1)
	{
		cout << "The stack is full!    " << endl << endl ;
		return ;
	}

	top++ ;									// 1> move the top pointer
	element[top] = value ;					// 2> infill the space top pointer directing
}

Node* Stack::Pop()							// Operation:Pop a element from stack
{
	if (top < 0)
	{
		return 0 ;
	}

	Node* temp = element[top] ;				// 1> get the value
	top-- ;									// 2> move the top pointer
	return temp ;
}

void Stack::Init()
{
	top = -1 ;
}

bool Stack::IsEmpty()						// test if the stack is empty ?
{
	return ( top < 0 ) ;
}
/*--------------------------------------Class Stack---------------------------------END---------------------*/


/*--------------------------------------Class Queue---------------------------------START-------------------*/

class Queue									// class of Queue
{
public:
	Queue() ;
	Node*  GetValue() const ;				// get the current value of Queue
	Node*  Delete() ;						// out_Queue
	void Append(Node* value) ;				// In__Queue				
	bool IsEmpty() const ;					// is empty ?
	bool IsFull()  const ;					// is full ?
private:
	int front ;								// front
	int rear  ;								// rear
	enum { MAX_SIZE = 500 } ;				// Notice:remember ; at the end
	Node* element[MAX_SIZE] ;				// implement with array
} ;

Queue::Queue() : front(0), rear(0) {}

Node* Queue::GetValue() const
{
	if ( IsEmpty() )
	{
		cout << "The queue is empty!" << endl << endl ;
		return 0 ;
	}

	int temp = front ;
	return element[++temp] ;		
}

void Queue::Append(Node* value)
{
	if ( IsFull() )
	{
		cout << "The queue is full!" << endl << endl ;
		return ;
	}

	rear = (rear+1) % MAX_SIZE ;
	element[rear] = value ;
}

Node* Queue::Delete()
{
	if ( IsEmpty() )
	{
		cout << "The queue is empty!" << endl << endl ;
		return 0 ;
	}

	//return element[(++front) % MAX_SIZE] ;					// different from the next sentence??
	front = (front+1) % MAX_SIZE ;
	return element[front] ;
}

bool Queue::IsEmpty() const						
{
	return (rear == front) ;
}

bool Queue::IsFull()  const
{
	return ( (rear+1) % MAX_SIZE == front ) ;
}

/*--------------------------------------Class Queue---------------------------------END---------------------*/


/*--------------------------------------GLOBAL VARIABLE-----------------------------START-------------------*/
Node* TAG = (Node*)10000 ;
const int ROW = 80 ;
const int COL = 80 ;
char a[ROW][COL] ;
Node *RFPrint = NULL ;	// root_for_print
/*--------------------------------------GLOBAL VARIABLE-----------------------------END---------------------*/

void operator <<(ostream os, Node node)		//-------------- output a node directly ----------------------
{
	os << node.c << " " ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Add_New_Node
** Parameters    : Node **root
**               : Node *temp	(any node)
** Return Value  : void
** Details       : add a new node into a binary search tree
**--------------------------------------------------------------------------------------------------------*/
void Add_New_Node(Node **root, Node *temp)
{
	if (*root == NULL)
	{
		*root = temp ;
		return ;
	}

	if ( temp->c < (*root)->c )
		root = &( (*root)->L_Child ) ;
	else
		root = &( (*root)->R_Child ) ;

	Add_New_Node(root, temp) ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Print
** Parameters    : Node *root	(the root of a binary tree)
**				   int x		(x coordinate of the certain node)
**				   int y		(y coordinate of the certain node)
** Return Value  : void
** Details       : print the architecture to a table
**--------------------------------------------------------------------------------------------------------*/
void Print(Node *r, int x, int y)		// r==root, a=arry, x=coordinate x, y=coordinate y
{
	Queue queue ;
	static Queue *q = &queue ;

	if (r == NULL)
		return ;

	q->Append(r) ;					

	while (q->IsEmpty() == false)
	{
		Node *temp = q->Delete() ;
		a[x][y] = temp->c ;

		if (temp->L_Child)
			a[x+1][y-1] = '/' ;
		if (temp->R_Child)
			a[x+1][y+1] = '\\' ;

		if (temp->L_Child)
			q->Append(temp->L_Child) ;
		if (temp->R_Child)
			q->Append(temp->R_Child) ;
	}
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Get_Node_Rank
** Parameters    : Node *root	(the root of a binary tree)
**				   Node *recent	(the recent node to be disposed)
** Return Value  : void
** Details       : get the rank of a certain node in the binary tree
**				   root : 1
**				   .... : 2
**				   .... : 3
**				   .... : 4 
**				   ........
**--------------------------------------------------------------------------------------------------------*/
int Get_Node_Rank(Node *root, Node *recent)
{
	bool found = false ;
	int count = 0 ;
	Stack s(100) ;					// the stack may be used

	while (root)
	{
		s.Push(root) ;
		if ( s.GetTopValue() == recent )
		{
			found = true ;
			break ;
		}
		else
			root = root->L_Child ;

		if (root == NULL)
		{
			Node *temp = s.GetTopValue() ;
			s.Push(TAG) ;
			root = temp->R_Child ;
			if (root == NULL)
			{
				while (true)
				{
					if (s.GetTopValue() == TAG)
					{	
						s.Pop() ;	
						s.Pop() ;	
					}
					else
					{	
						if (s.GetTopValue() == NULL)
							cout << "Null Pointer Exists..." << endl << endl ;
						root = ( s.GetTopValue()) ->R_Child ;
						if (root == NULL)
						{
							s.Pop() ;
							continue ;
						}
						else
						{
							s.Push(TAG) ;
							break ;
						}
					}
				}
			}
		}
	}

	if (found)
	{
		while (s.IsEmpty() == false)
		{
			if (s.Pop() != TAG)
				count ++ ;
		}
	}
	else
		return 0 ;

	return count ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Print_Tree
** Parameters    : Node *root	(the root of a binary tree)
**				   int x		(x coordinate of the certain node)
**				   int y		(y coordinate of the certain node)
** Return Value  : void
** Details       : print the architecture to the screen(through a table)
**--------------------------------------------------------------------------------------------------------*/
void Print_Tree(Node *r, int x, int y)
{
	int num = ( Get_Node_Rank(RFPrint, r) <= 7 ? (8-Get_Node_Rank(RFPrint,r)) : 1 ) ;
	a[x][y] = r->c ;
	for (int i=1; i<=num; i++)
	{
		if (r->L_Child)
			a[x+i][y-i] = '/' ;
		if (r->R_Child)
			a[x+i][y+i] = '\\' ;
	}

	if (r->L_Child)
	{
		Print_Tree(r->L_Child, x+(num+1), y-(num+1)) ;
	}
	if (r->R_Child)
	{
		Print_Tree(r->R_Child, x+(num+1), y+(num+1)) ;
	}
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Init_Table
** Parameters    : NULL
** Return Value  : void
** Details       : initialize all the elements of the table with NULL character
**--------------------------------------------------------------------------------------------------------*/
void Init_Table()
{
	for (int i=0; i<ROW; i++)					// initialize the char table
		for (int j=0; j<COL; j++)
			a[i][j] = ' ' ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Print_Table
** Parameters    : NULL
** Return Value  : void
** Details       : print the table to the screen
**--------------------------------------------------------------------------------------------------------*/
void Print_Table()
{
	for (int i=0; i<ROW; i++)						// print the tree
		for (int j=0; j<COL; j++)
			cout << a[i][j] ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Build_BSTree
** Parameters    : Node **root		
** Return Value  : void
** Details       : Build a binary search tree
**--------------------------------------------------------------------------------------------------------*/
void Build_BSTree(Node **root)
{
	while (true)
	{
		char c = 0 ;
		cout << "Another Node ? (Y/N) " ;
		cin  >> c;

		if (c != 'n' && c != 'N')
		{
			Node *temp = new Node() ;
			cout << "Please Enter The Value : " ;
			cin  >> temp->c ;
			temp->L_Child = temp->R_Child = NULL ;

			Add_New_Node(root, temp) ;
		}
		else
			break ;
	}
}

/*--------------------------------------------------------------------------------------------------------
** Function Name : Leftest
** Parameters    : Node *r	
** Return Value  : Node*
** Details       : find the leftest node of a node
**--------------------------------------------------------------------------------------------------------*/
Node* Leftest(Node *r)
{
	if (r == NULL)
		return NULL ;

	while (r)
	{
		if (r->L_Child == NULL)
			return r ;
		else
			r = r->L_Child ;
	}

	return r ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Find_A_Node
** Parameters    : const Node *root			(security)
** Return Value  : char value				
** Details       : find a node of the certain value, the node is the leftest node that has the value 
**--------------------------------------------------------------------------------------------------------*/
const Node* Find_A_Node(const Node *root, char value)
{
	if (root == NULL)
		return NULL ;

	if (value == root->c)
		return root ;
	else if(value < root->c)
		Find_A_Node(root->L_Child, value) ;
	else
		Find_A_Node(root->R_Child, value) ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Find_All_Nodes
** Parameters    : const Node *root			(security)
** Return Value  : char value				
** Details       : find all the nodes that has the certain value from a binary search tree 
**--------------------------------------------------------------------------------------------------------*/
void Find_All_Nodes(const Node *root, char value)
{
	const Node *r = Find_A_Node(root, value) ;

	if ( r == NULL )
		cout << "No Such Data Was Founded!" << endl << endl ;
	else
	{
		while (r != NULL && r->c == value)
		{
			cout << "Find Value : " << r->c << endl ;
			r = Leftest(r->R_Child) ;
		}
	}
}


int main()
{
	char c ;									// store the value that user entered
	Node *root = NULL ;							

	Build_BSTree(&root) ;						// build the Binary Search Tree

	/*---------------------------------- Print The Tree ----------------------------------*/
	Init_Table() ;
	RFPrint = root ;
	Print_Tree(root, 0, 40) ;				
	Print_Table() ;
	/*---------------------------------- Print The Tree ----------------------------------*/

	while (true)
	{
		cout << "\n\nPlease Enter The Value You Want To Find : " ;
		cin  >> c ;
		Find_All_Nodes(root, c) ;
	}

	return 0 ;
}




/********************************************************************************
*
* Notice : This Program Can Be Launched In VC6.0 Environment
*
********************************************************************************/