数据结构实现－二叉树.txt

包括数据结构中的常见的排序

/******************************************************************************************************
** Program Name : correlative operations of BTree
** 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 Position------------------------------START-------------------*/
class Position
{
public:
	Node *node ;
	int pos ;
	Position() : node(NULL), pos(LEFT) {} 
	Position(Node *n, int p) : node(n), pos(p) {}
} ;
/*--------------------------------------Class Position------------------------------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 << " " ;
}

int max(int a, int b)						//-------------- return the maximum of two values ------------
{
	return ( a > b ? a : b ) ;
}

/*--------------------------------------------------------------------------------------------------------
** Function Name : Pre_Order
** Parameters    : Node *root	(the root of a binary tree)
** Return Value  : void
** Details		 : all the nodes of a binary tree will be printed in PreOrder by RECURSION
**--------------------------------------------------------------------------------------------------------*/
void Pre_Order(Node *root)			// the recursive function
{
	if (root == NULL)				// the end condition for recursion
		return ;

	cout << (*root) ;				// print the node 

	Pre_Order(root->L_Child) ;		// dispose the left  node 
	Pre_Order(root->R_Child) ;		// dispose the right node
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Pre_Order2
** Parameters    : Node *root	(the root of a binary tree)
**				   Stack *s		(the stack used)
** Return Value  : void
** Details		 : 1> print all the nodes of a binary tree in Pre_Order
**				   2> NON-REVISION
**                 3> use a stack
**--------------------------------------------------------------------------------------------------------*/
void Pre_Order2(Node *root)	// the function without recursion
{
	Stack* s = new Stack(100) ;

	while (root)
	{
		cout << (*root) ;				// print the node first

		if (root->R_Child)				// push the right node
			s->Push(root->R_Child) ;

		if (root->L_Child)				// if left child exists, dispose it in the same way
			root = root->L_Child ;
		else							// if left child no exists, pop the proper right node to dispose
			root = s->Pop() ;
	}
	
	delete s ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Mid_Order
** Parameters    : Node *root	(the root of a binary tree)
** Return Value  : void
** Details		 : all the nodes of a binary tree in MidOrder by RECURSION
**--------------------------------------------------------------------------------------------------------*/
void Mid_Order(Node *root)			// the recursive function
{
	if (root == NULL)				// the end condition for recursion
		return ;

	Mid_Order(root->L_Child) ;		// dispose the left  node
	cout << (*root) ;				// print the node
	Mid_Order(root->R_Child) ;		// dispose the right node
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Mid_Order2
** Parameters    : Node *root	(the root of a binary tree)
**				   Stack *s		(the stack used)
** Return Value  : void
** Details		 : 1> print all the nodes of a binary tree in Mid_Order
**				   2> NON-RECURSION
**                 3> use a stack
**--------------------------------------------------------------------------------------------------------*/
void Mid_Order2(Node *r)
{
	Stack *s = new Stack(100) ;

	while ( r || s->IsEmpty() == false )
	{
		if (r)
		{
			s->Push(r) ;		// push the node
			r = r->L_Child ;
		} 
		else					// if no more node in the left
		{
			Node *temp = s->Pop() ;
			cout << (*temp) ;
			r = temp->R_Child ;	// after output the node, then visit the right node
		} 
	}
	
	delete s ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Pos_Order
** Parameters    : Node *root	(the root of a binary tree)
** Return Value  : void
** Details		 : all the nodes of a binary tree in PostOrder by RECURSION
**--------------------------------------------------------------------------------------------------------*/
void Pos_Order(Node *root)			// the recursive function
{
	if (root == NULL)				// the end condition for recursion
		return ;

	Pos_Order(root->L_Child) ;		// dispose the left  node
	Pos_Order(root->R_Child) ;		// dispose the right node
	cout << (*root) ;				// print the node
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Pos_Order2
** Parameters    : Node *root	(the root of a binary tree)
**				   Stack *s		(the stack used)
** Return Value  : void
** Details		 : 1> print all the nodes of a binary tree in Post_Order
**				   2> NON-RECURSION
**                 3> use a stack
**--------------------------------------------------------------------------------------------------------*/
void Pos_Order2(Node *r)
{
	Stack *s = new Stack(100) ;

	while ( r || s->IsEmpty() == false )		// end until the stack is empty
	{
		if (r)									// any node here thought as a middle node
		{
			s->Push(r) ;
			r = r->L_Child ;
		}
		else											// when the node has no left node, dispose it
		{
			if ( (s->GetTopValue())->R_Child == NULL)	// if has no right node
			{
				cout << ( *(s->Pop()) ) ;				// output the node directly
				/*-----------------------------------------------------------------------------------------
				* If s->GetTopValue() == TAG, indicates that the nodes in the right portion have been pushed
				* into the stack, so it can be pop directly, or indicates these nodes have not been pushed 
				* into the stack. The tag is just used to different from both cases.
				------------------------------------------------------------------------------------------*/
				while (s->GetTopValue() != NULL && s->GetTopValue() == TAG)
				{
					s->Pop() ;
					cout << ( *(s->Pop()) ) ;
				}
			} 
			else									// if it has right node
			{
				Node *temp = s->GetTopValue() ;
				s->Push(TAG) ;
				r = temp->R_Child ;
			}
		} 
	} // end while

	delete s ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Get_Node_Counts
** Parameters    : Node *root	(the root of a binary tree)
** Return Value  : int			(the total nodes of the binary tree)
** Details       : get total counts of nodes in a binary tree through the RECURSION way
**--------------------------------------------------------------------------------------------------------*/
int Get_Node_Counts(Node *r)		/* r = root */
{
	if (r == NULL)
		return 0 ;
	else
		return ( 1+ Get_Node_Counts(r->L_Child) + Get_Node_Counts(r->R_Child) );
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Get_Node_Counts2
** Parameters    : Node *root	(the root of a binary tree)
**				   Stack *s		(the stack used)
** Return Value  : int			(the total nodes of the binary tree)
** Details       : get total counts of the nodes in a binary tree through NON-RECURSION
**--------------------------------------------------------------------------------------------------------*/
int Get_Node_Counts2(Node *r)
{
	Stack *s = new Stack(100) ;
	int count = 0 ;

	while (r)
	{
		++ count ;
		if (r->R_Child)
			s->Push(r->R_Child) ;
		if (r->L_Child)
			r = r->L_Child ;
		else
			r = s->Pop() ;
	}

	delete s ;

	return count ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Get_Tree_Height
** Parameters    : Node *root	(the root of a binary tree)
** Return Value  : int			(the height of the binary tree)
** Details       : get the height of a binary tree in the way of recursion
**--------------------------------------------------------------------------------------------------------*/
int Get_Tree_Height(Node *r)
{
	if (r == NULL)
		return 0 ;
	else
		return ( 1+ max(Get_Tree_Height(r->L_Child), Get_Tree_Height(r->R_Child)) ) ;
}

/*--------------------------------------------------------------------------------------------------------
** 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 : Righest
** Parameters    : Node *r	
** Return Value  : Node*
** Details       : find the Rightest node of a node
**--------------------------------------------------------------------------------------------------------*/
Node* Rightest(Node *r)
{
	if (r == NULL)
		return NULL ;

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

	return r ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : BTree_To_List