二叉樹的線索化，這幾天以來我很難掌握，今天終于想通了，哈哈，首先我們來看看二叉樹線索化之后會變成什么樣子，這里我們以圖中的二叉樹為例，圖如下：

創(chuàng)新互聯(lián)公司是專業(yè)的新疆網(wǎng)站建設公司，新疆接單;提供網(wǎng)站設計制作、網(wǎng)站設計,網(wǎng)頁設計,網(wǎng)站設計,建網(wǎng)站,PHP網(wǎng)站建設等專業(yè)做網(wǎng)站服務;采用PHP框架,可快速的進行新疆網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團隊,希望更多企業(yè)前來合作!

   畫的太糙，各位看官講究著看吧- -。所謂二叉樹的線索化，就是當一個節(jié)點的左右指針為空時，就讓它的左右指針指向該節(jié)點的前驅或者后繼（一般來說左指針指向前驅，右指針指向后繼）。這里不論指向前驅或者后繼，我們都應該線索化時，至少要明確兩個節(jié)點指針的值，當前節(jié)點和當前節(jié)點的前驅/后繼。這也是線索化的兩種思路：

   保存前驅：訪問當前節(jié)點時若當前節(jié)點的左指針為空，則令左指針指向前驅，若前驅的右指針為空，則令前驅的右指針指向當前節(jié)點，代碼描述如下：

void visit(NODE* cur,NODE* &prev)//當前指針的前驅在當前指針訪問時會改變，故傳引用用來改變//prev
{
       if(prev->right==NULL;
           prev->right=cur;
       if(cur->left==NULL)
           cur->left=prev;
       prev=cur;
}

   這里我們要注意的是應該先進行訪問，最后再改變prev的值。

   保存后繼：這種方法很難做到，并且個人覺得沒有什么意義，因為在遍歷整個數(shù)的過程中我們始終都會訪問到一個節(jié)點的后繼，若將要訪問后繼那我們如何保存到未來的東西，即使通過類似棧的數(shù)據(jù)結構通過壓棧來強行訪問，效率也是不高的，在此不推薦。

   接下來獻上c++完整的線索二叉樹結構以及中序線索化過程，通過遞歸與非遞歸兩種方式實現(xiàn)，其他的都大同小異。

   節(jié)點類定義如下：

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);
		//stack<NODE*>s;//借助棧來實現(xiàn)非遞歸的中序線索化
		//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-。

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡助力業(yè)務部署。公司持有工信部辦法的idc、isp許可證， 機房獨有T級流量清洗系統(tǒng)配攻擊溯源，準確進行流量調度，確保服務器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務器買多久送多久。

文章標題：二叉樹的線索化算法思想詳解-創(chuàng)新互聯(lián)
網(wǎng)頁路徑：http://www.aaarwkj.com/article12/ccdogc.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供定制開發(fā)、App設計、域名注冊、關鍵詞優(yōu)化、網(wǎng)頁設計公司、軟件開發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)