二叉樹(shù)的線索化以及遍歷（前序、中序、后序）

2019-11-08 02:01:41

字體：大中小

供稿：網(wǎng)友

#define _CRT_SECURE_NO_WARNINGS#include <iostream>using namespace std;#include <stdlib.h>#include<string.h>enum ThdInfo{LINK,THREAD};template<class T>struct BinaryTreeThdNode{BinaryTreeThdNode(const T& data): pleft(NULL), PRight(NULL), pParent(NULL), _data(data), leftThd(LINK), rightThd(LINK){}BinaryTreeThdNode<T>* pleft; //左孩子BinaryTreeThdNode<T>* pright; //右孩子BinaryTreeThdNode<T>* pParent; //雙親結(jié)點(diǎn)T _data; ThdInfo leftThd; //左線索ThdInfo rightThd; //右線索};template<class T>class BinaryTreeThd{public:BinaryTreeThd():_pRoot(NULL){}BinaryTreeThd(T array[], size_t size){size_t index = 0;_CreateBinaryTree(_pRoot, array, size, index);}void PreOrderThd(){BinaryTreeThdNode<T>* prev = NULL;_PreOrderThd(_pRoot,prev);}void PreOrder(){_PreOrder(_pRoot);}void InOrderThd(){BinaryTreeThdNode<T>* prev = NULL;_InOrderThd(_pRoot,prev);}void InOrder(){_InOrder(_pRoot);}void PostOrderThd(){BinaryTreeThdNode<T>* prev = NULL;_PostOrderThd(_pRoot, prev);}void PostOrder(){_PostOrder(_pRoot);}private://前序遍歷void _PreOrder(BinaryTreeThdNode<T>* pRoot){BinaryTreeThdNode<T>* pCur = pRoot;while (pCur){//先找最左邊孩子并訪問(wèn)路徑上所有節(jié)點(diǎn)while (pCur->leftThd == LINK){cout << pCur->_data<< " ";pCur = pCur->pleft;}cout << pCur->_data << " ";//pCur = pCur->pright;//右孩子不存在連續(xù)訪問(wèn)后繼while (pCur && pCur->rightThd == THREAD){pCur = pCur->pright;cout << pCur->_data << " ";}if (pCur->leftThd == LINK){pCur = pCur->pleft;}else{pCur = pCur->pright;}}}//中序遍歷void _InOrder(BinaryTreeThdNode<T>* pRoot){BinaryTreeThdNode<T>* pCur = pRoot;while (pCur){//找最左邊的結(jié)點(diǎn)while (pCur->leftThd == LINK){pCur = pCur->pleft;}if (pCur->rightThd == LINK){cout << pCur->_data << " ";}else{while (pCur && pCur->rightThd == THREAD){cout << pCur->_data << " ";pCur = pCur->pright;}if (pCur->rightThd == LINK){cout << pCur->_data << " ";}if (pCur){pCur = pCur->pright;}}}}//后序遍歷void _PostOrder(BinaryTreeThdNode<T>*pRoot){BinaryTreeThdNode<T>* pCur = pRoot;BinaryTreeThdNode<T>* prev = NULL;while (pCur){//找最左邊的結(jié)點(diǎn)if (pCur->pleft != prev){while (pCur->leftThd == LINK){pCur = pCur->pleft;}}//處理左單支while (pCur && pCur->rightThd == THREAD){cout << pCur->_data << " ";prev = pCur;pCur = pCur->pright;}if (pCur == pRoot && pCur->pright==prev){cout << pCur->_data << " ";return;}//處理右單支while (pCur && pCur->pright == prev){cout << pCur->_data << " ";prev = pCur;pCur = pCur->pParent;}//處理當(dāng)前節(jié)點(diǎn)有右子樹(shù)的情況if (pCur && pCur->rightThd == LINK){pCur = pCur->pright;}}}//前序線索化void _PreOrderThd(BinaryTreeThdNode<T>*pRoot, BinaryTreeThdNode<T>*& prev){if (pRoot){//線索化當(dāng)前結(jié)點(diǎn)的左指針域if (pRoot->pleft == NULL){pRoot->pleft = prev;pRoot->leftThd = THREAD;}//線索化當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的右指針域if (prev &&prev->pright == NULL){prev->pright = pRoot;prev->rightThd = THREAD;}prev = pRoot;//遞歸線索化左子樹(shù)if (pRoot->leftThd == LINK){_PreOrderThd(pRoot->pleft, prev);}//遞歸線索化右子樹(shù)if (pRoot->rightThd == LINK){_PreOrderThd(pRoot->pright, prev);}}}//中序線索化void _InOrderThd(BinaryTreeThdNode<T>* pRoot,BinaryTreeThdNode<T>*& prev){if (pRoot){_InOrderThd(pRoot->pleft, prev);//線索化當(dāng)前結(jié)點(diǎn)的左指針域if (pRoot->pleft == NULL){pRoot->pleft = prev;pRoot->leftThd = THREAD;}//線索化當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的右指針域if (prev && prev->pright == NULL){prev->pright = pRoot;prev->rightThd = THREAD;}prev = pRoot;if (pRoot->rightThd == LINK){_InOrderThd(pRoot->pright, prev);}} } //后序線索化void _PostOrderThd(BinaryTreeThdNode<T>* pRoot, BinaryTreeThdNode<T>*& prev){if (pRoot){_PostOrderThd(pRoot->pleft, prev);_PostOrderThd(pRoot->pright, prev);//線索化當(dāng)前結(jié)點(diǎn)的左指針域if (pRoot->pleft == NULL){pRoot->pleft = prev;pRoot->leftThd = THREAD;}//線索化當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的右指針域if (prev && prev->pright == NULL){prev->pright = pRoot;prev->rightThd = THREAD;}prev = pRoot;}}//創(chuàng)建二叉樹(shù)void _CreateBinaryTree(BinaryTreeThdNode<T>*& pRoot, T array[], size_t size, size_t& index){if (index < size && array[index] != '#'){pRoot = new BinaryTreeThdNode<T>(array[index]);_CreateBinaryTree(pRoot->pleft, array, size, ++index);if (pRoot->pleft){pRoot->pleft->pParent = pRoot;}_CreateBinaryTree(pRoot->pright, array, size, ++index);if (pRoot->pright){pRoot->pright->pParent = pRoot;}}}private:BinaryTreeThdNode<T>* _pRoot;};void test(){char t[] = {'0','1','3','#','#','4','#','#','2','5'};BinaryTreeThd<char> bt(t,sizeof(t)/sizeof(t[0])); //bt.PreOrderThd();// bt.PreOrder();//bt.InOrderThd();//bt.InOrder();bt.PostOrderThd();bt.PostOrder();}int main(){test();system("pause");return 0;}

上一篇：leetcode 171 Excel Sheet Column Number

下一篇：leetcode No172. Factorial Trailing Zeroes