二叉樹（二）---線索化二叉樹-創(chuàng)新互聯(lián)

二叉樹是一種非線性結(jié)構(gòu)，遍歷二叉樹幾乎都是通過遞歸或者用棧輔助實現(xiàn)非遞歸的遍歷。用二叉樹作為存儲結(jié)構(gòu)時，取到一個節(jié)點，只能獲取節(jié)點的左孩子和右孩子，不能直接得到節(jié)點的任一遍歷序列的前驅(qū)或者后繼。

網(wǎng)站的建設成都創(chuàng)新互聯(lián)公司專注網(wǎng)站定制,經(jīng)驗豐富,不做模板,主營網(wǎng)站定制開發(fā).小程序定制開發(fā),H5頁面制作!給你煥然一新的設計體驗!已為成都攪拌罐車等企業(yè)提供專業(yè)服務。

為了保存這種在遍歷中需要的信息，我們利用二叉樹中指向左右子樹的空指針來存放節(jié)點的前驅(qū)和后繼信息。

代碼結(jié)構(gòu)如下：

enum PointerTag
{
	THREAD,
	LINK
};

template<class T>
struct BinaryTreeNode
{
	T _data;
	BinaryTreeNode<T>* _left;
	BinaryTreeNode<T>* _right;
	PointerTag _leftTag;//左孩子線索標志
	PointerTag _rightTag;//右孩子線索標志
	BinaryTreeNode(const T& d)
		:_data(d)
		, _left(NULL)
		, _right(NULL)
	{
		_leftTag = LINK;
		_rightTag = LINK;
	}
};

代碼實現(xiàn)如下：

void InOrderThreading()    //中序線索化
	{
		Node* prev = NULL;
		_InOrderThreading(_root, prev);
	}

	void PrevOrderThreading()   //前序線索化
	{
		Node* prev = NULL;
		_PrevOrderThreading(_root, prev);
	}

	//void PostOrderThreading()     //后序線索化
	//{
	//	Node* prev = NULL;
	//	_PostOrderThreading(_root, prev);
	//}

	void InOrderThd()     //中序遍歷
	{
		Node* cur = _root;
		while (cur)
		{
			while (cur->_leftTag == LINK)
			{
				cur = cur->_left;
			}
			cout << cur->_data << " ";
			while (cur->_rightTag == THREAD)
			{
				cur = cur->_right;
				cout << cur->_data << " ";
			}
			cur = cur->_right;
		}
		cout << endl;
	}

	void PrevOrderThd()   //前序遍歷
	{
		Node* cur = _root;
		while (cur)
		{
			cout << cur->_data << " ";
			while (cur->_leftTag == LINK)
			{
				cur = cur->_left;
				cout << cur->_data << " ";
			}
			cur = cur->_right;
		}
		cout << endl;
	}

	
	
	void _InOrderThreading(Node* root, Node*& prev)  //
	{
		if (root == NULL)
		{
			return;
		}
		_InOrderThreading(root->_left, prev);
		if (root->_left == NULL)
		{
			root->_leftTag = THREAD;
			root->_left = prev;
		}
		if (prev&&(prev->_right == NULL))
		{
			prev->_rightTag = THREAD;
			prev->_right = root;
		}
		prev = root;
		_InOrderThreading(root->_right, prev);
	}

	void _PrevOrderThreading(Node* root, Node*& prev)
	{
		Node* cur = root;
		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);
		}
	}

因為后序比較復雜，所以露珠不是很有能力寫出來。以后露珠會好好提高自己，然后把后序?qū)崿F(xiàn)了哈哈哈哈

另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

網(wǎng)頁標題：二叉樹（二）---線索化二叉樹-創(chuàng)新互聯(lián)
文章來源：http://www.muchs.cn/article24/dgieje.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供移動網(wǎng)站建設、App設計、網(wǎng)站設計、商城網(wǎng)站、微信小程序、手機網(wǎng)站建設

廣告

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