C++實現線索化二叉樹

     當以二叉樹作為存儲結構時，只能找到節點的左右孩子信息，不能直接得到結點在任一序列中的前驅和后繼信息，只有在遍歷過程中才能得到這種信息。我們知道，在n個結點的二叉鏈表棧必定存在n+1個空鏈域，因此，可以利用這些空鏈域來存放這些結點信息。所以作如下規定：若結點右左子樹，則其lchild域指向其左孩子，否則令lchild域指向其前驅；若結點有右子樹，其rchild域指向其右孩子，否則指向其后繼。以這種結構構成的二叉鏈表叫做線索鏈表。

前序線索化：

源代碼：

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;

enum PointerTag
{
	THREAD,
	LINK,
};

template <class T>
struct BinaryTreeNodeThd
{
	T _data;
	BinaryTreeNodeThd<T>*_left;
	BinaryTreeNodeThd<T>*_right;
	PointerTag _leftTag;
	PointerTag _rightTag;

	BinaryTreeNodeThd(const T&data)//線索化 ：利用二叉樹中指向左右子樹的空指針來存放節點的前驅和后繼信息
		:_data(data)
		, _left(NULL)
		, _right(NULL)
		, _leftTag(LINK)
		, _rightTag(LINK)
	{}

};

template <class T>
class BinaryTreeThd
{
	typedef BinaryTreeNodeThd<T>  Node;

private:
	Node* _root;
public:
	
	BinaryTreeThd()
		:_root(NULL)
	{}

	BinaryTreeThd(const T* a, size_t size,size_t index,const T& invalid)
	{
		
		_root = _CreateBinaryTreeThd(a, size, index, invalid);
	}

	//中序線索化
	void InorderThreading()
	{
	  Node* prev=NULL;
	  _InorderThreading(_root,prev);
	}

	//先序線索化
	void PrevtorderThreading()
	{
	Node* prev=NULL;
	_PrevorderThreading(_root,prev);
	}

	//中序線索化遍歷
	void _InorderThd()
	{
		Node* cur=_root;
		while(cur)
		{
		//	訪問最左邊的葉子節點
	     while(cur->_leftTag ==LINK)
		 {
		 cur=cur->_left ;
		 }

		 cout<<cur->_data <<" ";

		 while(cur->_rightTag ==THREAD)
		 {
			cur=cur->_right ;
			cout<<cur->_data <<" ";
		 }
		 //訪問右子樹
		 cur=cur->_right ;
		}
	}

	//先序線索化遍歷二叉樹
	void _Prevorderthd( )
	{
	Node*cur=_root;
	if(cur==NULL)
	{
		return;
	}
	while(cur)
	{ //輸出左邊的節點
		while(cur->_leftTag ==LINK)
			{
			cout<<cur->_data <<" ";
			cur=cur->_left ;
			}
			cout<<cur->_data <<" ";
			//轉移到右邊的節點
			cur=cur->_right;

			/*while(cur->_rightTag ==THREAD )
			{
			cur=cur->_right ;
			cout<<cur->_data<<" " ;
			}*/
		}
	}
protected:
	//
	Node* _CreateBinaryTreeThd(const T*a, size_t size, size_t& index, const T& invalid)
	{
		Node* root=NULL;
		if(index<size&&a[index]!=invalid)
		{
			root=new Node(a[index]);
			root->_left = _CreateBinaryTreeThd(a,size,++index,invalid);
			root->_right =_CreateBinaryTreeThd(a,size,++index,invalid);
		}
		return root;
	}

	//中序線索化子樹
	void _InorderThreading(Node* cur,Node*& prev)
	{
		if(cur==NULL)
		{
		 return;
		}
		//遞歸遍歷左子樹
		_InorderThreading(cur->_left ,prev);
		if(cur->_left ==NULL)
		{
		 cur->_leftTag =THREAD;
		 cur->_left =prev;
		}
		if(prev&&prev->_right ==NULL)
		{
		prev->_rightTag =THREAD ;
		prev->_right =cur;
		}
		prev=cur;
		//遞歸遍歷右子樹
		_InorderThreading(cur->_right ,prev);
	}

	//先序線索化子樹
	void _PrevorderThreading(Node* cur,Node*& prev)
	{
	 if(cur==NULL)
		 return;
	 //置前線索化
	 if(cur->_left ==NULL)
	 {
		 cur->_leftTag =THREAD ;
		 cur->_left =prev;
	 }
	 //置后線索化
	 if(prev&&prev->_right ==NULL)
	 {
	 prev->_rightTag =THREAD;
	 prev->_right =cur;
	 }

	 prev=cur;

	 if(cur->_leftTag ==LINK)
	 {
		 _PrevorderThreading(cur->_left ,prev);
	 }
	
	  if(cur->_rightTag ==LINK)
	 {
		_PrevorderThreading(cur->_right ,prev);
	 }

	}
};

測試代碼：

void test()
{
	int a1[10]={1,2,3,'#','#',4,'#','#',5,6};
	int a2[15]={1,2,'#',3,'#','#',4,5,'#',6,'#',7,'#','#',8};
	BinaryTreeThd<int>btt1(a1,10,0,'#');
	BinaryTreeThd<int>btt2(a2,15,0,'#');
	cout<<"中序線索化遍歷二叉樹：";
	btt1.InorderThreading ();
	btt1._InorderThd();
	cout<<endl;
	btt2.InorderThreading ();
	btt2._InorderThd();
	cout<<endl;
	cout<<"先序線索化遍歷二叉樹：";
	btt1.PrevtorderThreading();
	btt1. _Prevorderthd();
	cout<<endl;
	btt2.PrevtorderThreading();
	btt2. _Prevorderthd();
	cout<<endl;
}