二叉树C++实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了二叉树C++实现,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4272字,纯文字阅读大概需要7分钟。
内容图文
二叉搜索树的代码实现,有插入、查找、删除等基本功能。
需要注意的是,当类中有私有类pClass且在类外声明的成员函数的返回值是pClass类型的时候,需要在pClass前加typename。比如说
template <typename Comparable> typename binarysearchtree<Comparable>::BinaryNode* binarysearchtree<Comparable>::findMax(BinaryNode* t)const { if (t == NULL) return NULL; if (t->right == NULL) return t; return findMin(t->right); }
这里的typename如果去掉的话就会报错
warning C4346: “BinaryNode”: 依赖名称不是类型 error C2061: 语法错误: 标识符“BinaryNode”
这么做的原因,我目前还没搞清楚。
#pragma once template <typename Comparable> class binarysearchtree { public: binarysearchtree() { BinaryNode* root = nullptr; } binarysearchtree(const binarysearchtree& rhs) { this = rhs; } ~binarysearchtree() { makeEmpty(); } const Comparable& findMin() const { return findMin(root); } const Comparable& findMax() const { return findMax(root); } bool contains(const Comparable& x) const; bool isEmpty() const { return root == nullptr; } void printTree() const { printTree(root, 0); } void makeEmpty() { makeEmpty(root); } void insert(const Comparable& x); void remove(const Comparable& x); const binarysearchtree& operator=(const binarysearchtree& rhs) { if (*this != rhs) { makeEmpty(); root = clone(rhs.root); } return &this; } private: struct BinaryNode { Comparable element; BinaryNode* left; BinaryNode* right; BinaryNode(const Comparable& theElement, BinaryNode* lt, BinaryNode* rt) : element(theElement), left(lt), right(rt) {} }; BinaryNode* root; void insert(const Comparable& x, BinaryNode*& t) const; void remove(const Comparable& x, BinaryNode*& t) const; BinaryNode* findMin(BinaryNode* t)const; BinaryNode* findMax(BinaryNode* t)const; bool contains(const Comparable& x, BinaryNode* t) const; void makeEmpty(BinaryNode*& t); void printTree(BinaryNode* t, const int& depth)const; BinaryNode* clone(BinaryNode* t) const; }; template <typename Comparable> bool binarysearchtree<Comparable>::contains(const Comparable& x) const { return contains(x, root); } template <typename Comparable> void binarysearchtree<Comparable>::insert(const Comparable& x) { insert(x, root); } template <typename Comparable> void binarysearchtree<Comparable>::remove(const Comparable& x) { remove(x, root); } template <typename Comparable> bool binarysearchtree<Comparable>::contains(const Comparable& x, BinaryNode* t) const { if (t == NULL) return false; else if (t->element > x) return contains(x, t->left); else if (t->element < x) return contains(x, t->right); else return true; } template <typename Comparable> typename binarysearchtree<Comparable>::BinaryNode* binarysearchtree<Comparable>::findMin(BinaryNode* t)const{ if (t == NULL) return NULL; if (t->left == NULL) return t; return findMin(t->left); } template <typename Comparable> typename binarysearchtree<Comparable>::BinaryNode* binarysearchtree<Comparable>::findMax(BinaryNode* t)const { if (t == NULL) return NULL; if (t->right == NULL) return t; return findMin(t->right); } template <typename Comparable> void binarysearchtree<Comparable>::insert(const Comparable& x, BinaryNode*& t) const { if (t == NULL) t = new BinaryNode(x, NULL, NULL); else if (t->element > x) insert(x, t->left); else if (t->element < x) insert(x, t->right); else; } template <typename Comparable> void binarysearchtree<Comparable>::remove(const Comparable& x, BinaryNode*& t) const { if (t == NULL) return; if (t->element > x) remove(x, t->left); else if (t->element < x) remove(x, t->right); else if (t->right != NULL && t->left != NULL) { t->element = findMin(t->right)->element; remove(t->element, t->right); } else { BinaryNode* oldNode = t; t = (t->left != NULL) ? t->left : t->right; delete oldNode; } } template<typename Comparable> void binarysearchtree<Comparable>::makeEmpty(BinaryNode*& t) { if (t != nullptr) { makeEmpty(t->left); makeEmpty(t->right); delete t; t = nullptr; } } template<typename Comparable> typename binarysearchtree<Comparable>::BinaryNode* binarysearchtree<Comparable>::clone(BinaryNode* t) const { if (t == nullptr) return t; return new BinaryNode(t->element, clone(t->left), clone(t->right)); } template<typename Comparable> void binarysearchtree<Comparable>::printTree(BinaryNode* t, const int& i)const { if (t != nullptr) { printTree(t->left, i + 1); std::cout << string(i, '\t') << t->element << std::endl; printTree(t->right, i + 1); } }
内容总结
以上是互联网集市为您收集整理的二叉树C++实现全部内容,希望文章能够帮你解决二叉树C++实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。