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

威遠ssl適用于網(wǎng)站、小程序/APP、API接口等需要進行數(shù)據(jù)傳輸應用場景，ssl證書未來市場廣闊！成為創(chuàng)新互聯(lián)的ssl證書銷售渠道，可以享受市場價格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：13518219792（備注：SSL證書合作）期待與您的合作！

前序線索化：

源代碼：

#define _CRT_SECURE_NO_WARNINGS 1
#include 
using namespace std;

enum PointerTag
{
	THREAD,
	LINK,
};

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

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

};

template 
class BinaryTreeThd
{
	typedef BinaryTreeNodeThd  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)
		{
		//	訪問最左邊的葉子節(jié)點
	     while(cur->_leftTag ==LINK)
		 {
		 cur=cur->_left ;
		 }

		 cout<_data <<" ";

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

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

			/*while(cur->_rightTag ==THREAD )
			{
			cur=cur->_right ;
			cout<_data<<" " ;
			}*/
		}
	}
protected:
	//
	Node* _CreateBinaryTreeThd(const T*a, size_t size, size_t& index, const T& invalid)
	{
		Node* root=NULL;
		if(index_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};
	BinaryTreeThdbtt1(a1,10,0,'#');
	BinaryTreeThdbtt2(a2,15,0,'#');
	cout<<"中序線索化遍歷二叉樹：";
	btt1.InorderThreading ();
	btt1._InorderThd();
	cout<            
            
                        

            網(wǎng)頁標題：C++實現(xiàn)線索化二叉樹            

            本文鏈接：http://weahome.cn/article/pdheoo.html