国产探花免费观看_亚洲丰满少妇自慰呻吟_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是否為空

 

 

               


發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 泗阳县| 望奎县| 兴文县| 呼玛县| 聊城市| 广宁县| 洪洞县| 临沂市| 磴口县| 邵阳县| 集安市| 边坝县| 正定县| 金山区| 新河县| 元氏县| 攀枝花市| 改则县| 东城区| 乌鲁木齐县| 遂川县| 徐水县| 宁晋县| 富顺县| 邢台市| 自治县| 桂平市| 武威市| 永兴县| 万宁市| 兰考县| 宾川县| 神池县| 和林格尔县| 晴隆县| 顺昌县| 芮城县| 怀远县| 吉木萨尔县| 区。| 贵阳市|