线索二叉树-创新互联

用二叉树作为存储结构时，取到一个节点，只能获取节点的左孩子和右孩子，不能直接得到节点的任一遍历序列的前驱或者后继。但是常常我们会想要更加直观的知道节点的前驱后继。线索二叉树显得尤为的重要。

 线索二叉树的关键就是要定义一个全局变量来存放上一个访问过的结点。

 Node* prev;

（一）前序线索二叉树

	void PrevOrderTag()
	{
		_PrevOrderTag(_root);
	}
	void _PrevOrderTag(Node* root)//前序线索二叉树
	{
		if (root == NULL)
			return;
		if (!root->_left)
		{
			root->_leftTag = THREAD;
			root->_left = prev;
		}
		if (prev && !prev->_right)
		{
			prev->_rightTag = THREAD;
			prev->_right = root;
		}
		prev = root;
		if (root->_leftTag == LINK)//只有当_leftTag为LINK时递归修改前驱后继
			_PrevOrderTag(root->_left);
		if (root->_rightTag == LINK)
			_PrevOrderTag(root->_right);
	}
	void PrevOrderTagPrint()//前序线索化打印
	{
		Node* cur = _root;
		//while (cur)
		//{
		//	while (cur->_leftTag == LINK)
		//	{
		//		cout << cur->_data << " ";
		//		cur = cur->_left;
		//	}
		//	cout << cur->_data << " ";
		//	cur = cur->_right;
		//}
	//2.
		while (cur)
		{
			cout << cur->_data << " ";
			if (cur->_leftTag == LINK)
			{
				cur = cur->_left;
			}
			else
			{
				cur = cur->_right;
			}
		}
	}

  使用二叉树的线索打印二叉树是比较方便的，不用递归就能解决问题。只要cur不为NULL就一直寻找后继打印。

（二）中序线索二叉树

	void MidOrderTag()
	{
		_MidOrderTag(_root);
	}
	void _MidOrderTag(Node* root)//中序线索二叉树
	{
		if (root == NULL)
		{
			return;
		}
		if (root->_leftTag == LINK)//只有当_leftTag为LINK时递归修改前驱后继
		    _MidOrderTag(root->_left);
		    
		    
		    
		if (!root->_left)
		{
			root->_leftTag = THREAD;
			root->_left = prev;
		}
		if (prev&&!prev->_right)
		{
			prev->_rightTag = THREAD;
			prev->_right = root;
		}
		prev = root;
		
		
		
		if (root->_rightTag == LINK)
		    _MidOrderTag(root->_right);
	}
	void MidOrderTagPrint()//中序线索打印
	{
		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 RearOrderTag()
	{
		_RearOrderTag(_root);
	}
	void _RearOrderTag(Node* root)//后序线索二叉树
	{
		if (root == NULL)
		{
			return;
		}
		if (root->_leftTag == LINK)//只有当_leftTag为LINK时递归修改前驱后继
		    _RearOrderTag(root->_left);
		if (root->_rightTag == LINK)
		    _RearOrderTag(root->_right);
		    
		    
		    
		    
		if (!root->_left)
		{
			root->_leftTag = THREAD;
			root->_left = prev;
		}
		if (prev&&!prev->_right)
		{
			prev->_rightTag = THREAD;
			prev->_right = root;
		}
		prev = root;
	}

  注意，线索二叉树只有当tag的类型为LINK时才修改结点的前驱和后继

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