線索化二叉樹

      二叉樹是一種非線性結(jié)構(gòu)，遍歷二叉樹幾乎都是通過遞歸或者用棧輔助實現(xiàn)非遞歸的遍歷。用二叉樹作為存儲結(jié)構(gòu)時，取到一個節(jié)點，只

能獲取節(jié)點的左孩子和右孩子，不能直接得到節(jié)點的任一遍歷序列的前驅(qū)或者后繼。

     為了保存這種在遍歷中需要的信息，我們利用二叉樹中指向左右子樹的空指針來存放節(jié)點的前驅(qū)和后繼信息。

enum PointerTag

{

LINK,    //0

THREAD   //1

};

template <typename T>

struct BitreeNodeTH

{

T Data;

BitreeNodeTH<T> *left;   //左孩子

BitreeNodeTH<T> *right;  //右孩子

PointerTag left_Tag;   //左孩子線索標(biāo)志

PointerTag right_Tag;  //右孩子線索標(biāo)志

BitreeNodeTH(T data = T())

:Data(data)

,left(NULL)

,right(NULL)

,left_Tag(LINK)

,right_Tag(LINK)

{}

};

一個線索二叉樹的節(jié)點：

線索化二叉樹的主要源代碼：

建樹：

	BitreeNodeTH<T>* Create_tree(T *arr,int sz,int &i)
	{
		if(*arr==NULL||arr[i]=='#'||i>=sz)
			return NULL;
		else 
		{
			BitreeNodeTH<T> *cur=new BitreeNodeTH<T>;
			cur->Data=arr[i];
			i++;
			cur->left=Create_tree(arr,sz,i);
			i++;
			cur->right=Create_tree(arr,sz,i);
			return cur;
		}
	}

前序線索化：

	void FirstOrderTH(BitreeNodeTH<T>* root, BitreeNodeTH<T>* &prev)// &表示沒有開辟臨時變量
	{
		if (root == NULL)
			return;
		BitreeNodeTH<T>* cur = root;
	 	if (cur->left == NULL)
		{
			cur->left_Tag = THREAD;
			cur->left = prev;
		}
		if (prev&&prev->right == NULL)
		{
			prev->right_Tag = THREAD;
			prev->right = cur;
		}
		prev = cur;
		if (cur->left_Tag == LINK)   //cur->left
			FirstOrderTH(cur->left,prev);
		if(cur->right_Tag == LINK)   //cur->right
			FirstOrderTH(cur->right, prev);
	}

前序遍歷：

	void FirstOrderTHing(BitreeNodeTH<T>* root)
	{
		if (root == NULL)
			return;
		BitreeNodeTH<T>* cur = root;
		while (cur)
		{
			while(cur->left_Tag == LINK)
			{
				cout<<cur->Data<<" ";
				cur = cur->left;
			}
			cout << cur->Data<<" ";
			if (cur->left_Tag == THREAD)
			{
				cur = cur->right;
			}
		}
	}

中序線索化：

void MidOrderTH(BitreeNodeTH<T>* root, BitreeNodeTH<T>* &prev)
	{
		if (root == NULL)
			return;
		BitreeNodeTH<T>* cur = root;
		MidOrderTH(cur->left,prev);
		if (cur->left == NULL)
		{
			cur->left_Tag = THREAD;
			cur->left = prev;
		}
		if (prev && prev->right == NULL)
		{
			prev->right = cur;
			prev->right_Tag = THREAD;
		}
		prev = cur;
		MidOrderTH(cur->right,prev);
	}

中序遍歷：

void MidOrderTHing(BitreeNodeTH<T>* root)
	{
		BitreeNodeTH<T>* cur = root;
		while(cur)
		{
			while (cur->left_Tag == LINK)
			{
				cur = cur->left;
			}
			cout<<cur->Data<<" ";
			while (cur->right_Tag == THREAD)
			{
				cur = cur->right;
				cout << cur->Data<< " ";
			}
			if (cur->right_Tag == LINK)
			{
				cur = cur->right;
			}
		}
	}

后序線索化：

void LaterOrderTH(BitreeNodeTH<T>* root, BitreeNodeTH<T>* &prev)
	{
		if (root == NULL)
			return;
		BitreeNodeTH<T>* cur = root;
		LaterOrderTH(cur->left,prev);
		LaterOrderTH(cur->right,prev);
	 

		if (cur->left == NULL)
		{
			cur->left_Tag = THREAD;
			cur->left = prev;
		}
		if (prev&&prev->right == NULL)
		{
			prev->right = cur;
			prev->right_Tag = THREAD;
		}
		prev = cur;
	}