您好,登錄后才能下訂單哦!
二叉樹是一種非線性結(jié)構(gòu),遍歷二叉樹幾乎都是通過遞歸或者用棧輔助實(shí)現(xiàn)非遞歸的遍歷。用二叉樹作為存儲結(jié)構(gòu)時,取到一個節(jié)點(diǎn),只能獲取節(jié)點(diǎn)的左孩子和右孩子,不能直接得到節(jié)點(diǎn)的任一遍歷序列的前驅(qū)或者后繼。為了保存這種在遍歷中需要的信息,我們利用二叉樹中指向左右子樹的空指針來存放節(jié)點(diǎn)的前驅(qū)和后繼信息。
#include <iostream> using namespace std; enum PointerTag {THREAD, LINK}; template<class T> struct BinaryTreeNodeThd { T _data; //數(shù)據(jù) BinaryTreeNodeThd<T>* _left; //左孩子 BinaryTreeNodeThd<T>* _right; //右孩子 PointerTag _leftTag; //左孩子線索標(biāo)志 PointerTag _rightTag; //右孩子線索標(biāo)志 BinaryTreeNodeThd(const T& data) :_data(data) ,_left(NULL) ,_right(NULL) ,_leftTag(LINK) ,_rightTag(LINK) {} }; template<class T> class BinaryTreeThd { public: BinaryTreeThd(const T* array, size_t size, const T& invalid) { size_t index = 0; _root = _CreateTree(array, size, index, invalid); } ~BinaryTreeThd() { _DestroyTree(_root); _root = NULL; } void InOrderThreading() { BinaryTreeNodeThd<T>* prev = NULL; _InOrderThreading(_root, prev); } void PreOrderThreading() { BinaryTreeNodeThd<T>* prev = NULL; _PreOrderThreading(_root, prev); } void PostOrderThreading() { BinaryTreeNodeThd<T>* prev = NULL; _PostOrderThreading(_root, prev); } void PreOrderThd() { BinaryTreeNodeThd<T>* cur = _root; while (cur) { while (cur && LINK == cur->_leftTag) { cout<<cur->_data<<" "; cur = cur->_left; } cout<<cur->_data<<" "; cur = cur->_right; } cout<<endl; } void InOrderThd() { BinaryTreeNodeThd<T>* cur = _root; while (cur) { while (cur && LINK == cur->_leftTag) { cur = cur->_left; } cout<<cur->_data<<" "; while (THREAD == cur->_rightTag) { cur = cur->_right; cout<<cur->_data<<" "; } cur = cur->_right; } cout<<endl; } protected: BinaryTreeNodeThd<T>* _CreateTree(const T* array, size_t size, size_t& index, const T& invalid) { BinaryTreeNodeThd<T>* root = NULL; if (index < size && array[index] != invalid) { root = new BinaryTreeNodeThd<T>(array[index]); root->_left = _CreateTree(array, size, ++index, invalid); root->_right = _CreateTree(array, size, ++index, invalid); } return root; } void _DestroyTree(BinaryTreeNodeThd<T>* root) { if (NULL == root) return; if (LINK == root->_leftTag) _DestroyTree(root->_left); if (LINK == root->_rightTag) _DestroyTree(root->_right); delete root; } void _PreOrderThreading(BinaryTreeNodeThd<T>* cur, BinaryTreeNodeThd<T>*& prev) { if (NULL == cur) return; if (NULL == cur->_left) { cur->_leftTag = THREAD; cur->_left = prev; } if (prev && NULL == prev->_right) { prev->_rightTag = THREAD; prev->_right = cur; } prev = cur; if (cur->_leftTag == LINK) _PreOrderThreading(cur->_left, prev); if (cur->_rightTag == LINK) _PreOrderThreading(cur->_right, prev); } void _InOrderThreading(BinaryTreeNodeThd<T>* cur, BinaryTreeNodeThd<T>*& prev) { if (NULL == cur) return; _InOrderThreading(cur->_left, prev); if (NULL == cur->_left) { cur->_leftTag = THREAD; cur->_left = prev; } if (prev && NULL == prev->_right) { prev->_rightTag = THREAD; prev->_right = cur; } prev = cur; _InOrderThreading(cur->_right, prev); } void _PostOrderThreading(BinaryTreeNodeThd<T>* cur, BinaryTreeNodeThd<T>*& prev) { if (NULL == cur) return; _PostOrderThreading(cur->_left, prev); _PostOrderThreading(cur->_right, prev); if (cur->_left == NULL) { cur->_leftTag = THREAD; cur->_left = prev; } if (prev && NULL == prev->_right) { prev->_rightTag = THREAD; prev->_right = cur; } prev = cur; } protected: BinaryTreeNodeThd<T>* _root; }; void Test() { int a[] = {1, 2, 3, '#', '#', 4, '#', '#', 5, 6}; BinaryTreeThd<int> t1(a, sizeof(a)/sizeof(a[0]), '#'); t1.PreOrderThreading(); t1.PreOrderThd(); BinaryTreeThd<int> t2(a, sizeof(a)/sizeof(a[0]), '#'); t2.InOrderThreading(); t2.InOrderThd(); int a1[] = {1, 2, '#', 3, '#', '#', 4, 5, '#', 6, '#', 7, '#', '#', 8}; BinaryTreeThd<int> t3(a1, sizeof(a1)/sizeof(a1[0]), '#'); t3.PreOrderThreading(); t3.PreOrderThd(); } int main() { Test(); return 0; }
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。