二叉樹是一種非線性結構，遍歷二叉樹需要通過遞歸或者用棧輔助實現非遞歸的遍歷。

創新互聯公司堅持“要么做到，要么別承諾”的工作理念，服務領域包括：成都網站制作、網站設計、企業官網、英文網站、手機端網站、網站推廣等服務，滿足客戶于互聯網時代的盱眙網站設計、移動媒體設計的需求，幫助企業找到有效的互聯網解決方案。努力成為您成熟可靠的網絡建設合作伙伴！

  用二叉樹作為壓縮存儲結構時，取到一個結點，只能獲取節點的左孩子和右孩子，不能直接得到結點的任一遍歷序列的前驅或者后繼。為了實現這種遍歷，偶們利用二叉樹中指向左右子樹的空指針來存放結點的前驅和后繼。

線索化二叉樹思路：

  當某一結點的左結點或結右點存在NULL時，則該結點的為空的子結點需要線索化。

  在進行線索化時，結點的前驅指向前一個訪問過的結點，故定義一個指針prev來保存前一個結點；結點的后繼偶們并不知道，則對于未來的事情并不知道，偶們可以在未來對該結點的后繼進行線索化，使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)//到未來的結點進行先前結點后繼的線索化
	{
		prev->_rightTag = THREAD;
		prev->_right = cur;
	}
	prev = cur;
	if (cur->_leftTag == LINK)//線索化左結點
	{
		_PrevOrderThreading(cur->_left, prev);
	}
	if (cur->_rightTag == LINK)//線索化右結點
	{
		_PrevOrderThreading(cur->_right, prev);
	}
}

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

遞歸實現：

template<class T>
void BinaryTreeThd<T>::InOrderThreading()//中序線索化二叉樹
{
	//遞歸實現中序線索化
	Node* prev = NULL;//線索化的前一個結點
	_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;//當前結點的前驅指向前一個結點
	}
	//對先前的結點后繼進行線索化，在cur指向下一個結點即后繼時，將先前節點的后繼指向cur
	//到未來的結點進行先前結點后繼的線索化
	if (prev && prev->_right == NULL)
	{
		cur->_rightTag = THREAD;
		prev->_right = cur;
	}
	prev = cur;
	_InOrederThreading(cur->_right, prev);//遞歸出cur->_right為空
}

非遞歸實現（利用棧）：

template<class T>
void BinaryTreeThd<T>::InOrderThreading_NonR()//中序線索化二叉樹--非遞歸
{
	//棧實現中序線索化
	stack<Node*> s;
	Node* prev = NULL;
	Node* cur = _root;
	if (cur == NULL)
	{
		return;
	}
	while (cur || !s.empty())
	{
		while(cur)//找到最左結點,入棧
		{
			s.push(cur);
			cur = cur->_left;
		}//cur不為空進棧，cur為空說明cur已經線索化了
		cur = s.top();//循環進入使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;//設置cur為空，防止死循環（2）
		}
		else
		{
			cur = cur->_right;//線索化跳到右子樹進行
		}
	}
}

后序遍歷二叉樹------左->右->根（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);//最左結點
	_PastOrderThreading(cur->_right, prev);//最右結點
	if (cur->_left == NULL)//線索化前驅
	{
		cur->_leftTag = THREAD;
		cur->_left = prev;
	}
	if (prev && prev->_right == NULL)//線索化后繼
	{
		prev->_rightTag = THREAD;
		prev->_right = cur;
	}
	prev = cur;
}

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

當前名稱：二叉樹的前序、中序和后序線索化-創新互聯
標題鏈接：http://www.yijiale78.com/article44/cspiee.html

成都網站建設公司_創新互聯，為您提供App開發、網站建設、網站收錄、企業建站、品牌網站設計、建站公司

廣告

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