/*--------------------------------------------------------
文件名:ThreadBinTree.h
作用：定義了線索二叉樹
作者：謝亞龍
創建日期：2008年5月23日
最后修改日期：2008年5月24日
--------------------------------------------------------*/
#ifndef _THREADBINTREE
#define _THREADBINTREE

#include "stdafx.h"
#include "ThreadBinTreeNode.h"
#include <stack>
#include <iostream>
using namespace std;

template <class Elem>
class ThreadBinTree
{
private:
	ThreadBinTreeNode<Elem>* root;//樹根節點
	void DeleteAll(ThreadBinTreeNode<Elem>* p)//刪除以p為根的子樹
	{
		if(!p)//如果p為空，返回
			return;
		DeleteAll(p->Left());//刪除p的左子樹
		DeleteAll(p->Right());//刪除p的右子樹
		delete p;//刪除p節點本身
	}

	ThreadBinTreeNode<Elem>* Create(Elem& ch)//供內部使用的建樹函數
	{
		//構建二叉樹，當輸入的為ch時，構建空二叉樹	
		Elem i;
		cin >> i;
		if(i != ch)
		{
			//如果輸入的不是結束標志，則表示繼續構造
			ThreadBinTreeNode<Elem>* temp = new ThreadBinTreeNode<Elem>(i);
			temp->SetLeft(Create(ch));		//構建左子樹
			temp->SetRight(Create(ch));		//構建右子樹
			return temp;						//返回根節點
		}
		return NULL;	//當得到的是結束符時，表示此子樹構建完成,返回空子樹
	}

	void InThread(ThreadBinTreeNode<Elem>* root,ThreadBinTreeNode<Elem>* &pre)
	{
		//供內部使用的中序線索化一棵二叉樹，root為該樹節點 pre為前驅節點
		if(root)//樹不為空
		{
			InThread(root->Left(),pre);//先線索化左子樹
			if(!root->Left())//左子樹為空
			{
				root->SetLeft(pre);//左指針指向其前驅
				if(pre)//前驅不為空
					root->LTag(true);
			}
			if( pre && !pre->Right())//前驅不為空 且 前驅的右子樹為空
			{
				pre->SetRight(root);//把前驅的 右指針指向root節點，作為pre的后繼
				pre->RTag(true);//改變右標記位的值
			}
			pre = root;
			InThread(root->Right(),pre);//再線索化右子樹
		}
	}

public:
	ThreadBinTree():root(NULL){};//缺省構造函數
	~ThreadBinTree()//析構函數
	{
		DeleteAll(root);
	}

	void CreateTree(Elem& ch)//供外部使用的建樹函數,ch是建樹結束符
	{
		//得到的樹的根賦值給 root就好了
		root = Create(ch);
//		InThread();//構建好樹之后 立即線索化
		InThreadWithStack();
	}

	ThreadBinTreeNode<Elem>* GetRoot()const//返回根節點
	{
		return root;
	}

	void InThread()//供外部使用的線索化二叉樹
	{
		ThreadBinTreeNode<Elem>* pre = NULL;//第一個前驅節點的值為空
		InThread(root,pre);//調用內部的線索化函數，以樹根為節點
	}

	void InOrder()//中序周游線索化二叉樹
	{
		if(!root)//為空樹
			return;
		ThreadBinTreeNode<Elem>* temp = root;
		while(temp->Left())//當temp->left沒指空時
			temp = temp->Left();
		while(1)
		{
			Visit(temp);//訪問的都是 最左節點
			if(!temp->Right())//如果temp右指針指空，則表示temp為線索化的最后的一個右節點的后繼
				return;
			if(temp->RTag())//為后繼，則按照后繼移動即可
				temp = temp->Right();
			else
			{
				temp = temp->Right();//上面的各步都是temp為左的情況
				while(!temp->LTag())//當左標記位表示為 左子節點時
					temp = temp->Left();
			}
		}
	}

	void Visit(ThreadBinTreeNode<Elem>* temp)//訪問當前節點
	{
		if(!temp)//為空節點
			return;
		cout << temp->GetValue() << " ";
	}

	void InThreadWithStack()//用非遞歸實現中序線索化二叉樹
	{
		if(!root)//為空樹
			return;
		ThreadBinTreeNode<Elem>* pre = NULL;//第一個前驅節點的值為空
		ThreadBinTreeNode<Elem>* temp = root;
		stack<ThreadBinTreeNode<Elem>*> s;
		while(temp != NULL || !s.empty())//當 當前節點不為空 或 棧不為空時循環
		{
			if(temp != NULL)//當前節點不為空
			{
				s.push(temp);//入棧
				temp = temp->Left();
			}
			else
			{
				temp = s.top();//的到棧頂元素的值
				if(pre && !pre->Right())//前驅不為空，且前驅的右指針為空時
				{
					pre->SetRight(temp);//得到 pre 的后繼節點為 當前節點
					pre->RTag(true);//改變標記位
				}
				s.pop();//棧頂元素出棧
				if(!temp->Left())//當彈出的元素的左指針為空
				{
					temp->SetLeft(pre);
					if(pre)//如果前驅指針不為空，則改變其左標記位
						temp->LTag(true);
				}
				pre = temp;
				temp = temp->Right();
			}
			
		}
	}


};

#endif