線索化二叉樹：

創(chuàng)新互聯(lián)是一家專業(yè)提供息烽企業(yè)網(wǎng)站建設(shè),專注與成都做網(wǎng)站、成都網(wǎng)站制作、成都外貿(mào)網(wǎng)站建設(shè)、H5場景定制、小程序制作等業(yè)務(wù)。10年已為息烽眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站設(shè)計公司優(yōu)惠進(jìn)行中。

  利用二叉樹中指向左右子樹的空指針來存放節(jié)點的前驅(qū)和后繼信息。

LChild（左孩子）

Ltag（左線索標(biāo)志）

Data

Rtag（右線索標(biāo)志）

RChild（右孩子）

中序（左根右）：

前序（根左右）：

注意：因為++index返回對象 index++返回臨時變量 傳引用時只能用++index。

前序、中序的線索化及遍歷具體實現(xiàn)如下：

#pragma once

enum
{
	THREAD,
	LINK,
};

typedef int PointerTag;

template<class T>
struct BinaryTreeNodeThd
{
	T _data;                      //數(shù)據(jù)
	BinaryTreeNodeThd<T>* _left;  //左孩子  
	BinaryTreeNodeThd<T>* _right; //右孩子
	PointerTag _leftTag;          //左孩子線索化標(biāo)志  
	PointerTag _rightTag;          //右孩子線索化標(biāo)志

	BinaryTreeNodeThd(const T& x)
		:_data(x)
		, _left(NULL)
		, _right(NULL)
		, _leftTag(LINK)
		, _rightTag(LINK)
	{}
};

template<class T>
class BinaryTreeThd
{
	typedef BinaryTreeNodeThd<T> Node;
public:
	//構(gòu)造
	BinaryTreeThd()
		:_root(NULL)
	{}
	// a--樹的節(jié)點前序遍歷的數(shù)組  size--數(shù)組中元素個數(shù)  invaild--無效值即節(jié)點為空
	BinaryTreeThd(const T* a, size_t size, const T& invalid)
	{
		size_t index = 0;
		_root = _CreateTree(a, size, invalid, index);
	}
	//析構(gòu)
	~BinaryTreeThd()
	{
		_Destory(_root);
		_root = NULL;
	}
	//拷貝  
	BinaryTreeThd(const BinaryTreeThd<T>& t)
	{
		_root = _Copy(t._root);
	}
	//賦值重載(傳統(tǒng))
	//BinaryTreeThd<T>& operator=(const BinaryTreeThd<T>& t)
	//{
	//	if (this != &t)
	//	{
	//		Node* tmp = _Copy(t._root);
	//		_Destory(_root);
	//		_root = tmp;
	//	}
	//	return *this;
	//}
	//賦值重載(現(xiàn)代)
	BinaryTreeThd<T>& operator=(BinaryTreeThd<T> t)
	{
		swap(_root, t._root);
		return *this;
	}

	T& operator->()
	{
		return _root;
	}

public:
	//線索化
	void PrevOrderThread()  //前序
	{
		Node* prev = NULL;
		return _PrevOrderThread(_root, prev);
	}
	void InOrderThread()   //中序
	{
		Node* prev = NULL;
		return _InOrderThread(_root, prev);
	}
	void PostOrderThread()  //后序
	{
		Node* prev = NULL;
		return _PostOrderThread(_root, prev);
	}
	
	//線索化遍歷
	void PrevOrderThd()  //前序遍歷（法一）
	{
		if(_root == NULL)
			return;
		Node* cur = _root;
		while (cur)
		{
			//找最左節(jié)點
			while (cur->_leftTag == LINK)
			{	
				cout << cur->_data << " ";
				cur = cur->_left;
			}
			cout << cur->_data << " ";
			//訪問右子樹
			cur = cur->_right;
		}
		cout << endl;
	}

