// ThreadBinaryTree.h: interface for the ThreadBinaryTree class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_THREADBINARYTREE_H__73E5ADE5_F47C_463B_B199_91EE62DE38D6__INCLUDED_)
#define AFX_THREADBINARYTREE_H__73E5ADE5_F47C_463B_B199_91EE62DE38D6__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include "ThreadBinaryTreeNode.h"

template <class T>
class ThreadBinaryTree  
{
private:
	ThreadBinaryTreeNode<T>* root;						//根結點指針
public:
	ThreadBinaryTree(){	root=NULL;};					//構造函數
	virtual ~ThreadBinaryTree(){DeleteTree(root);};
	ThreadBinaryTreeNode<T>* getRoot(){return root;};	//返回根結點指針
	//以element作為根結點，leftTree作為樹的左子樹，rightTree作為樹的右子樹，構造一棵新的二叉樹
	void CreateTree(const T& elem, ThreadBinaryTree<T>& leftTree, ThreadBinaryTree<T>& rightTree);
	//刪除二叉樹或其子樹
	void DeleteTree(ThreadBinaryTreeNode<T>* root);
	//對稱序線索化二叉樹
	void InThread(ThreadBinaryTreeNode<T>* root);
	//遞歸對稱序線索化二叉樹
	void InThread(ThreadBinaryTreeNode<T>* root,ThreadBinaryTreeNode<T>* &pre);
	//對稱序周游
	void InOrder(ThreadBinaryTreeNode<T>* root);
	//在對稱序穿線樹中找指定結點在前序下的后繼
	ThreadBinaryTreeNode<T>* FindNextinInorderTree(ThreadBinaryTreeNode<T>* pointer);
	//往對稱序穿線樹里插入一個新結點
	void InsertNode(ThreadBinaryTreeNode<T>*pointer,ThreadBinaryTreeNode<T>* newpointer);
};

template <class T>
void ThreadBinaryTree<T>::CreateTree(const T& elem, ThreadBinaryTree<T>& leftTree, ThreadBinaryTree<T>& rightTree)
{
	root=new ThreadBinaryTreeNode<T>(elem,leftTree.root,0,rightTree.root,0);//創建新樹
	leftTree.root=rightTree.root=NULL;							//原來兩棵子樹的根結點指空，避免訪問

}

template <class T>
void ThreadBinaryTree<T>::DeleteTree(ThreadBinaryTreeNode<T>* root)//刪除二叉樹或其子樹
{
	if(root)
	{
		if(root->lTag==0)
			DeleteTree(root->left);
		if(root->rTag==0)
		DeleteTree(root->right);
		delete root;
	}
	else
		delete root;
}

template <class T>
void ThreadBinaryTree<T>::InThread(ThreadBinaryTreeNode<T>* root,ThreadBinaryTreeNode<T>* &pre)
//遞歸對稱序線索化二叉樹
{
	if(root!=NULL)
	{
		//中序線索化左子樹
		InThread(root->leftchild(),pre);
		if(root->leftchild()==NULL)
		{
		//建立前驅線索
			root->left=pre;			
			root->lTag=1;
		}
		if((pre)&&(pre->rightchild()==NULL))
		{
		//建立后繼線索
			pre->right=root;
			pre->rTag=1;
		}
		pre=root;
		//中序線索化右子樹
		InThread(root->rightchild(),pre);
	}
}

template <class T>
void ThreadBinaryTree<T>::InThread(ThreadBinaryTreeNode<T>* root)//對稱序線索化二叉樹
//對稱序線索化二叉樹
{
	//初始化
	using std::stack;
	stack<ThreadBinaryTreeNode<T>*> aStack;
	ThreadBinaryTreeNode<T>* pointer=root;
	ThreadBinaryTreeNode<T>* temppointer=NULL;		//遞歸對稱序線索化二叉樹
	//訪問一個結點，必要時建立線索
	while(1)
	{
		while(NULL!=pointer)
		{
			aStack.push(pointer);
			pointer=pointer->leftchild();			//沿左子樹方向下降
		}
		if(aStack.empty())							//棧空，算法結束
			return;
		else
		{
			pointer=aStack.top();
			aStack.pop();
			if(NULL!=temppointer)
			{
				if(NULL==temppointer->right)
				{
					temppointer->rTag=1;
					temppointer->right=pointer;		//確定中序后繼
				};
				if(NULL==pointer->left)
				{
					pointer->lTag=1;
					pointer->left=temppointer;		//確定中序前驅
				}
			}
			temppointer=pointer;
			pointer=pointer->rightchild();			//轉向二叉樹的右子樹
		}
	}
}

template <class T>
void ThreadBinaryTree<T>::InOrder(ThreadBinaryTreeNode<T>* root)//對稱序周游
{
	ThreadBinaryTreeNode<T>* pointer;
	//是否為空二叉樹
	if(root==NULL)
		return;
	else pointer=root;
	//找“最左下”結點
	while(pointer->leftchild()!=NULL)
		pointer=pointer->leftchild();
	//訪問當前結點并找出當前結點的對稱序后繼
	while(1)
	{
		AfxMessageBox(pointer->value());			//訪問當前結點
		if(pointer->rightchild()==NULL)
			return;
		if(pointer->rTag==1)
			pointer=pointer->rightchild();
		else
		{
			pointer=pointer->rightchild();
			while(pointer->lTag==0)
				pointer=pointer->leftchild();
		}
	}
}

template <class T>
ThreadBinaryTreeNode<T>* ThreadBinaryTree<T>::FindNextinInorderTree(ThreadBinaryTreeNode<T>* pointer)		
//在對稱序穿線樹中找指定結點在前序下的后繼
{
	ThreadBinaryTreeNode<T>* temppointer=NULL;
	if(pointer->lTag==0)
		return pointer->leftchild();
	else
		temppointer=pointer;
	while(temppointer->rTag==1)
		temppointer=temppointer->rightchild();
	temppointer=temppointer->rightchild();
	return temppointer;
}

template <class T>
void ThreadBinaryTree<T>::InsertNode(ThreadBinaryTreeNode<T>*pointer,ThreadBinaryTreeNode<T>* newpointer)
//往對稱序穿線樹里插入一個新結點
{
	ThreadBinaryTreeNode<T>* temppointer=NULL;
	//找指定結點的對稱序后繼
	if(pointer->rightchild()==NULL)
		temppointer=NULL;
	else if(pointer->rTag==1)
			temppointer=pointer->rightchild();
		 else
		 {
			temppointer=pointer->rightchild();
			while(temppointer->lTag==0)
				temppointer=temppointer->leftchild();
		 }
	//temppointer指針指向pointer結點的對稱序后繼
	//建立指定結點的對稱序后繼的左線索
	if((temppointer!=NULL)&&(temppointer->lTag==1))
		temppointer->left=newpointer;
	//建立新結點的右指針或右線索
	newpointer->rTag=pointer->rTag;
	newpointer->right=pointer->rightchild();
	//插入新結點
	pointer->rTag=0;
	pointer->right=newpointer;
	//建立新結點左線索
	newpointer->lTag=1;
	newpointer->left=pointer;
}

#endif // !defined(AFX_THREADBINARYTREE_H__73E5ADE5_F47C_463B_B199_91EE62DE38D6__INCLUDED_)