binary_tree.cpp

Binary_tree.cpp ：执行文件生成所有二叉树 这样做的目的C + +程序是产生所有二叉树指定节点数目。 基本思想是衍生所有二叉树基于退化树。 该算法的动机是圆括号法则代表二叉

//********************************************************************//
//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 side
while(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);            
	}
}