//定義類中的成員函數，文件名為tree.cpp
#include<iostream>
#include<string>
#include"tree.h"
using namespace std;
/*
 *前置條件：樹不存在
 *輸    入：無
 *功    能：構造一棵樹
 *輸    出：無
 *后置條件：產生一棵樹 
 */

template<class T>
Tree<T>::Tree( )
{
	const int MaxSize = 100;
    int end = 0;
	int front = 0;
	int rear  = 0;  //采用順序隊列，并假定不會發生上溢
	int j = 0;	
	TNode<T>* queue[MaxSize]; //聲明一個隊列 
	TNode<T>* tempNode;              //聲明指向結點類型的指針  
	TNode<T>* brotherNode;   //工作指針
    TNode<T>* q;
	T ch;
    cout<<"請輸入創建一棵樹的根結點數據"<<endl;
	cin>>ch;
    root = new TNode<T>;
	root->data = ch;
	root->firstchild = NULL;
	root->rightsib = NULL;
    queue[rear++] = root;  
    while (!end)    //若繼續創建樹
	{ 
		T ch1,ch2;
		cout<<"請輸入創建一棵樹的父結點數據和孩子結點數據"<<endl;
		cin>>ch1>>ch2;
		TNode<T>* p = new TNode<T>;       //生成一個結點
		p->data = ch2;
		p->firstchild = NULL;    
		p->rightsib = NULL; 
        queue[rear++] = p;
		tempNode = queue[front];//頭結點出隊，同時對頭元素的標識符后移           			
		while(ch1 != tempNode->data)  		
			tempNode = queue[front++];											
		if(tempNode->firstchild == NULL)	tempNode->firstchild = p;
		else{
			brotherNode = tempNode->firstchild;  //工作指針指向結點的第一個孩子
			while (brotherNode != NULL)          //若第一個孩子有兄弟結點
			{
				q = brotherNode;
				brotherNode = brotherNode->rightsib;//工作指針指向第一個孩子的右兄弟				
			}            
			q->rightsib = p;			        
		}
		cout<<"創建結束? 如果結束請按1否則請按0 "<<endl;
		cin>>end;
	}
}
/*
 *前置條件：樹已存在
 *輸    入：無
 *功    能：釋放樹中各結點的存儲空間
 *輸    出：無
 *后置條件：樹不存在 
 */
template<class T>
Tree<T>::~Tree(void)
{
	Release(root);
}
/*
 *前置條件：樹已存在
 *輸    入：無
 *功    能：獲取指向樹根結點的指針
 *輸    出：指向樹根結點的指針
 *后置條件：樹不變 
 */
template<class T>
TNode<T>* Tree<T>::Getroot( )
{
	return root;
}
/*
 *前置條件：樹已存在
 *輸    入：無
 *功    能：前序遍歷樹
 *輸    出：樹中結點的一個線性排列
 *后置條件：樹不變 
 */
template<class T>
void Tree<T>::PreOrder(TNode<T> *root)      //前序遍歷樹
{
	if (root == NULL)  return;     //遞歸調用的結束條件
	else{		
		cout<<root->data;          //打印根節點
		PreOrder(root->firstchild);    //前序遞歸遍歷root的第一個孩子
		PreOrder(root->rightsib);    //前序遞歸遍歷root的右兄弟  
	}
}
/*
 *前置條件：樹已存在
 *輸    入：無
 *功    能：后序遍歷樹
 *輸    出：樹中結點的一個線性排列
 *后置條件：樹不變 
 */
template<class T>
void Tree<T>::PostOrder(TNode<T> *root)
{ 
	if (root == NULL)  return;     //遞歸調用的結束條件
	else{		
		PostOrder(root->firstchild);    //后序遞歸遍歷root的第一個孩子
        cout<<root->data;               //打印出root結點
		PostOrder(root->rightsib);      //后序遞歸遍歷root的右兄弟        
	}
} 
/*
 *前置條件：樹已存在
 *輸    入：無
 *功    能：層序遍歷樹
 *輸    出：樹中結點的一個線性排列
 *后置條件：樹不變
 */
template<class T>
void Tree<T>::LeverOrder(TNode<T> *root)   
{		
	const int MAX_QUEUE_SIZE = 100;
	int front = 0;
	int rear  = 0;  //采用順序隊列，并假定不會發生上溢		
	TNode<T>* queue[MAX_QUEUE_SIZE]; //聲明一個隊列 
	TNode<T>* tempNode;      //聲明指向結點類型的指針  
	TNode<T>* brotherNode;   //工作指針

	if (root == NULL) return;//循環結束條件
	queue[rear++] = root;    //否則結點入隊
	while (front != rear)    //若隊列中有結點
	{
		tempNode = queue[front++];//頭結點出隊，同時對頭元素的標識符后移
		cout<<tempNode->data;     //打印出頭結點    
		brotherNode = tempNode->firstchild;  //工作指針指向結點的第一個孩子
		while (brotherNode != NULL)          //若第一個孩子有兄弟結點
		{
			queue[rear++] = brotherNode;     //第一個孩子結點入隊
			brotherNode = brotherNode->rightsib;//工作指針指向第一個孩子的右兄弟
		}
	}
}
/*
 *前置條件：樹已經存在
 *輸    入：無
 *功    能：釋放樹的存儲空間，析構函數調用
 *輸    出：無
 *后置條件：樹不存在
 */
template <class T>
void Tree<T>::Release(TNode<T>* root)
{
	if (root != NULL){ 	
		Release (root->firstchild);   //釋放第一個孩子
		Release (root->rightsib);   //釋放右兄弟
        delete root;
	}
}