C++实现线索化二叉树

     当以二叉树作为存储结构时，只能找到节点的左右孩子信息，不能直接得到结点在任一序列中的前驱和后继信息，只有在遍历过程中才能得到这种信息。我们知道，在n个结点的二叉链表栈必定存在n+1个空链域，因此，可以利用这些空链域来存放这些结点信息。所以作如下规定：若结点右左子树，则其lchild域指向其左孩子，否则令lchild域指向其前驱；若结点有右子树，其rchild域指向其右孩子，否则指向其后继。以这种结构构成的二叉链表叫做线索链表。

威远ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景，ssl证书未来市场广阔！成为创新互联的ssl证书销售渠道，可以享受市场价格4-6折优惠！如果有意向欢迎电话联系或者加微信：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)//线索化 ：利用二叉树中指向左右子树的空指针来存放节点的前驱和后继信息
		:_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)
		{
		//	访问最左边的叶子节点
	     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)
	{ //输出左边的节点
		while(cur->_leftTag ==LINK)
			{
			cout<_data <<" ";
			cur=cur->_left ;
			}
			cout<_data <<" ";
			//转移到右边的节点
			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<            
            
                        

            分享标题：C++实现线索化二叉树            

            标题来源：http://cxhlcq.com/article/pdheoo.html