大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

二叉树的线索化算法思想详解-创新互联

   二叉树的线索化,这几天以来我很难掌握,今天终于想通了,哈哈,首先我们来看看二叉树线索化之后会变成什么样子,这里我们以图中的二叉树为例,图如下:

创新互联公司是专业的新疆网站建设公司,新疆接单;提供网站设计制作、网站设计,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行新疆网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

二叉树的线索化算法思想详解

   画的太糙,各位看官讲究着看吧- -。所谓二叉树的线索化,就是当一个节点的左右指针为空时,就让它的左右指针指向该节点的前驱或者后继(一般来说左指针指向前驱,右指针指向后继)。这里不论指向前驱或者后继,我们都应该线索化时,至少要明确两个节点指针的值,当前节点和当前节点的前驱/后继。这也是线索化的两种思路:

   保存前驱:访问当前节点时若当前节点的左指针为空,则令左指针指向前驱,若前驱的右指针为空,则令前驱的右指针指向当前节点,代码描述如下:

void visit(NODE* cur,NODE* &prev)//当前指针的前驱在当前指针访问时会改变,故传引用用来改变//prev
{
       if(prev->right==NULL;
           prev->right=cur;
       if(cur->left==NULL)
           cur->left=prev;
       prev=cur;
}

   这里我们要注意的是应该先进行访问,最后再改变prev的值。

   保存后继:这种方法很难做到,并且个人觉得没有什么意义,因为在遍历整个数的过程中我们始终都会访问到一个节点的后继,若将要访问后继那我们如何保存到未来的东西,即使通过类似栈的数据结构通过压栈来强行访问,效率也是不高的,在此不推荐。

   接下来献上c++完整的线索二叉树结构以及中序线索化过程,通过递归与非递归两种方式实现,其他的都大同小异。

   节点类定义如下:

typedef char Datatype;
enum NodeType
{
	LINK,
	THERAD
};

struct TheardBinaryTreeNode
{
	TheardBinaryTreeNode* _left;
	TheardBinaryTreeNode* _right;
	NodeType _leftTag;
	NodeType _rightTag;
	Datatype _data;
	TheardBinaryTreeNode(const Datatype & data)
		:_left(NULL)
		, _right(NULL)
		, _leftTag(LINK)
		, _rightTag(LINK)
		,_data(data)
	{}
	TheardBinaryTreeNode()
		: _left(NULL)
		, _right(NULL)
		, _leftTag(LINK)
		, _rightTag(LINK)
		,_data((Datatype)0)
	{}
};

   中序线索化如下:

void InTherad()
	{
		NODE* prev = NULL;
		_InTherad(_root, prev);
		//stacks;//借助栈来实现非递归的中序线索化
		//NODE* cur = _root;
		//NODE* prev = NULL;
		//while (!s.empty()||cur)
		//{
		//	while (cur)
		//	{
		//		s.push(cur);
		//		cur = cur->_left;
		//	}
		//	NODE* top = s.top();
		//	s.pop();
		//	if (top->_left == NULL&&top->_leftTag == LINK)
		//	{
		//		top->_left = prev;
		//		top->_leftTag = THERAD;
		//	}
		//	prev = top;
		//	if (top->_right == NULL&&top->_rightTag==LINK)
		//	{
		//		top->_rightTag = THERAD;
		//		if (!s.empty())
		//			top->_right = s.top();
		//	}
		//	else
		//		cur = top->_right;
		//}
	}
		void _InTherad(NODE*root, NODE* &prev)//递归的中序线索化
	{
		if (root == NULL)
			return;
		_InTherad(root->_left, prev);
		if (prev&&prev->_rightTag == LINK&&prev->_right == NULL)
		{
			prev->_right = root;
			prev->_rightTag = THERAD;
		}
		if (root->_leftTag == LINK&&root->_left == NULL)
		{
			root->_leftTag = THERAD;
			root->_left = prev;
			prev = root;
		}
		_InTherad(root->_right,prev);
	}

   如有不足或者疑问希望留言提出。3Q -3-。

创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。


标题名称:二叉树的线索化算法思想详解-创新互联
网站地址:http://dzwzjz.com/article/ccdogc.html
在线咨询
服务热线
服务热线:028-86922220
TOP