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

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

** Parameters    : Node *r	(r == root)
** Return Value  : Node *	(return the header of the chain)
** Details       : the function transform a binary tree to a single chain (Mid_Order)
**--------------------------------------------------------------------------------------------------------*/
void Make_Links(Node *r)				// r = root
{
	if (r == NULL)
		return ;

	if (r->L_Child)
		Rightest(r->L_Child)->next = r ;
	if (r->R_Child)
		r->next = Leftest(r->R_Child) ;

	Make_Links(r->L_Child) ;
	Make_Links(r->R_Child) ;
}

Node* BTree_To_List(Node *r)
{
	Node *left = Leftest(r) ;
	Node *right = Rightest(r) ;
	Node *header = new Node('H') ;
	header->next = left ;
	right->next = NULL ;
	Make_Links(r) ;

	return header ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : List_Printer
** Parameters    : Node *header	(the header of a chain)
** Return Value  : void
** Details       : print all the nodes of the chain
**--------------------------------------------------------------------------------------------------------*/
void List_Printer(const Node *header)			// List_Printer
{
	const Node *recent = header ;

	while (recent)
	{
		cout << recent->c << " --> " ;
		recent = recent->next ;
		if (recent == NULL) 
			cout << "NULL" ;
	}

	cout << endl << endl ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Hierarchy_Travel
** Parameters    : Node *root	(the root of a binary tree)
**				   Queue *q		(the queue to be used)
** Return Value  : void
** Details       : the function travel a binary tree hierarchically by use a queue
**--------------------------------------------------------------------------------------------------------*/
void Hierarchy_Travel(Node *r)
{
	Queue *q = new Queue() ;

	if (r == NULL)
	{
		cout << "A NULL Tree!" << endl << endl ;
		return ;
	}

	/*--------------------------------------------------------------------------------
	** Details : First append the root to the queue, and then, after letting a node out
	**           from the queue, you must let its left child and its right child into 
	**           the queue.(Of course, on condition that it has child exists)
	**           Circle until no elements exist in the queue
	**--------------------------------------------------------------------------------*/
	q->Append(r) ;												

	while (q->IsEmpty() == false)
	{
		Node *temp = q->Delete() ;
		cout << (*temp) ;

		if (temp->L_Child)
			q->Append(temp->L_Child) ;
		if (temp->R_Child)
			q->Append(temp->R_Child) ;
	}

	delete q ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Find_Null_Node
** Parameters    : Node *root	(the root of a binary tree)
**				   Queue *q		(the queue to be used)
** Return Value  : Position		(the data structure has been defined)
** Details       : 1> The function are always used in a full binary tree
**				   2> It can find the first node whose left child or right child is NULL
**--------------------------------------------------------------------------------------------------------*/
Position Find_Null_Node(Node *r, Queue *q)
{
	if (r == NULL)						// if a binary tree is null, return NULL to indicate
		return Position(NULL, LEFT) ;

	if (q->IsEmpty() )
		q->Append(r) ;

	while (q->IsEmpty() == false)
	{
		Node *temp = q->GetValue() ;

		if (temp->L_Child == NULL)
			return Position(temp, LEFT) ;
		
		if (temp->R_Child == NULL)
			return Position(temp, RIGHT) ;
	

		q->Delete() ;

		if (temp->L_Child)
			q->Append(temp->L_Child) ;
		if (temp->R_Child)
			q->Append(temp->R_Child) ;
	}

	return Position(NULL, LEFT) ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Add_New_Node
** Parameters    : Position pos	(pos is a data structure, it contains a pointer of the node to be added and
**								 the direction [left or righ?] to be added)
**				   Queue *q		(the queue to be used)
**				   Node *node	(the node will be added to the full binary tree)
** Return Value  : void
** Details       : add a new node into a full binary tree
**--------------------------------------------------------------------------------------------------------*/
void Add_New_Node(Position pos, Node *node, Queue *q)
{
	if (pos.node == NULL)
	{
		cout << "Can't be added, the binary tree is empty!" ;
		return ;
	}

	if (pos.pos == LEFT)
		pos.node->L_Child = node ;
	else
		pos.node->R_Child = node ;
	

	q->Append(node) ;
}
/*--------------------------------------------------------------------------------------------------------
** 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] ;
}


int main()
{
	
	Node A = Node('A') ;
	Node B = Node('B') ;
	Node C = Node('C') ;
	Node D = Node('D') ;
	Node E = Node('E') ;
	Node F = Node('F') ;
	Node G = Node('G') ;
	Node H = Node('H') ;
	Node I = Node('I') ;
	Node J = Node('J') ;
	Node K = Node('K') ;
	Node L = Node('L') ;
	Node M = Node('M') ;
	Node N = Node('N') ;
	Node O = Node('O') ;
	Node P = Node('P') ;
	Node Q = Node('Q') ;

	A.L_Child = &B ;
	A.R_Child = &C ;
	B.L_Child = &D ;
	B.R_Child = &E ;
	C.L_Child = &F ;
	C.R_Child = &G ;
	D.L_Child = &H ;
	D.R_Child = &I ;
	E.L_Child = &J ;
	E.R_Child = &K ;
	F.L_Child = &L ;
	F.R_Child = &M ;
	G.L_Child = &N ;
	G.R_Child = &O ;
	H.L_Child = &P ;
	H.R_Child = &Q ;

	Node *root = &A ;
	
	cout << "------------------------------------------------------------------------------" << endl
		 << "Details : The Program Demenstrate The Correlative Operations Of A Binary Tree" << endl
		 << "Author  : Lu Jian Hua" << endl 
		 << "Time    : 2007-6-9"    << endl
		 << "------------------------------------------------------------------------------" << endl << endl ;

	Init_Table() ;
	RFPrint = root ;
	Print_Tree(root, 0, 40) ;					// print the tree to the char table
	Print_Table() ;

	cout << "The results of hierachy travel : " ;
	Hierarchy_Travel(root) ;					// hierarchy Travel
	cout << endl << endl ;


	cout << "The Quantity Of Nodes (With Recursion) : " << Get_Node_Counts(root)  << endl << endl
		 << "The Quantity Of Nodes (NO   Recursion) : " << Get_Node_Counts2(root) << endl << endl
		 << "The Height   Of Tree  (NO   Recursion) : "   << Get_Tree_Height(root)  << endl << endl
		 << "The Leftest  Node                      : " ;
	cout << Leftest(root)->c << endl << endl ;
	cout << "The Leftest  Node                      : " ;
	cout << Rightest(root)->c << endl << endl ;

	cout << "Pre Order With Recursion : " ;
	Pre_Order(root) ;		cout << endl << endl ;
	cout << "Pre Order No   Recursion : " ;
	Pre_Order2(root) ;		cout << endl << endl ;
	
	cout << "Mid Order With Recursion : " ;
	Mid_Order(root) ;	cout << endl << endl ;
	cout << "Mid Order No   Recursion : " ;
	Mid_Order2(root) ;	cout << endl << endl ;

	cout << "Pos Order With Recursion : " ;
	Pos_Order(root) ;	cout << endl << endl ;
	cout << "Pos Order No   Recursion : " ;
	Pos_Order2(root) ;	cout << endl << endl ;

	cout << "The Binary Tree Can Be Transformed Into A Single Chain ..." << endl << endl 
		 << "The Result As Follows : " << endl << endl ;
	List_Printer( BTree_To_List(root) ) ;

	cout << "----------------------------------------------------" << endl
		 << "         Now Will Build A Full Binary Tree          " << endl
		 << "----------------------------------------------------" << endl << endl ;

  
	Node r = Node('A');
	Queue q ;

	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( Find_Null_Node(&r, &q), temp, &q ) ;
		}
		else
			break ;
	}

	RFPrint = &r ;
	Init_Table() ;
	Print_Tree(&r, 0, 40) ;
	Print_Table() ;

	system("pause") ;
	return 0 ;
}




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