二叉樹是一種非線性結(jié)構(gòu)，遍歷二叉樹幾乎都是通過遞歸或者用棧輔助實(shí)現(xiàn)非遞歸的遍歷。用二叉樹作為存儲(chǔ)結(jié)構(gòu)時(shí)，取到一個(gè)節(jié)點(diǎn)，只

創(chuàng)新互聯(lián)公司-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比格爾木網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式格爾木網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋格爾木地區(qū)。費(fèi)用合理售后完善，十載實(shí)體公司更值得信賴。

能獲取節(jié)點(diǎn)的左孩子和右孩子，不能直接得到節(jié)點(diǎn)的任一遍歷序列的前驅(qū)或者后繼。

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

enum PointerTag

{

LINK,  //0

THREAD  //1

};

template

struct BitreeNodeTH

{

T Data;

BitreeNodeTH *left;  //左孩子

BitreeNodeTH *right; //右孩子

PointerTag left_Tag;  //左孩子線索標(biāo)志

PointerTag right_Tag; //右孩子線索標(biāo)志

BitreeNodeTH(T data = T())

:Data(data)

,left(NULL)

,right(NULL)

,left_Tag(LINK)

,right_Tag(LINK)

{}

};

一個(gè)線索二叉樹的節(jié)點(diǎn)：

left

left_Tag

Data

reght_Tag

reght

線索化二叉樹的主要源代碼：

建樹：

	BitreeNodeTH* Create_tree(T *arr,int sz,int &i)
	{
		if(*arr==NULL||arr[i]=='#'||i>=sz)
			return NULL;
		else 
		{
			BitreeNodeTH *cur=new BitreeNodeTH;
			cur->Data=arr[i];
			i++;
			cur->left=Create_tree(arr,sz,i);
			i++;
			cur->right=Create_tree(arr,sz,i);
			return cur;
		}
	}

前序線索化：

	void FirstOrderTH(BitreeNodeTH* root, BitreeNodeTH* &prev)// &表示沒有開辟臨時(shí)變量
	{
		if (root == NULL)
			return;
		BitreeNodeTH* cur = root;
	 	if (cur->left == NULL)
		{
			cur->left_Tag = THREAD;
			cur->left = prev;
		}
		if (prev&&prev->right == NULL)
		{
			prev->right_Tag = THREAD;
			prev->right = cur;
		}
		prev = cur;
		if (cur->left_Tag == LINK)   //cur->left
			FirstOrderTH(cur->left,prev);
		if(cur->right_Tag == LINK)   //cur->right
			FirstOrderTH(cur->right, prev);
	}

前序遍歷：

	void FirstOrderTHing(BitreeNodeTH* root)
	{
		if (root == NULL)
			return;
		BitreeNodeTH* cur = root;
		while (cur)
		{
			while(cur->left_Tag == LINK)
			{
				cout<Data<<" ";
				cur = cur->left;
			}
			cout << cur->Data<<" ";
			if (cur->left_Tag == THREAD)
			{
				cur = cur->right;
			}
		}
	}

中序線索化：

void MidOrderTH(BitreeNodeTH* root, BitreeNodeTH* &prev)
	{
		if (root == NULL)
			return;
		BitreeNodeTH* cur = root;
		MidOrderTH(cur->left,prev);
		if (cur->left == NULL)
		{
			cur->left_Tag = THREAD;
			cur->left = prev;
		}
		if (prev && prev->right == NULL)
		{
			prev->right = cur;
			prev->right_Tag = THREAD;
		}
		prev = cur;
		MidOrderTH(cur->right,prev);
	}

中序遍歷：

void MidOrderTHing(BitreeNodeTH* root)
	{
		BitreeNodeTH* cur = root;
		while(cur)
		{
			while (cur->left_Tag == LINK)
			{
				cur = cur->left;
			}
			cout<Data<<" ";
			while (cur->right_Tag == THREAD)
			{
				cur = cur->right;
				cout << cur->Data<< " ";
			}
			if (cur->right_Tag == LINK)
			{
				cur = cur->right;
			}
		}
	}

后序線索化：

void LaterOrderTH(BitreeNodeTH* root, BitreeNodeTH* &prev)
	{
		if (root == NULL)
			return;
		BitreeNodeTH* cur = root;
		LaterOrderTH(cur->left,prev);
		LaterOrderTH(cur->right,prev);
	 

		if (cur->left == NULL)
		{
			cur->left_Tag = THREAD;
			cur->left = prev;
		}
		if (prev&&prev->right == NULL)
		{
			prev->right = cur;
			prev->right_Tag = THREAD;
		}
		prev = cur;
	}

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

新聞標(biāo)題：線索化二叉樹-創(chuàng)新互聯(lián)
當(dāng)前URL：http://weahome.cn/article/pcioi.html