二叉树线索化

时间：2016-04-20 21:46:39 阅读：107 评论：0 收藏：0 [点我收藏+]

#include using namespace std; typedef enum { LINK, THREAD }PointerTag; template struct BinaryTreeNodeThd { T _data; BinaryTreeNodeThd* _left; BinaryTreeNodeThd* _right; PointerTag _leftTag; PointerTag _rightTag; BinaryTreeNodeThd() : _left(NULL), _right(NULL), _leftTag(LINK), _rightTag(LINK) {} BinaryTreeNodeThd(const T&data) :_data(data), _left(NULL), _right(NULL), _leftTag(LINK), _rightTag(LINK) {} }; template class BinaryTreeThd { public: BinaryTreeThd() :_root(NULL) {} BinaryTreeThd(const T*a, size_t size) { size_t index = 0; _root = _CreateTree(a, size, index); } BinaryTreeThd(const BinaryTreeThd& t) { _root = _Copy(t._root); } void InOrderThreading() { BinaryTreeNodeThd* prev = NULL; _InOrderThreading(_root, prev); } void PrevOrderThreading() { BinaryTreeNodeThd* prev = NULL; _PrevOrderThreading(_root, prev); } void PostOrderThreading() { BinaryTreeNodeThd* prev = NULL; _PostOrderThreading(_root, prev); } public: void InOrderThd() { BinaryTreeNodeThd* cur=_root; while (cur) { while (cur->_leftTag == LINK) { cur = cur->_left; } cout<_data<<" "; while(cur&&cur->_rightTag == THREAD) { cur = cur->_right; cout << cur->_data; } cur = cur->_right; } cout << endl; } void PrevOrderThd() { BinaryTreeNodeThd *cur =_root; while (cur) { while (cur&&cur->_leftTag == LINK) { cout << cur->_data << " "; cur = cur->_left; } cout << cur->_data << " "; while (cur&&cur->_rightTag == THREAD) { cur = cur->_right; cout << cur->_data << " "; } if (cur->_leftTag == LINK) cur = cur->_left; else cur = cur->_right; } } protected: BinaryTreeNodeThd* _CreateTree(const T*a, size_t size, size_t &index) { BinaryTreeNodeThd* root = NULL; if (index < size&&a[index] != ‘#‘) { root = new BinaryTreeNodeThd(a[index]); root->_left = _CreateTree(a, size, ++index); root->_right = _CreateTree(a, size, ++index); } return root; } void _InOrderThreading(BinaryTreeNodeThd* cur, BinaryTreeNodeThd*& prev) { if (cur == NULL) return; _InOrderThreading(cur->_left, prev); if (cur->_left == NULL) { cur->_leftTag = THREAD; cur->_left = prev; } if (prev&&prev->_rightTag == NULL) { prev->_rightTag = THREAD; prev->_right = cur; } prev = cur; _InOrderThreading(cur->_right, prev); } void _PrevOrderThreading(BinaryTreeNodeThd *cur, BinaryTreeNodeThd*& prev) { if (cur == NULL) { return; } if (cur->_left == NULL) { cur->_leftTag = THREAD; cur->_left = prev; } if (prev&&prev->_right== NULL) { prev->_rightTag = THREAD; prev->_right = cur; } prev = cur; if (cur->_leftTag == LINK) { _PrevOrderThreading(cur->_left, prev); } if (cur->_rightTag == LINK) { _PrevOrderThreading(cur->_right, prev); } } void _PostOrderThreading(BinaryTreeNodeThd *cur, BinaryTreeNodeThd*& prev) { if (cur == NULL) { return; } _PostOrderThreading(cur->_left, prev); _PostOrderThreading(cur->_right, prev); if (cur->_left == NULL) { cur->_leftTag = THREAD; cur->_left = prev; } if (prev&&prev->_right == NULL) { prev->_rightTag = THREAD; prev->_right = cur; } prev = cur; } BinaryTreeNodeThd* _Copy(BinaryTreeNodeThd* root) { if (root == NULL) return NULL; BinaryTreeNodeThd* newRoot = new BinaryTreeNodeThd(root->_data); newRoot->_left = _Copy(root->_left); newRoot->_right = _Copy(root->_right); return newRoot; } /*BinaryTreeThd& operator=(BinaryTreeThd*& t) { if (this != &t) { this->_Destory(_root); _root = _Copy(t._root); } return *this; }*/ //BinaryTreeNodeThd& operator=(BinaryTreeNodeThd t) //{ // swap(_root, t._root); // return *this; //} protected: BinaryTreeNodeThd *_root; }; int main() { int a[] = { 1, 2, 3, ‘#‘, ‘#‘, 4, ‘#‘, ‘#‘, 5, 6 }; BinaryTreeThd t(a, 10); BinaryTreeThd temp; t.InOrderThd(); t.InOrderThreading(); //t.PrevOrderThreading(); //t.PostOrderThreading(); cout << endl; system("pause"); return 0; }

二叉树线索化

原文：http://www.cnblogs.com/yuanshuang/p/5414477.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)