strahler_num2.cpp

这个课程项目计算了strahler number； 这个很有利于理解二叉树和链表。

#include<fstream>
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <iostream>
#include <fstream>
#include <iomanip>

#include <stack>
#include <deque>
std::stack<int> s;
std::stack<int> f;
std::deque<int> q;
using namespace std;
#define MaximumNode 50
#define LENGTH sizeof(struct record)
ofstream fout("table_strahler_pruning.txt");

void showTree(void);
void build_tree(int);
void Convert2Binary(int);
void Convert2Forest();
void build_first_tree(int);
int mostRightTree(int);
void findInsertPos(int);
int findParent(int);
int* findTreeParent(int, int [][MaximumNode]);
bool testFinal(void);
int getRightPos(int);
int Strahler(int);
int Pruning(int [][MaximumNode]);

int lt[MaximumNode];
int rt[MaximumNode];
int Strahler_Num[MaximumNode];
int forest[MaximumNode][MaximumNode];

int Tree_Node_Num;
int counter = 1;
int root = 1;
int REF = 0;
int pruning_num;
int Total_Strahler = 0;
int Total_Pruning = 0;

int Global_Pruning_Counter[15][MaximumNode];
int Global_Strahler_Counter[15][MaximumNode];


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 BinaryTrees ";
	//fout<<" # of Memory Reference  ";
	//fout<<" # of average Memoery Reference";
	//fout<<" # Strahler";
	//fout<<" # Pruning"<<endl;
	double aver = 0;
	int Global_Counter;
	cout<<"Possible Number";
	fout<<"Possible Number";
	cout<<"        1 ";
	fout<<"        1 ";
	cout<<"        2 ";
	fout<<"        2 ";
	cout<<"        3 ";
	fout<<"        3 ";
	cout<<"        4 ";
	fout<<"        4 ";
	cout<<"      5 ";
	fout<<"      5 ";
	cout<<"      6 ";
	fout<<"      6 ";
	cout<<"      7 "<<endl;
	fout<<"      7 "<<endl;
	cout<<"(Strahler/Pruning):"<<endl;
	fout<<"(Strahler/Pruning):"<<endl;
	cout<<"-------------------------------------------------------------------------"<<endl;
	fout<<"-------------------------------------------------------------------------"<<endl;
	for(int k=2;k<=Tree_Node_Num;k++)
	{
		REF = 0; 
		counter = 1;
		Total_Strahler = 0;
		Total_Pruning = 0;

		
     	//aver = (double)REF/(counter-1);
		for(int j=0; j < MaximumNode; j++)
		{
			Global_Pruning_Counter[k-2][j] = 0;
			Global_Strahler_Counter[k-2][j] = 0;
		}
		//fout<<k<<setw(15)<<counter-1<<setw(15)<<REF<<setw(15)<<aver<<setw(15)<<Total_Strahler<<setw(15)<<Total_Pruning<<endl;			
		//fout<<k<<setw(15)<<counter-1<<setw(15)<<Total_Strahler<<setw(15)<<Total_Pruning<<endl;	
		build_tree(k);

		Global_Counter = 1;
		cout<<"Node Number: "<<k<<endl;
		fout<<"Node Number: "<<k<<endl;
		cout<<"Strahler Number:       ";
		fout<<"Strahler Number:       ";
		while(Global_Strahler_Counter[k-2][Global_Counter] != 0)
		{
			
			cout<<Global_Strahler_Counter[k-2][Global_Counter]<<setw(10);
			fout<<Global_Strahler_Counter[k-2][Global_Counter]<<setw(10);
			Global_Counter++;
		}
		cout<<endl;
		fout<<endl;
		Global_Counter = 1;
		cout<<"Pruning Number:        ";
		fout<<"Pruning Number:        ";
		while(Global_Pruning_Counter[k-2][Global_Counter] != 0)
		{
			
			cout<<Global_Pruning_Counter[k-2][Global_Counter]<<setw(10);
			fout<<Global_Pruning_Counter[k-2][Global_Counter]<<setw(10);
			Global_Counter++;
		}
		cout<<endl;
		fout<<endl;
		cout<<"-------------------------------------------------------------------------"<<endl;
		fout<<"-------------------------------------------------------------------------"<<endl;
	}
	//exit(0);	
	system("pause");
}