	void PrevOrderThd_O()  //前序遍歷（法二）
	{
		if(_root == NULL)
			return;
		Node* cur = _root;

		while (cur)
		{
			cout << cur->_data << " ";
			//找最左節(jié)點
			if (cur->_leftTag == LINK)
			{
				cur = cur->_left;
			}
			else     //訪問右子樹 
			{
				cur = cur->_right;
			}
		}
		cout << endl;
	}

	void InOrderThd() //中序遍歷
	{
		Node* cur = _root;
		while (cur)
		{
			//找最左節(jié)點
			while (cur->_leftTag == LINK)
				cur = cur->_left;
			cout << cur->_data << " ";

			//訪問連續(xù)的后繼
			while (cur->_rightTag == THREAD)
			{
				cur = cur->_right;
				cout << cur->_data << " ";
			}

			//訪問右子樹
			cur = cur->_right;
		}
		cout << endl;
	}
	void PostOrderThd();   //后序遍歷
protected:
        //注意 此處index要用引用傳參
	Node* _CreateTree(const T* a, size_t size, const T& invalid, size_t& index) 
	{
		Node* root = NULL;
		if ((index < size) && (a[index] != invalid))
		{
			root = new Node(a[index]);

       //注意下面只能用++index。因為++index返回對象index++返回臨時變量 此處傳的是引用
			root->_left = _CreateTree(a, size, invalid, ++index);
			root->_right = _CreateTree(a, size, invalid, ++index);

		}
		return root;
	}

	void _Destory(Node* root)
	{
		if (root == NULL)
			return;
		_Destroy(root->_left);
		_Destroy(root->_right);
		delete root;
	}
	Node* _Copy(Node* root)
	{
		if (root == NULL)
			return NULL;
		NOde* newRoot = new Node(root->_data);
		newRoot->_left = _Copy(root->_left);
		newRoot->_right = _Copy(root->_right);
		return newRoot;
	}
	
       //前序線索化
	void _PrevOrderThread(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)  //線索化左子樹
			_PrevOrderThread(cur->_left, prev);
		if (cur->_rightTag == LINK)  //線索化右子樹
			_PrevOrderThread(cur->_right, prev);
	}
	
	//中序線索化
	void _InOrderThread(Node* cur, Node* &prev)   
	{
		if (cur == NULL)
			return;
		_InOrderThread(cur->_left, prev);
		//置前驅(qū)線索
		if (cur->_left == NULL)
		{
			cur->_leftTag = THREAD;
			cur->_left = prev;
		}
		//置后繼線索
		if (prev&&prev->_right == NULL)
		{
			prev->_rightTag = THREAD;
			prev->_right = cur;
		}

		prev = cur;

		_InOrderThread(cur->_right, prev);
	}
	
	//后序線索化
	void _PostThread(Node* cur, Node* &prev);  
private:
	Node* _root;
};

測試代碼：

void TestInOrder()
{
	int a1[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
	size_t size = sizeof(a1) / sizeof(int);
	BinaryTreeThd<int> t1 = BinaryTreeThd<int>(a1, size, '#');

	t1.InOrderThread();
	cout << "中序后：";
	t1.InOrderThd();
}
void TestPrev()
{
	int a1[10] = { 1, 2, 3, '#', '#', 4, '#', '#',5, 6 };
	size_t size = sizeof(a1) / sizeof(int);
	BinaryTreeThd<int> t1 = BinaryTreeThd<int>(a1, size, '#');

        t1.PrevOrderThread();
	cout << "前序后(1)：";     
	t1.PrevOrderThd();
	cout << "前序后(2)：";      
	t1.PrevOrderThd_O();
}

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

新聞名稱：【二叉樹】線索化二叉樹-創(chuàng)新互聯(lián)
網(wǎng)頁地址：http://jinyejixie.com/article12/ccejdc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供標(biāo)簽優(yōu)化、網(wǎng)站內(nèi)鏈、商城網(wǎng)站、網(wǎng)站排名、靜態(tài)網(wǎng)站、網(wǎng)站制作

廣告

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