線索化二叉樹：

創新互聯是一家專業提供息烽企業網站建設,專注與成都做網站、成都網站制作、成都外貿網站建設、H5場景定制、小程序制作等業務。10年已為息烽眾多企業、政府機構等服務。創新互聯專業網站設計公司優惠進行中。

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

LChild（左孩子）

Ltag（左線索標志）

Data

Rtag（右線索標志）

RChild（右孩子）

中序（左根右）：

前序（根左右）：

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

前序、中序的線索化及遍歷具體實現如下：

#pragma once

enum
{
	THREAD,
	LINK,
};

typedef int PointerTag;

template<class T>
struct BinaryTreeNodeThd
{
	T _data;                      //數據
	BinaryTreeNodeThd<T>* _left;  //左孩子  
	BinaryTreeNodeThd<T>* _right; //右孩子
	PointerTag _leftTag;          //左孩子線索化標志  
	PointerTag _rightTag;          //右孩子線索化標志

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

template<class T>
class BinaryTreeThd
{
	typedef BinaryTreeNodeThd<T> Node;
public:
	//構造
	BinaryTreeThd()
		:_root(NULL)
	{}
	// a--樹的節點前序遍歷的數組  size--數組中元素個數  invaild--無效值即節點為空
	BinaryTreeThd(const T* a, size_t size, const T& invalid)
	{
		size_t index = 0;
		_root = _CreateTree(a, size, invalid, index);
	}
	//析構
	~BinaryTreeThd()
	{
		_Destory(_root);
		_root = NULL;
	}
	//拷貝  
	BinaryTreeThd(const BinaryTreeThd<T>& t)
	{
		_root = _Copy(t._root);
	}
	//賦值重載(傳統)
	//BinaryTreeThd<T>& operator=(const BinaryTreeThd<T>& t)
	//{
	//	if (this != &t)
	//	{
	//		Node* tmp = _Copy(t._root);
	//		_Destory(_root);
	//		_root = tmp;
	//	}
	//	return *this;
	//}
	//賦值重載(現代)
	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)
		{
			//找最左節點
			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 << " ";
			//找最左節點
			if (cur->_leftTag == LINK)
			{
				cur = cur->_left;
			}
			else     //訪問右子樹 
			{
				cur = cur->_right;
			}
		}
		cout << endl;
	}

	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 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);
		//置前驅線索
		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();
}

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

新聞名稱：【二叉樹】線索化二叉樹-創新互聯
網頁地址：http://vcdvsql.cn/article12/ccejdc.html

成都網站建設公司_創新互聯，為您提供標簽優化、網站內鏈、商城網站、網站排名、靜態網站、網站制作

廣告

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