void build_tree(int node_num)
{
	int MostRight;
	int parent;
	bool flag = true;
	int strahler_root;
	build_first_tree(node_num);
	//cout<<counter++<<endl;
	counter++;
	Convert2Binary(root);	
	
	for(int i = 1; i<=Tree_Node_Num+1;i++)
	{
		Strahler_Num[i] = 0;
		for(int j = 1; j<=Tree_Node_Num+1;j++)
			forest[i][j] = 49;
	}
	Convert2Forest();
	strahler_root = Strahler(root);
    Total_Strahler = Total_Strahler + strahler_root;
	Global_Strahler_Counter[node_num-2][strahler_root] = Global_Strahler_Counter[node_num-2][strahler_root] + 1;

	pruning_num = 0;
	pruning_num = Pruning(forest);
	Total_Pruning = Total_Pruning  + pruning_num;
	Global_Pruning_Counter[node_num-2][pruning_num] = Global_Pruning_Counter[node_num-2][pruning_num]+1;

	//fout<<"------------------------------------------------------------------------------" <<endl;
	MostRight = mostRightTree(root);	
	while(MostRight != NULL)
	{
	
		parent = findParent(MostRight);
		findInsertPos(MostRight);
		//cout<<counter<<endl;
		//fout<<counter++<<endl;
		counter++;
		Convert2Binary(root);	
		
		for(int i = 1; i<=Tree_Node_Num+1;i++)
		{
			Strahler_Num[i] = 0;
			for(int j = 1; j<=Tree_Node_Num+1;j++)
				forest[i][j] = 49;
		}

		Convert2Forest();
		strahler_root = Strahler(root);
		Global_Strahler_Counter[node_num-2][strahler_root] = Global_Strahler_Counter[node_num-2][strahler_root] + 1;

		Total_Strahler = Total_Strahler + strahler_root;
		pruning_num = 0;
		pruning_num = Pruning(forest);
		Global_Pruning_Counter[node_num-2][pruning_num] = Global_Pruning_Counter[node_num-2][pruning_num]+1;
		Total_Pruning = Total_Pruning  + pruning_num;
		MostRight = mostRightTree(root);
	}	
}
//This function is useless at last, since algorithm can be stopped by NULL returned 
//most right node;
bool testFinal()
{
	bool flag_temp = true;
	int local_counter = 0;
	int i=1;
	while(local_counter<Tree_Node_Num && i != 0)
	{
		if(lt[i]!=0 &&rt[i]==0)
		{										
												
            local_counter++;
		}		
		i = lt[i];								
	}
	if(local_counter == Tree_Node_Num-1)
		flag_temp = false;
	return flag_temp;
}
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;
}
void findInsertPos(int MostRight)
{
	int parent;
	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;
}

int mostRightTree(int root)
{
	int current_node = root;
	int final_node = NULL;
	// 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;
}
void build_first_tree(int node_num)
{
	int i;
	for(i=1; i<node_num; i++)
	{
		lt[i] = 0;                                                      
		rt[i] = i+1;                            
	}
	lt[node_num] = 0;                           
	rt[node_num] = 0;                           
}

void Convert2Binary(int currentNode)
{	
	if(currentNode==0)
	{
		if(s.empty()) return;
		else
		{
			//cout<<"0";	
			q.insert(q.end(),0);
			currentNode = s.top();
			s.pop();
			Convert2Binary(currentNode);
		}
	}
	else
	{
		//cout<<"1";
		q.insert(q.end(),1);
//		q.enqueue(1);
		s.push(rt[currentNode]);               
		currentNode=lt[currentNode];           
		Convert2Binary(currentNode);            
	}
}


void Convert2Forest()
{	
	int currentNode = 1;
	int counter = 1;
	int temp,temp_old;
	if(q.empty())
		cout<<"This is a NULL tree!"<<endl;
	else
	{
		while(!q.empty())
		{
			temp = q.front();
			if(temp == 1)
			{			
				if(f.empty())
				{
					f.push(counter++);
					temp_old = q.front();
				}
				else
				{			
					temp_old = q.front();
					currentNode = f.top();
					int i = 1;
					while(forest[currentNode][i] != 49)
						i++;
					forest[currentNode][i] = counter;
					f.push(counter++);
				}
				
			}
			else if(temp == 0)
			{
				currentNode = f.top();				
				if(temp_old == 1)
				{
					int i = 1;
					while(forest[currentNode][i] != 49)
						i++;
					forest[currentNode][i] = 0;
					forest[currentNode][i+1] = 0;
				}
				else 
				{
						int i = 1;
						int counter_temp = 0;
						while(forest[currentNode][i] != 49)
						{
							i++;
							if(forest[currentNode][i]!=0)
								counter_temp++;

						}
						if(counter_temp == 1)
							forest[currentNode][i] = 0;
				}
				f.pop();
			}		
			temp_old = temp; // this is to judge the consecutive pair
			q.pop_front();
		}
	}
}

