二叉樹的前序、中序和后序線索化-創(chuàng)新互聯(lián)

  二叉樹是一種非線性結(jié)構(gòu)，遍歷二叉樹需要通過(guò)遞歸或者用棧輔助實(shí)現(xiàn)非遞歸的遍歷。

創(chuàng)新互聯(lián)公司堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都網(wǎng)站制作、網(wǎng)站設(shè)計(jì)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的盱眙網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

  用二叉樹作為壓縮存儲(chǔ)結(jié)構(gòu)時(shí)，取到一個(gè)結(jié)點(diǎn)，只能獲取節(jié)點(diǎn)的左孩子和右孩子，不能直接得到結(jié)點(diǎn)的任一遍歷序列的前驅(qū)或者后繼。為了實(shí)現(xiàn)這種遍歷，偶們利用二叉樹中指向左右子樹的空指針來(lái)存放結(jié)點(diǎn)的前驅(qū)和后繼。

線索化二叉樹思路：

  當(dāng)某一結(jié)點(diǎn)的左結(jié)點(diǎn)或結(jié)右點(diǎn)存在NULL時(shí)，則該結(jié)點(diǎn)的為空的子結(jié)點(diǎn)需要線索化。

  在進(jìn)行線索化時(shí)，結(jié)點(diǎn)的前驅(qū)指向前一個(gè)訪問(wèn)過(guò)的結(jié)點(diǎn)，故定義一個(gè)指針prev來(lái)保存前一個(gè)結(jié)點(diǎn)；結(jié)點(diǎn)的后繼偶們并不知道，則對(duì)于未來(lái)的事情并不知道，偶們可以在未來(lái)對(duì)該結(jié)點(diǎn)的后繼進(jìn)行線索化，使prev的后繼指向cur。

前序遍歷二叉樹------根->左->右（1,2,3,4,5,6）

template<class T>
void BinaryTreeThd<T>::PrevOrderThreading()//前序線索化二叉樹
{
	Node* prev = NULL;
	_PrevOrderThreading(_root, prev);
}
template<class T>
void BinaryTreeThd<T>::_PrevOrderThreading(Node* cur, Node*& prev)//前序線索化二叉樹
{
	if (cur == NULL)
	{
		return;
	}
	if (cur->_left == NULL)
	{
		cur->_leftTag = THREAD;
		cur->_left = prev;
	}
	if (prev && prev->_right == NULL)//到未來(lái)的結(jié)點(diǎn)進(jìn)行先前結(jié)點(diǎn)后繼的線索化
	{
		prev->_rightTag = THREAD;
		prev->_right = cur;
	}
	prev = cur;
	if (cur->_leftTag == LINK)//線索化左結(jié)點(diǎn)
	{
		_PrevOrderThreading(cur->_left, prev);
	}
	if (cur->_rightTag == LINK)//線索化右結(jié)點(diǎn)
	{
		_PrevOrderThreading(cur->_right, prev);
	}
}

中序遍歷二叉樹------左->根->右（3,2,4,1,6,5）

遞歸實(shí)現(xiàn)：

template<class T>
void BinaryTreeThd<T>::InOrderThreading()//中序線索化二叉樹
{
	//遞歸實(shí)現(xiàn)中序線索化
	Node* prev = NULL;//線索化的前一個(gè)結(jié)點(diǎn)
	_InOrederThreading(_root, prev);
}
template<class T>
void BinaryTreeThd<T>::_InOrederThreading(Node* cur,Node*& prev)//中序線索化二叉樹
{
	if (cur == NULL)
	{
		return;
	}
	_InOrederThreading(cur->_left, prev);//遞歸出cur->_left為空
	if (cur->_left == NULL)
	{
		cur->_leftTag = THREAD;
		cur->_left = prev;//當(dāng)前結(jié)點(diǎn)的前驅(qū)指向前一個(gè)結(jié)點(diǎn)
	}
	//對(duì)先前的結(jié)點(diǎn)后繼進(jìn)行線索化，在cur指向下一個(gè)結(jié)點(diǎn)即后繼時(shí)，將先前節(jié)點(diǎn)的后繼指向cur
	//到未來(lái)的結(jié)點(diǎn)進(jìn)行先前結(jié)點(diǎn)后繼的線索化
	if (prev && prev->_right == NULL)
	{
		cur->_rightTag = THREAD;
		prev->_right = cur;
	}
	prev = cur;
	_InOrederThreading(cur->_right, prev);//遞歸出cur->_right為空
}

非遞歸實(shí)現(xiàn)（利用棧）：

template<class T>
void BinaryTreeThd<T>::InOrderThreading_NonR()//中序線索化二叉樹--非遞歸
{
	//棧實(shí)現(xiàn)中序線索化
	stack<Node*> s;
	Node* prev = NULL;
	Node* cur = _root;
	if (cur == NULL)
	{
		return;
	}
	while (cur || !s.empty())
	{
		while(cur)//找到最左結(jié)點(diǎn),入棧
		{
			s.push(cur);
			cur = cur->_left;
		}//cur不為空進(jìn)棧，cur為空說(shuō)明cur已經(jīng)線索化了
		cur = s.top();//循環(huán)進(jìn)入使cur為棧頂元素并判斷是否需要線索化
		if (cur->_left == NULL)
		{
			cur->_leftTag = THREAD;
			cur->_left = prev;
		}
		s.pop();//彈出棧頂元素，使棧頂保存需要線索化的cur的后繼
		prev = cur;
		if (cur->_right == NULL && !s.empty())
		{
			cur->_rightTag = THREAD;
			cur->_right = s.top();
			cur = NULL;//設(shè)置cur為空，防止死循環(huán)（2）
		}
		else
		{
			cur = cur->_right;//線索化跳到右子樹進(jìn)行
		}
	}
}

后序遍歷二叉樹------左->右->根（3,4,2,6,5,1）

template<class T>
void BinaryTreeThd<T>::PastOrderThreading()//后序線索化二叉樹
{
	Node* prev = NULL;
	_PastOrderThreading(_root, prev);
}
template<class T>
void BinaryTreeThd<T>::_PastOrderThreading(Node* cur, Node*& prev)//后序線索化二叉樹
{
	if (cur == NULL)
	{
		return;
	}
	_PastOrderThreading(cur->_left, prev);//最左結(jié)點(diǎn)
	_PastOrderThreading(cur->_right, prev);//最右結(jié)點(diǎn)
	if (cur->_left == NULL)//線索化前驅(qū)
	{
		cur->_leftTag = THREAD;
		cur->_left = prev;
	}
	if (prev && prev->_right == NULL)//線索化后繼
	{
		prev->_rightTag = THREAD;
		prev->_right = cur;
	}
	prev = cur;
}

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

當(dāng)前名稱：二叉樹的前序、中序和后序線索化-創(chuàng)新互聯(lián)
標(biāo)題鏈接：http://muchs.cn/article44/cspiee.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App開發(fā)、網(wǎng)站建設(shè)、網(wǎng)站收錄、企業(yè)建站、品牌網(wǎng)站設(shè)計(jì)、建站公司

廣告

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