首页 / C++ / c++ 实现二叉搜索树
c++ 实现二叉搜索树
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了c++ 实现二叉搜索树,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2321字,纯文字阅读大概需要4分钟。
内容图文
******************************.h部分****************************
#ifndef BINARYSERCHTREE_BST_H #define BINARYSERCHTREE_BST_H #include <iostream> template <class T> class BST;//声明 template <class T> class element { public: T key; //可以添加更多的数据 private: }; template <class T> class BSTnode { friend class BST<T>; public: private: element<T> data; BSTnode<T>* leftnode; BSTnode<T>* rightnode; void dispaly(int i); }; template <class T> class BST { public: BST():root(0){}; bool insert(element<T>& a); BSTnode<T>* search(element<T>& a);//递归搜索 BSTnode<T>* search(BSTnode<T>*,element<T>&);//递归搜索 BSTnode<T>* itersearch(element<T>&);//迭代搜索 void display(); private: BSTnode<T>* root; }; template <class T> void BSTnode<T>::dispaly(int i) { std::cout<<"posizition:"<<i; std::cout<<"data.key:"<<data.key<<"\n"; if (leftnode) leftnode->dispaly(2*i); if(rightnode) rightnode->dispaly(2*i+1); } template <class T> void BST<T>::display() { if (root) { root->dispaly(1); } else { cout<<"bts 为0 cannot be display"<<endl; } } template <class T> bool BST<T>::insert(element<T> &a) { BSTnode<T>* p=root; BSTnode<T>* q=0; //指向当前操作指针的父节点。 //insert之前需要查找 while (p) { q=p;//保存每次p指针变化前的节点 if(a.key==p->data.key) return false;//发生重复 else if (a.key<p->data.key) p=p->leftnode; else if (a.key>p->data.key) p=p->rightnode; } //找到的位置就是q p=new BSTnode<T>; p->rightnode=p->leftnode=0; p->data=a; //让该位置q节点的父节点链接它 if (!root) root=p; else if (a.key<q->data.key) q->leftnode=p; else q->rightnode=p; } #endif //BINARYSERCHTREE_BST_H
*************************************.cpp实现*****************************
#include <iostream> using namespace std; #include "bst.h" //BTS:binary search tree 二叉查找树的缺点,永远把第一个节点作为根节点,当插入的数据都比根节点大或者小的时候变为了链表 //二叉查找树是不平衡的树 //红黑树是平衡的,可以自动平衡 //二叉树性质: //1.每一个元素有一个键值 //2.左子树的键值都小于根节点的键值 //3.右子树的键值都大于根节点的键值 //4.左右子树都是二叉查找树 int main() { std::cout << "测试自己定义的搜索二叉树" << std::endl; BST<int > mybst; element<int> a,b,c,d,e,f,g,h; a.key=5; b.key=3; c.key=2; d.key=11; e.key=15; f.key=45; g.key=33; h.key=61; mybst.insert(a); mybst.insert(b); mybst.insert(c); mybst.insert(d); mybst.insert(e); // mybst.insert(h); // mybst.insert(f); // mybst.insert(g); mybst.display(); return 0; }
内容总结
以上是互联网集市为您收集整理的c++ 实现二叉搜索树全部内容,希望文章能够帮你解决c++ 实现二叉搜索树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。