二叉树(1)二叉树基本操作通用接口
2020-02-06 16:02:13来源:博客园 阅读 ()
二叉树(1)二叉树基本操作通用接口
二叉树的基本操作,为 二叉查找(搜索、排序)树、二叉平衡树(AVL树)、红黑树 等提供基础接口。
名称空间:namespace BTO
基础接口如:
① 遍历操作:
递归 和 非递归 版本的 先序、中序、后序 遍历。
层序遍历。
接口原型:void xxxTraversal(_Node*& _node, const _Func& _func);
其中 _Func 为函数对象,接受一个 _Node* 的参数,用于在遍历时作用于各个节点。
② find 操作:
寻找指定键的节点(迭代和非迭代版本)。
寻找键最大最小值的节点。
寻找前驱后继。
获取二叉树的高度。
接口原型:_Node* xxxfindxxx(_Node*& _node, const _Ty& _key);
其中 _Ty 为键类型。
③ 插入操作:
接口原型:std::pair<_Node*, bool> insert(_Node*& _node, const _Ty& _key);
其中 将键为 _Ty 类型的值 _key 添加到节点为 _Node* 类型的根为 _node 的二叉树中。
返回插入节点的指针和是否成功插入的 bool 值(不存在键值相同的节点,若插入键已经存在,则插入失败返回 pair(nullptr, false) )。
④ 复制操作(迭代和非迭代版本):
接口原型:_Node* xxxCopy(_Node*& _node, _Node* _ret);
其中 _node 为待复制二叉树的根节点,_ret 必须为 nullptr 且默认为 nullptr,返回新树的根节点 _ret。
⑤ 清空操作:
接口原型:void clear(_Node*& _node);
清除 _node 为根的二叉树,务必保证 _node 不是子树。
测试代码 main.cpp:
#include <iostream> #include "BinaryTreeOperations.h" using namespace std; template<typename _Ty> struct Node { _Ty key; Node* left = nullptr; Node* right = nullptr; Node* parent = nullptr; Node(const _Ty& _key) :key(_key) {} }; int main() { Node<int>* root = nullptr; auto il = { 5,3,7,4,8,1,0,9,2,6 }; for (auto& x : il) BTO::insert(root, x); cout << "先序遍历:" << endl; BTO::preorderTraversal(root, [](const Node<int>* _node) { cout << _node->key << " "; }); cout << endl; BTO::iterativePreorderTraversal(root, [](const Node<int>* _node) { cout << _node->key << " "; }); cout << endl << endl; cout << "中序遍历:" << endl; BTO::inorderTraversal(root, [](const Node<int>* _node) { cout << _node->key << " "; }); cout << endl; BTO::iterativeInorderTraversal(root, [](const Node<int>* _node) { cout << _node->key << " "; }); cout << endl << endl; cout << "后序遍历:" << endl; BTO::postorderTraversal(root, [](const Node<int>* _node) { cout << _node->key << " "; }); cout << endl; BTO::iterativePostorderTraversal(root, [](const Node<int>* _node) { cout << _node->key << " "; }); cout << endl << endl; cout << "层序遍历:" << endl; BTO::levelTraversal(root, [](const Node<int>* _node) { cout << _node->key << " "; }); cout << endl << endl; cout << "BTO::find(root, 5)->key:" << endl; auto p5 = BTO::find(root, 5); if (p5 != nullptr) cout << p5->key << ", " << BTO::iterativeFind(root, 5)->key << endl; else cout << "nullptr" << endl; cout << "BTO::find(root, 11)->key:" << endl; auto p11 = BTO::find(root, 11); if (p11 != nullptr) cout << p11->key << ", " << BTO::iterativeFind(root, 11)->key << endl; else cout << "nullptr" << endl << endl; cout << "BTO::findMaximum(root)->key:" << endl; cout << BTO::findMaximum(root)->key << endl; cout << "BTO::findMinimum(root)->key:" << endl; cout << BTO::findMinimum(root)->key << endl << endl; cout << "BTO::findPrecursor(p5)->key:" << endl; cout << BTO::findPrecursor(p5)->key << endl; cout << "BTO::findSuccessor(p5)->key:" << endl; cout << BTO::findSuccessor(p5)->key << endl << endl; auto root2 = BTO::copy(root); auto root3 = BTO::copy(root); cout << "BTO::getLevel(root):" << endl; cout << BTO::getLevel(root) << endl; cout << "BTO::getLevel(root2):" << endl; cout << BTO::getLevel(root2) << endl; cout << "BTO::getLevel(root3):" << endl; cout << BTO::getLevel(root3) << endl << endl; BTO::clear(root); BTO::clear(root2); BTO::clear(root3); return 0; }
头文件 BinaryTreeOperations.h:
#pragma once #ifndef __BINARY_TREE_OPERATIONS_H__ #define __BINARY_TREE_OPERATIONS_H__ /* The node must have members which are named: "key"、"left"、"right"、"parent" */ #include <stack> #include <queue> #include <utility> namespace BTO { /* Traversal operations */ // Recursive operations template<typename _Node, typename _Func> void preorderTraversal(_Node*&, const _Func&); template<typename _Node, typename _Func> void inorderTraversal(_Node*&, const _Func&); template<typename _Node, typename _Func> void postorderTraversal(_Node*&, const _Func&); // Iterative operations template<typename _Node, typename _Func> void iterativePreorderTraversal(_Node*&, const _Func&); template<typename _Node, typename _Func> void iterativeInorderTraversal(_Node*&, const _Func&); template<typename _Node, typename _Func> void iterativePostorderTraversal(_Node*&, const _Func&); // Level traversal template<typename _Node, typename _Func> void levelTraversal(_Node*&, const _Func&); /* Find operations */ template<typename _Node, typename _Ty> _Node* find(_Node*&, const _Ty&); template<typename _Node, typename _Ty> _Node* iterativeFind(_Node*&, const _Ty&); template<typename _Node> _Node* findMaximum(_Node*&); template<typename _Node> _Node* findMinimum(_Node*&); template<typename _Node> _Node* findPrecursor(_Node*&); template<typename _Node> _Node* findSuccessor(_Node*&); template<typename _Node> size_t getLevel(_Node*&); /* Inset operation */ template<typename _Node, typename _Ty> std::pair<_Node*, bool> insert(_Node*&, const _Ty&); /* Copy operation */ template<typename _Node> _Node* copy(_Node*&, _Node* _ret = nullptr); template<typename _Node> _Node* iterativeCopy(_Node*&, _Node* _ret = nullptr); /* Clear operation */ template<typename _Node> void clear(_Node*&); } /* Traversal operations */ template<typename _Node, typename _Func> void BTO::preorderTraversal(_Node*& _node, const _Func& _func) { if (_node == nullptr) return; _func(_node); preorderTraversal(_node->left, _func); preorderTraversal(_node->right, _func); } template<typename _Node, typename _Func> void BTO::inorderTraversal(_Node*& _node, const _Func& _func) { if (_node == nullptr) return; inorderTraversal(_node->left, _func); _func(_node); inorderTraversal(_node->right, _func); } template<typename _Node, typename _Func> void BTO::postorderTraversal(_Node*& _node, const _Func& _func) { if (_node == nullptr) return; postorderTraversal(_node->left, _func); postorderTraversal(_node->right, _func); _func(_node); } template<typename _Node, typename _Func> void BTO::iterativePreorderTraversal(_Node*& _node, const _Func& _func) { if (_node == nullptr) return; std::stack<_Node*> nodePointers; _Node* cur = _node; while (cur != nullptr || !nodePointers.empty()) { _func(cur); nodePointers.push(cur); cur = cur->left; while (cur == nullptr && !nodePointers.empty()) { cur = nodePointers.top()->right; nodePointers.pop(); } } } template<typename _Node, typename _Func> void BTO::iterativeInorderTraversal(_Node*& _node, const _Func& _func) { if (_node == nullptr) return; std::stack<_Node*> nodePointers; _Node* cur = _node; while (cur != nullptr || !nodePointers.empty()) { if (cur->left != nullptr) { nodePointers.push(cur); cur = cur->left; } else { _func(cur); cur = cur->right; while (cur == nullptr && !nodePointers.empty()) { cur = nodePointers.top(); nodePointers.pop(); _func(cur); cur = cur->right; } } } } template<typename _Node, typename _Func> void BTO::iterativePostorderTraversal(_Node*& _node, const _Func& _func) { if (_node == nullptr) return; std::stack<_Node*> nodePointers; nodePointers.push(_node); _Node* last = nullptr; _Node* cur = nullptr; while (!nodePointers.empty()) { cur = nodePointers.top(); if ((cur->left == nullptr && cur->right == nullptr) || last != nullptr && (last == cur->left || last == cur->right)) { _func(cur); nodePointers.pop(); last = cur; } else { if (cur->right != nullptr) nodePointers.push(cur->right); if (cur->left != nullptr) nodePointers.push(cur->left); } } } template<typename _Node, typename _Func> void BTO::levelTraversal(_Node*& _node, const _Func& _func) { if (_node == nullptr) return; std::queue<_Node*> nodePointers; nodePointers.push(_node); _Node* cur = nullptr; while (!nodePointers.empty()) { cur = nodePointers.front(); _func(cur); if (cur->left != nullptr) nodePointers.push(cur->left); if (cur->right != nullptr) nodePointers.push(cur->right); nodePointers.pop(); } } /* Find operations */ template<typename _Node, typename _Ty> _Node* BTO::find(_Node*& _node, const _Ty& _key) { if (_node == nullptr || _key == _node->key) return _node; if (_key < _key) return find(_node->left, _key); else return find(_node->right, _key); } template<typename _Node, typename _Ty> _Node* BTO::iterativeFind(_Node*& _node, const _Ty& _key) { _Node* cur = _node; while (cur != nullptr && cur->key != _key) { if (_key < cur->key) cur = cur->left; else cur = cur->right; } return cur; } template<typename _Node> _Node* BTO::findMaximum(_Node*& _node) { _Node* cur = _node; if (cur == nullptr) return cur; while (cur->right != nullptr) cur = cur->right; return cur; } template<typename _Node> _Node* BTO::findMinimum(_Node*& _node) { _Node* cur = _node; if (cur == nullptr) return cur; while (cur->left != nullptr) cur = cur->left; return cur; } template<typename _Node> _Node* BTO::findPrecursor(_Node*& _node) { _Node* cur = _node; if (cur->left != nullptr) return findMaximum(cur->left); _Node* par = cur->parent; while ((par != nullptr) && (cur == par->left)) { cur = par; par = par->parent; } return par; } template<typename _Node> _Node* BTO::findSuccessor(_Node*& _node) { _Node* cur = _node; if (cur->right != nullptr) return findMinimum(cur->right); _Node* par = cur->parent; while ((par != nullptr) && (cur == par->right)) { cur = par; par = par->parent; } return par; } template<typename _Node> size_t BTO::getLevel(_Node*& _node) { if (_node == nullptr) 0; size_t n = 0; std::queue<_Node*> nodePointers; nodePointers.push(_node); while (!nodePointers.empty()) { _Node* levelBegin = nodePointers.front(); _Node* levelEnd = nodePointers.back(); _Node* cur = levelBegin; while (true) { if (cur->left != nullptr) nodePointers.push(cur->left); if (cur->right != nullptr) nodePointers.push(cur->right); if (cur == levelEnd) break; nodePointers.pop(); cur = nodePointers.front(); } nodePointers.pop(); ++n; } return n; } /* Inset operation */ template<typename _Node, typename _Ty> std::pair<_Node*, bool> BTO::insert(_Node*& _node, const _Ty& _key) { std::pair<_Node*, bool> ret(nullptr, true); if (_node == nullptr) { _node = new _Node(_key); ret.first = _node; return ret; } _Node* cur = _node; while (true) { if (_key == cur->key) { ret.second = false; return ret; } else if (_key < cur->key && cur->left != nullptr) cur = cur->left; else if (_key > cur->key&& cur->right != nullptr) cur = cur->right; else break; } _Node* newNode = new _Node(_key); if (_key < cur->key) cur->left = newNode; else cur->right = newNode; newNode->parent = cur; ret.first = newNode; newNode = nullptr; return ret; } /* Copy operations */ template<typename _Node> _Node* BTO::copy(_Node*& _node, _Node* _ret) { if (_ret != nullptr) return nullptr; preorderTraversal(_node, [&_ret](_Node*& _no) { insert(_ret, _no->key); }); return _ret; } template<typename _Node> _Node* BTO::iterativeCopy(_Node*& _node, _Node* _ret) { if (_ret != nullptr) return nullptr; iterativePreorderTraversal(_node, [&_ret](_Node*& _no) { insert(_ret, _no->key); }); return _ret; } /* Clear operation */ template<typename _Node> void BTO::clear(_Node*& _node) { if (_node == nullptr) return; clear(_node->left); clear(_node->right); delete _node; _node = nullptr; } #endif // !__BINARY_TREE_OPERATIONS_H__
原文链接:https://www.cnblogs.com/teternity/p/BinaryTreeOperations.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:洛谷P1014 Cantor表
下一篇:结题报告
- 二叉搜索树_BST 2020-05-30
- 二叉树 2020-05-02
- 二叉排序树 2020-05-02
- C++ 字符集 2020-03-26
- 二叉堆(3)SkewHeap 2020-02-20
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