c++实现搜索二叉树
2021/10/28 11:11:58
本文主要是介绍c++实现搜索二叉树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
第一次接触树,各种递归搞得眼花,总算是按书上的代码,敲了下来,记录一下
/** * Created by admin on 2021/10/27. * 搜索二叉树实现 */ #ifndef HELLOWORLD_BINARY_SEARCH_TREE_H #define HELLOWORLD_BINARY_SEARCH_TREE_H #include <istream> template <typename Object> class BinarySearchTree{ struct TreeNode{ Object object; // 数据 TreeNode *left; // 左子树指针 TreeNode *right; // 右子树指针 }; // 二进制树 TreeNode *root; // 根节点 void insert(const Object &, TreeNode *&); // 插入元素 void printTree(TreeNode *&); // 打印树 bool contain(const Object&, TreeNode *&); // 查找树中是否有该元素 TreeNode *findMax(TreeNode *&); // 找最大值 TreeNode *findMin(TreeNode *&); // 找最小值 void remove(const Object &object, TreeNode *&); void makeEmpty(TreeNode *&); TreeNode *clone(TreeNode *); public: BinarySearchTree(): root(nullptr){}; // 普通构造函数 ~BinarySearchTree(){ makeEmpty(root);} // 析构函数 BinarySearchTree(const BinarySearchTree &rhs): root(nullptr){root = clone(rhs.root);} void insert(const Object &object){ insert(object, root);} // 插入数据 void printTree(){ printTree(root);}; // 打印树 bool contain(const Object &object){ return contain(object, root);} const Object &findMax(){return findMax(root)->object;} // 找最大值 const Object &findMin(){return findMin(root)->object;} // 找最小值 void remove(const Object &object){remove(object, root);} // 删除元素 }; template<typename Object> void BinarySearchTree<Object>::insert(const Object &object, TreeNode *&treeNode) { if (treeNode == nullptr) treeNode = new TreeNode{object, nullptr, nullptr}; // 新建节点 else if (object < treeNode->object) insert(object, treeNode->left); // 向左递归插入 else if (object > treeNode->object) insert(object, treeNode->right); // 向左递归插入 } template<typename Object> void BinarySearchTree<Object>::printTree(BinarySearchTree::TreeNode *&treeNode) { if (treeNode == nullptr) return; std::cout << treeNode->object; // 前序打印 if (treeNode->left != nullptr) printTree(treeNode->left); if (treeNode->right != nullptr) printTree(treeNode->right); } template<typename Object> bool BinarySearchTree<Object>::contain(const Object &object, BinarySearchTree::TreeNode *&treeNode) { if (treeNode == nullptr) return false; else if (object < treeNode->object) contain(object, treeNode->left); else if (object > treeNode->object) contain(object, treeNode->right); else return true; // 匹配 } template<typename Object> typename BinarySearchTree<Object>::TreeNode *BinarySearchTree<Object>::findMax(BinarySearchTree::TreeNode *&treeNode) { if (treeNode == nullptr) return nullptr; if (treeNode->right == nullptr) return treeNode; return findMax(treeNode->right); } template<typename Object> typename BinarySearchTree<Object>::TreeNode *BinarySearchTree<Object>::findMin(BinarySearchTree::TreeNode *&treeNode) { if (treeNode == nullptr) return nullptr; if (treeNode->left == nullptr) return treeNode; return findMin(treeNode->left); } template<typename Object> void BinarySearchTree<Object>::remove(const Object &object, BinarySearchTree::TreeNode *&treeNode) { if (treeNode == nullptr) return; else if (object < treeNode->object) remove(object, treeNode->left); else if (object > treeNode->object) remove(object, treeNode->right); else if (treeNode->left != nullptr && treeNode->right != nullptr){ // 双节点的情况 treeNode->object = findMin(treeNode->right)->object; // 值用右树最小值替换 remove(treeNode->object, treeNode->right); // 找到替换的节点 }else{ TreeNode *oldTreeNode = treeNode; treeNode = treeNode->left != nullptr? treeNode->left: treeNode->right; delete oldTreeNode; } } template<typename Object> void BinarySearchTree<Object>::makeEmpty(BinarySearchTree::TreeNode *&treeNode) { if (treeNode == nullptr) return; makeEmpty(treeNode->left); makeEmpty(treeNode->right); delete treeNode; treeNode = nullptr; } template<typename Object> typename BinarySearchTree<Object>::TreeNode *BinarySearchTree<Object>::clone(BinarySearchTree::TreeNode *treeNode) { if (treeNode == nullptr) return nullptr; else return new TreeNode{treeNode->object, clone(treeNode->left), clone(treeNode->right)}; } #endif //HELLOWORLD_BINARY_SEARCH_TREE_H
这篇关于c++实现搜索二叉树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升