void showTree()
{
	for(int i=1;i<=Tree_Node_Num;i++)   
	{
		int j = 1;
		while(forest[i][j] != 49)
		{
		   cout<<"forest["<<i<<"]["<<j<<"]="<<forest[i][j++]<<setw(10);
		}
		cout<<endl;
	}
}

int Strahler(int currentNode)
{
	int strahler_left = 0;
	int strahler_right = 0;
	if(lt[currentNode] != 0)
		strahler_left = Strahler(lt[currentNode]);
	else
		strahler_left = 0;
	if(rt[currentNode] != 0)
		strahler_right = Strahler(rt[currentNode]);
	else
		strahler_right = 0;
	if(strahler_left != strahler_right)
		Strahler_Num[currentNode] = max(strahler_left, strahler_right);
	else
		Strahler_Num[currentNode] = strahler_left+1;
	return Strahler_Num[currentNode];
}

int Pruning(int tempForest[][MaximumNode])
{
	int local_counter1 = 1;
	int local_counter2;
	int leave_array[MaximumNode];
	bool flag = false;
	bool flag_temp = false;
	int* currentParent;
	int local_pruning = 1;
	int currentForest[MaximumNode][MaximumNode];
	int temp[MaximumNode][MaximumNode];

	for(int i=1; i<=Tree_Node_Num; i++)
	{
		for(int j=1; j<=Tree_Node_Num; j++)
		{
			currentForest[i][j] = tempForest[i][j];
			temp[i][j] = tempForest[i][j];
		}			
	}

	while(1)
	{
		for(int i=1; i<=Tree_Node_Num; i++)
		{
			int j = 1;
			while(j<=Tree_Node_Num)
			{
				if(currentForest[i][j] == 0)
					flag = true;
				else
					break;
				j++;
			}
			if(flag)		
			{
				leave_array[local_counter1++] = i;
				flag = false;
			}
		}

		
		for(int i=1; i<local_counter1; i++)
		{
			for(int j=1; j<Tree_Node_Num;j++)
				temp[leave_array[i]][j] = 50;
			currentParent = findTreeParent( leave_array[i],currentForest);
			while(currentParent != NULL){
					local_counter2 = 0;
					int j = 1;
					while(j<=Tree_Node_Num)
					{
						if(currentForest[*currentParent][j] != 0 && currentForest[*currentParent][j] != 49 && currentForest[*currentParent][j] != 50)
							local_counter2++;
						if(currentForest[currentParent[0]][j] == 49)
							break;
						j++;
					}
					temp[*currentParent][*(currentParent+1)] = 0;   // set zero but do not remove it now. 
					if(local_counter2 > 1)
						break;
					
					currentParent = findTreeParent(currentParent[0],currentForest);
					//delete []currentParent;

			}

		}
		for(int i=1; i<=Tree_Node_Num; i++)
		{
			int j = 1;
			int local_counter3 = 0;
			while(j<=Tree_Node_Num)
			{				
				if(currentForest[i][j] != 0 && currentForest[i][j] !=49 && currentForest[i][j] != 50)
					local_counter3++;// how many silibings in this node
				j++;
			}
			if(local_counter3 == 1)
			{
				int j = 1;
				while(j<=Tree_Node_Num)
				{				
					if(temp[i][j] == 0)
						temp[i][j] = 50;  // remove the node
					j++;
				}
			}
			else if(local_counter3 > 1)
				flag_temp = true;			
		}
		if(flag_temp)
		{
			local_pruning++;
			flag_temp = false;
		}
		else
			break;
				
		// copy the temp forest to current forest;
		for(int i=1; i<=Tree_Node_Num; i++)
		{
			for(int j=1; j<=Tree_Node_Num; j++)
			{
				currentForest[i][j] = temp[i][j];
			}			
		}

	}
	return local_pruning;
	//cout<<"The Pruning Number is:"<<local_pruning<<endl;
}

int* findTreeParent(int currentNode, int forest_temp[][MaximumNode])
{
	//int* parent;	
	//parent = new int[2];
	int parent[2];
	bool flag = false;
	int i;
	for(i=1;i<=Tree_Node_Num;i++)
	{
		for(int j=1; j<=Tree_Node_Num;j++)
		{
			if(forest_temp[i][j] == currentNode)
			{
				//parent = strcat(i,j);
				parent[0] = i;
				parent[1] = j;
				flag = true;
				break;
			}
		}
	}
	if(!flag)
		return NULL;
	else
		return parent;
}