数据结构--二叉树的线索化-创新互联

线索二叉树它解决了无法直接找到该结点在某种遍历序列中的前趋和后继结点的问题，出现了二叉链表找左、右孩子困难的问题，线索二叉树又分为前序线索化，中序线索化和后序线索化，分别用不同的逻辑去实现。

在鄂托克前等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供成都网站建设、成都网站制作 网站设计制作定制网站建设,公司网站建设,企业网站建设,品牌网站制作,全网整合营销推广,外贸营销网站建设,鄂托克前网站建设费用合理。

线索二叉树的实现思想：借用一个枚举类型tag其中包含两个状态Link(代表有数据)，thread(代表下一个节点为空)在一个节点的左节点或者右节点为空的情况下，将它的left或right设为thread,则它的左或右访问的是改遍历模式下访问到的下一个节点数据，这样就完成了跳到另一颗子树的过程，减少了递归的次数。

先序线索化

void _PrevorderThreading(BinaryTreeXsh *cur, BinaryTreeXsh *&prev)
	{
		if (cur == NULL)
		{
			return;
		}
		if (cur->_leftnode==NULL)
		{
			cur->_LeftTag=THREAD;
			cur->_leftnode=prev;
		}
		if (prev&&prev->_rightnode==NULL)
		{
			prev->_RightTag = THREAD;
			prev->_rightnode = cur;
		}
		prev = cur;
		if (cur->_LeftTag == LINK)
		{
			_PrevorderThreading(cur->_leftnode, prev);
		}
		if (cur->_RightTag == LINK)
		{
			_PrevorderThreading(cur->_rightnode, prev);
		}
	}

中序线索化

	void _InorderThreading(BinaryTreeXsh* root, BinaryTreeXsh *&prev)
	{
		BinaryTreeXsh*cur = root;
		if (cur == NULL)
		{
			return;
		}
		_InorderThreading(cur->_leftnode, prev);
		
		if (cur->_leftnode == NULL)
		{
			cur->_LeftTag = THREAD;
			cur->_leftnode = prev;
		}
		if (prev&&prev->_rightnode == NULL)
		{
			prev->_RightTag = THREAD;
			prev->_rightnode = cur;
		}
		prev = cur;
		_InorderThreading(cur->_rightnode, prev);
	}

后序线索化

	void _PostorderThreading(BinaryTreeXsh*root, BinaryTreeXsh*&prev)
	{
		BinaryTreeXsh*cur = root;
		if (cur == NULL)
		{
			return;
		}
		_PostorderThreading(cur->_leftnode, prev);
		_PostorderThreading(cur->_rightnode, prev);
		if (cur->_leftnode==NULL)
		{
			cur->_LeftTag = THREAD;
			cur->_leftnode = prev;
		}
		if (prev&&prev->_rightnode == NULL)
		{
			prev->_RightTag = THREAD;
			prev->_rightnode = cur;
		}
		prev = cur;
	}

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

分享名称：数据结构--二叉树的线索化-创新互联
本文路径：http://mswzjz.cn/article/dhcojj.html