構建節點:多了雙親節點
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}測試一下特殊的右單支的情況:

ZG{SX7F7AMJP)[ZXA.png)
分析右單支:注意(3)步

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

新聞熱點
疑難解答