二叉树(二)线索二叉树
2020-02-01 16:00:35来源:博客园 阅读 ()
二叉树(二)线索二叉树
二叉树创建 先序线索、中序线索,通过线索进行的 先序遍历、中序遍历。
main.cpp:
#include <iostream> #include <queue> #include "ThreadedBinaryTree.h" using namespace std; int main() { queue<char> qu({ 'a','b','c',0,0,'d','e',0,0,'f','g',0,0,0,'h','i',0,0,'j',0,0 }); ThreadedBinaryTree<char> thBinTree(0, qu); cout << "preorderTraversal:\n\t"; thBinTree.preorderTraversal(); cout << "\n\npreorderTraversalByThread:\n\t"; thBinTree.preorderTraversalByThread(); cout << "\n\ninorderTraversal:\n\t"; thBinTree.inorderTraversal(); cout << "\n\ninorderTraversalByThread:\n\t"; thBinTree.inorderTraversalByThread(); cout << "\n\npostorderTraversal:\n\t"; thBinTree.postorderTraversal(); cout << "\n\nlevelTraversal:\n\t"; thBinTree.levelTraversal(); cout << endl; return 0; }
ThreadedBinaryTree.h:
#pragma once #ifndef __THREADEDBINARYTREE_H__ #define __THREADEDBINARYTREE_H__ #include <queue> #include <stack> template<typename _Ty> class ThreadedBinaryTree { private: enum class Tag :bool { LINK = 0, THREAD }; struct Node { _Ty data; Tag Ltag = Tag::LINK; Tag Rtag = Tag::LINK; Node* left = nullptr; Node* right = nullptr; Node(const _Ty& _data) :data(_data) {} }; public: enum class ThreadType { NONE = 0, INORDER, PREORDER }; public: ThreadedBinaryTree(const _Ty& _val) :nullVal(_val) {} ThreadedBinaryTree(const _Ty& _val, std::queue<_Ty>& _qu) :nullVal(_val) { creatTree(_qu, root); } ~ThreadedBinaryTree() { clear(root); } void clear() { head = nullptr; threadType = ThreadType::NONE; clear(root); } size_t size() const { return size_n; } void setNullValue(const _Ty& _val) { nullVal = _val; } void creatTree(std::queue<_Ty>& _qu) { if (root != nullptr) clear(root); creatTree(_qu, root); } void preorderTraversal() const { preorderTraversal(root); } void inorderTraversal() const { inorderTraversal(root); } void postorderTraversal() const { postorderTraversal(root); } void levelTraversal() const { levelTraversal(root); } void creatThread(ThreadType); void inorderTraversalByThread(); void preorderTraversalByThread(); private: void creatTree(std::queue<_Ty>&, Node*&); void clear(Node*&); void preorderTraversal(Node*) const; void inorderTraversal(Node*) const; void postorderTraversal(Node*) const; void levelTraversal(Node*) const; void creatInorderThread(Node*, Node*& _pre); void creatPreorderThread(Node*, Node*& _pre); private: _Ty nullVal; size_t size_n = 0; Node* root = nullptr; Node* head = nullptr; ThreadType threadType = ThreadType::NONE; }; template<typename _Ty> void ThreadedBinaryTree<_Ty>::creatTree(std::queue<_Ty>& _qu, Node*& _node) { if (_qu.empty()) return; if (_qu.front() == nullVal) { _qu.pop(); return; } _node = new Node(_qu.front()); _qu.pop(); ++size_n; creatTree(_qu, _node->left); creatTree(_qu, _node->right); } template<typename _Ty> void ThreadedBinaryTree<_Ty>::clear(Node*& _node) { if (_node == nullptr) return; if (_node->left != nullptr && _node->Ltag == Tag::LINK) clear(_node->left); if (_node->right != nullptr && _node->Rtag == Tag::LINK) clear(_node->right); delete _node; _node = nullptr; --size_n; } template<typename _Ty> void ThreadedBinaryTree<_Ty>::preorderTraversal(Node* _node) const { if (_node == nullptr) return; std::cout << _node->data << " "; if (_node->left != nullptr && _node->Ltag == Tag::LINK) preorderTraversal(_node->left); if (_node->right != nullptr && _node->Rtag == Tag::LINK) preorderTraversal(_node->right); } template<typename _Ty> void ThreadedBinaryTree<_Ty>::inorderTraversal(Node* _node) const { if (_node == nullptr) return; if (_node->left != nullptr && _node->Ltag == Tag::LINK) inorderTraversal(_node->left); std::cout << _node->data << " "; if (_node->right != nullptr && _node->Rtag == Tag::LINK) inorderTraversal(_node->right); } template<typename _Ty> void ThreadedBinaryTree<_Ty>::postorderTraversal(Node* _node) const { if (_node == nullptr) return; if (_node->left != nullptr && _node->Ltag == Tag::LINK) postorderTraversal(_node->left); if (_node->right != nullptr && _node->Rtag == Tag::LINK) postorderTraversal(_node->right); std::cout << _node->data << " "; } template<typename _Ty> void ThreadedBinaryTree<_Ty>::levelTraversal(Node* _node) const { if (_node == nullptr) return; std::queue<Node*> nodePointers; nodePointers.push(_node); while (!nodePointers.empty()) { Node* cur = nodePointers.front(); std::cout << cur->data << " "; if (cur->left != nullptr && cur->Ltag == Tag::LINK) nodePointers.push(cur->left); if (cur->right != nullptr && cur->Rtag == Tag::LINK) nodePointers.push(cur->right); nodePointers.pop(); } } template<typename _Ty> void ThreadedBinaryTree<_Ty>::creatInorderThread(Node* _node, Node*& _pre) { if (_node == nullptr) return; if (_node->Ltag == Tag::LINK) creatInorderThread(_node->left, _pre); if (_node->left == nullptr || _node->Ltag == Tag::THREAD) { _node->Ltag = Tag::THREAD; _node->left = _pre; } if (_pre != nullptr && (_pre->right == nullptr || _pre->Rtag == Tag::THREAD)) { _pre->Rtag = Tag::THREAD; _pre->right = _node; } _pre = _node; if (_node->Rtag == Tag::LINK) creatInorderThread(_node->right, _pre); } template<typename _Ty> void ThreadedBinaryTree<_Ty>::creatPreorderThread(Node* _node, Node*& _pre) { if (_node == nullptr) return; if (_node->left == nullptr || _node->Ltag == Tag::THREAD) { _node->Ltag = Tag::THREAD; _node->left = _pre; } if (_pre != nullptr && (_pre->right == nullptr || _pre->Rtag == Tag::THREAD)) { _pre->Rtag = Tag::THREAD; _pre->right = _node; } _pre = _node; if (_node->Ltag == Tag::LINK) creatPreorderThread(_node->left, _pre); if (_node->Rtag == Tag::LINK) creatPreorderThread(_node->right, _pre); } template<typename _Ty> void ThreadedBinaryTree<_Ty>::creatThread(ThreadType _type) { if (root == nullptr || _type == threadType) return; if (_type != ThreadType::INORDER && _type != ThreadType::PREORDER) { delete head; head = nullptr; threadType = _type; return; } if (head != nullptr && _type != threadType) delete head; head = new Node(static_cast<_Ty>(0)); head->left = root; threadType = _type; Node* temp = nullptr; switch (threadType) { case ThreadType::INORDER: creatInorderThread(root, temp); break; case ThreadType::PREORDER: creatPreorderThread(root, temp); break; } head->right = temp; } template<typename _Ty> void ThreadedBinaryTree<_Ty>::inorderTraversalByThread() { if (root != nullptr) creatThread(ThreadType::INORDER); if (head == nullptr) return; Node* temp = head->left; while (temp != nullptr) { while (temp->Ltag == Tag::LINK) temp = temp->left; std::cout << temp->data << " "; while (temp != nullptr && temp->Rtag == Tag::THREAD) { temp = temp->right; if (temp != nullptr) std::cout << temp->data << " "; } if (temp != nullptr) temp = temp->right; } } template<typename _Ty> void ThreadedBinaryTree<_Ty>::preorderTraversalByThread() { if (root != nullptr) creatThread(ThreadType::PREORDER); if (head == nullptr) return; Node* temp = head->left; while (temp != nullptr) { std::cout << temp->data << " "; if (temp->Ltag == Tag::LINK) temp = temp->left; else temp = temp->right; } } #endif // !__THREADEDBINARYTREE_H__
原文链接:https://www.cnblogs.com/teternity/p/ThreadedBinaryTree.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 二叉搜索树_BST 2020-05-30
- 二叉树 2020-05-02
- 二叉排序树 2020-05-02
- 二叉堆(3)SkewHeap 2020-02-20
- 二叉堆(2)LeftistHeap 2020-02-19
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash