国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

二叉樹后序線索化以及后序遍歷

2019-11-08 02:48:53
字體:
來源:轉載
供稿:網友

構建節點:多了雙親節點

struct BinaryTreeNodeThd{	BinaryTreeNodeThd(const T& data)	: _data(data)	, _pLeft(NULL)	, _PRight(NULL)	, _pParent(NULL)	, _LeftThread(LINK)	, _RightThread(LINK)	{}	T _data;	BinaryTreeNodeThd<T>* _pLeft;	BinaryTreeNodeThd<T>* _pRight;	BinaryTreeNodeThd<T>* _pParent;	Info _LeftThread;	Info _RightThread;};

  后序線索化:先線索化左子樹 再線索化右子樹,最后線索化當前根節點

   直接貼代碼

	void PostThread()	{		BinaryTreeNodeThd<T>* prev = NULL;		_PostThread(_pRoot, prev);	}	void _PostThread(BinaryTreeNodeThd<T>* pRoot, BinaryTreeNodeThd<T>*& prev)	{		if (pRoot)		{			_PostThread(pRoot->_pLeft,prev);// 線索化左子樹			_PostThread(pRoot->_pRight,prev); //線索化右子樹			if (pRoot->_pLeft == NULL)			{				pRoot->_LeftThread = THREAD;				pRoot->_pLeft = prev;			}						if (prev && prev->_pRight == NULL)			{				prev->_RightThread = THREAD;				prev->_pRight = pRoot;			}			prev = pRoot;		}	} 

后序遍歷線索二叉樹:

 思路:(1)找到最左邊的節點(分為兩種情況 :存在右子樹 ,不存在右子樹)

    (2)while循環一直遍歷節點的后繼(prev保存上一次訪問的節點)注意左單支

跳出循環條件:當前節點有右子樹或者可能到根節點

    (3)跳出循環:判斷是否為根節點:如果根節點沒有右子樹,直接訪問return退出

    (4)當前節點不為根節點,循環訪問當前節點的雙親節點  注意右單支

    (5)最后判斷是否為有右子樹,當前節點指向其右子樹

  

代碼:

 

	void PostOrder()	{		_PostOrder(_pRoot);	}        void _PostOrder(BinaryTreeNodeThd<T>* pRoot) 	{		BinaryTreeNodeThd<T>* pCur = pRoot; 		BinaryTreeNodeThd<T>* prev = NULL; //保存上一次訪問的節點		while (pCur)		{			//找最左邊的節點			while (pCur->_LeftThread == LINK && pCur->_pLeft != prev) //防止陷入死循環  			{				pCur = pCur->_pLeft;			} //跳出循環的條件:pCur為最左邊的節點						//訪問節點的后繼			while (pCur && THREAD == pCur->_RightThread) // 			{				cout << pCur->_data << " ";				prev = pCur; //perv記錄已經訪問過的節點				pCur = pCur->_pRight;			}//跳出循環的條件:pCur為空(即左單支情況) 節點有右子樹,節點為根節點			//跳出循環,判斷是否為根節點			if (pCur == pRoot && pCur->_pRight == prev)			{				cout << pCur->_data << " ";				return;			}			//不是根節點,訪問當前節點的雙親節點			while (pCur && pCur->_pRight == prev) // 注意 右單支情況			{				cout << pCur->_data << " ";				prev = pCur;				pCur = pCur->_pParent;			}			// 判斷根節點是否有右子樹			if (pCur && pCur->_RightThread == LINK)			{				pCur = pCur->_pRight;			}		}	}

  代碼測試分析:

 

  測試代碼:

void FunTest2(){	char* pTreeInfo = "1245##6#7###3";	BinaryTreeThd<char> bt(pTreeInfo, strlen(pTreeInfo));	bt.PostThread();	bt.PostOrder(); //結果:5764231}

測試一下特殊的右單支的情況:

        

 分析右單支:注意(3)步

     

測試一下特殊的左單支:所以循環訪問后繼的時候需要加判斷pCur是否為空

 

 

               


發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 贵阳市| 宝山区| 滨州市| 牙克石市| 瑞金市| 信宜市| 滨州市| 安远县| 巴彦县| 施甸县| 合作市| 沙坪坝区| 洛阳市| 巴楚县| 临漳县| 迁安市| 武强县| 尖扎县| 疏勒县| 吉首市| 京山县| 烟台市| 泰兴市| 肥乡县| 恩施市| 临泉县| 大埔区| 滕州市| 麻江县| 大庆市| 弥渡县| 建昌县| 德兴市| 六盘水市| 钟祥市| 屏南县| 中卫市| 镇康县| 涟源市| 澜沧| 沙坪坝区|