//********************************************************************////Binary_tree.cpp : implementation file for generating all the binary tree //The purpose of this C++ Program is to generate all the binary trees given the node number.//The basic idea is to evolve all the binary trees from the degenerate tree.//The algorithm is motivated by the parenthesis representation of binary trees.//The parenthesis set can be organized through lexicographical order. But the algorithm//in the code has not simply converted from parenthesis representation; instead//it has kept on shifting the last node from the latest binary tree to the next//possible left handside position(here we assume the degenerate tree is right handside).//This file has also computed the memory reference times(read/write) and avarage //reference times.////This program works in microsoft visual studio 2005 environment.////Author: ////Date: Oct18,2008//*********************************************************************//#include "Binary_tree.h"int main(){	cout<<"Generate the table from 2 to N node binary tree"<<endl;	cout<<"Please tell me the tree's node number:"<<endl;		cin>>Tree_Node_Num;		fout<<"(Node Num) ";	fout<<"(# of BinaryTree) ";	fout<<"(# of Memory Reference) ";	fout<<"(# of Average Memory Ref)"<<endl;	cout<<"(Node Num) ";	cout<<"(# of BinaryTree) ";	cout<<"(# of Memory Reference) ";	cout<<"(# of Average Memory Ref)"<<endl;	float aver;	for(int k=2;k<=Tree_Node_Num;k++)	{		REF = 0; counter = 1;		build_tree(k);		aver = (double)REF/(counter-1);		fout<<k<<setw(18)<<counter-1<<setw(18)<<REF<<setw(18)<<aver<<endl;		cout<<k<<setw(18)<<counter-1<<setw(18)<<REF<<setw(18)<<aver<<endl;		cout<<"-------------------------------------------------------------" <<endl;	}	system("pause");}// this function will build all the binary trees given the node number.void build_tree(int node_num){	int MostRight;	int parent;	bool flag = true;	build_first_tree(node_num);  // This function will generate the first degenerate binary tree;	counter++;	fout<<"-------------------------------------------------------------" <<endl;	MostRight = mostRightTree(root);		while(MostRight != 0)	{		// This function will find the next shiftable node's parent.		parent = findParent(MostRight);    		// Find the insert position of the shiftable node and insert it to this position.		findInsertPos(MostRight);        		////**************************************************************************//		//// the following region is to show all the generated binary trees;		//// For efficiency reason, they could be commented. The result has already been 		//// saved into a text file in the project's local directory.		//cout<<"This is Tree "<<counter<<" :"<<endl;		//for(int i=1;i<=Tree_Node_Num;i++)   		//	cout<<"L["<<i<<"]="<<lt[i]<<" , "<<"R["<<i<<"]="<<rt[i]<<endl;		//Convert2Binary(root);            // This function is to show the binary tree result.		//cout<<" Memory Reference: "<<REF<<endl;		//cout<<"\n---------------------------------" <<endl;		////**************************************************************************//				counter++;					MostRight = mostRightTree(root);   // Find the most right shiftable node.	}	}// This function will find the next shiftable node's parent.int findParent(int MostRight){	int parent;	int i;	for(i=1;i<=Tree_Node_Num;i++)	{		if(rt[i] == MostRight)		{							             REF++;						parent = i;		}	}	return parent;}// Find the insert position of the shiftable node// and insert it to this position.																		   void findInsertPos(int MostRight){	int parent;	int MostRight_temp;	int temp;	parent = findParent(MostRight);			     												 REF++; 	if(lt[parent] == 0) // the parent has empty left child	{                                            REF++; 		if(lt[MostRight] != 0) 		{			                                           			temp = getRightPos(parent);			rt[parent] = 0;                      REF++;			rt[temp] = lt[MostRight];            REF++;			lt[parent] = MostRight;              			temp = lt[MostRight];                   			// Transfer the left branch to the right sidewhile(lt[temp] != 0)			{                                    				rt[temp] = lt[temp];               REF++;				lt[temp] = 0;                      REF++;				temp = rt[temp];                 			}											       REF++;			lt[MostRight] = 0;                  		}		else		{			lt[parent] = MostRight;              			parent = findParent(MostRight);      			rt[parent] = 0;                      REF++;      		}													}	else if(lt[parent] != 0)	{                                           		//Former Wrong method:		//MostRight_temp = mostRightTree(lt[parent]);		//rt[MostRight_temp] = MostRight;  // here I have lost one case!		//Current correct method:        temp = lt[parent];                      		while(rt[temp] != 0)		{                                       			temp = rt[temp];                     REF++;               		}                                       		rt[temp] = MostRight;                    REF++;											     REF++;		if(lt[MostRight] != 0)		{                                       			temp = getRightPos(parent);    			rt[parent] = 0;                      REF++;			rt[temp] = lt[MostRight];            REF++;			temp = lt[MostRight];               			// Transfer the left branch to the right side			while(lt[temp] != 0)			{													rt[temp] = lt[temp];               REF++;				lt[temp] = 0;                      REF++;				temp = rt[temp];               			}                                      REF++;		}		else		{			rt[parent] = 0;                        REF++;		}		lt[MostRight] = 0;                      	}}int getRightPos(int parent){	int pos = root;	while(rt[pos] != 0)	{										    		if(parent == pos) 			break;		pos = rt[pos];                            REF++;               	}                                             REF++;	return pos;}// Find the most right shiftable node.int mostRightTree(int root){	int current_node = root;	int final_node = 0;	// Search the left 		while(lt[current_node] != 0 && rt[current_node] == 0)	{                                          REF++; REF++;		current_node = lt[current_node];       	}											   REF++; REF++;	// Search the most right	while(rt[current_node] != 0)	{		current_node = rt[current_node];       		final_node = current_node;		while(lt[current_node]!=0 && rt[current_node] == 0)		{											   REF++; REF++;															current_node = lt[current_node];    		}											   REF++; REF++;	}                                          	return final_node;}// This function will generate the first degenerate binary tree;void build_first_tree(int node_num){	int i;	for(i=1; i<node_num; i++)	{		lt[i] = 0;                              //REF++;                         		rt[i] = i+1;                            //REF++;	}	lt[node_num] = 0;                           //REF++;	rt[node_num] = 0;                           //REF++;}// This function is to show the binary tree result.void Convert2Binary(int currentNode){		if(currentNode==0)	{		if(s.empty()) return;		else		{			cout<<"0";				currentNode = s.top();			s.pop();			Convert2Binary(currentNode);		}	}	else	{		cout<<"1";		s.push(rt[currentNode]);               		currentNode=lt[currentNode];           		Convert2Binary(currentNode);            	}}