二叉树（二）---线索化二叉树-创新互联

二叉树是一种非线性结构，遍历二叉树几乎都是通过递归或者用栈辅助实现非递归的遍历。用二叉树作为存储结构时，取到一个节点，只能获取节点的左孩子和右孩子，不能直接得到节点的任一遍历序列的前驱或者后继。

为了保存这种在遍历中需要的信息，我们利用二叉树中指向左右子树的空指针来存放节点的前驱和后继信息。

代码结构如下：

enum PointerTag
{
	THREAD,
	LINK
};

template
struct BinaryTreeNode
{
	T _data;
	BinaryTreeNode* _left;
	BinaryTreeNode* _right;
	PointerTag _leftTag;//左孩子线索标志
	PointerTag _rightTag;//右孩子线索标志
	BinaryTreeNode(const T& d)
		:_data(d)
		, _left(NULL)
		, _right(NULL)
	{
		_leftTag = LINK;
		_rightTag = LINK;
	}
};

代码实现如下：

void InOrderThreading()    //中序线索化
	{
		Node* prev = NULL;
		_InOrderThreading(_root, prev);
	}

	void PrevOrderThreading()   //前序线索化
	{
		Node* prev = NULL;
		_PrevOrderThreading(_root, prev);
	}

	//void PostOrderThreading()     //后序线索化
	//{
	//	Node* prev = NULL;
	//	_PostOrderThreading(_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;
		}
		cout << endl;
	}

	void PrevOrderThd()   //前序遍历
	{
		Node* cur = _root;
		while (cur)
		{
			cout << cur->_data << " ";
			while (cur->_leftTag == LINK)
			{
				cur = cur->_left;
				cout << cur->_data << " ";
			}
			cur = cur->_right;
		}
		cout << endl;
	}

	
	
	void _InOrderThreading(Node* root, Node*& prev)  //
	{
		if (root == NULL)
		{
			return;
		}
		_InOrderThreading(root->_left, prev);
		if (root->_left == NULL)
		{
			root->_leftTag = THREAD;
			root->_left = prev;
		}
		if (prev&&(prev->_right == NULL))
		{
			prev->_rightTag = THREAD;
			prev->_right = root;
		}
		prev = root;
		_InOrderThreading(root->_right, prev);
	}

	void _PrevOrderThreading(Node* root, Node*& prev)
	{
		Node* cur = root;
		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);
		}
	}

因为后序比较复杂，所以露珠不是很有能力写出来。以后露珠会好好提高自己，然后把后序实现了哈哈哈哈

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。