- 浏览: 45396 次
- 性别:
- 来自: 广州
最新评论
-
raojl:
用google prototype!
C++ 消息序列化与反序列化 -
candle_huihui:
表示遇到过相同及更痛苦的情况过,曾被grub弄得很惨, ...
安装双系统引发的问题 -
moxiaomomo:
基德KID.1412 写道查找字符串中的子串,子串可以不连续对 ...
懂得实现字符串的操作(strcpy函数等)(一) -
基德KID.1412:
查找字符串中的子串,子串可以不连续对吧?
懂得实现字符串的操作(strcpy函数等)(一) -
moxiaomomo:
用hash表找吧,把第一个活动的会员用QQ号生成hashcod ...
如何快速找出两个队列中相同的元素,假设队列的长度非常大
因为是第一次写T树,网上的参考源码稀缺,所以程序中不免有bug,正在修正中。
我的同步博客:http://blog.csdn.net/moxiaomomo/archive/2011/06/09/6535008.aspx
主要参考资料来源于csdn博客:
http://blog.csdn.net/liuxuezong/archive/2010/12/03/6052686.aspx
http://blog.csdn.net/liuxuezong/archive/2010/12/06/6058373.aspx
我的同步博客:http://blog.csdn.net/moxiaomomo/archive/2011/06/09/6535008.aspx
view plaincopy to clipboardprint? #pragma once // // by xiaomo // 2011.06 // Ttree.h #include<iostream> using namespace std; enum ENUM { MaxSize=64, MinSize=MaxSize-2 }; template<typename T> struct TtreeNode { int balance; //平衡因子 TtreeNode<T>* left; //左子树指针 TtreeNode<T>* right; //右子树指针 unsigned short int nItems; //当前实际元素数目 T item[MaxSize]; //节点键值数组 T data[MaxSize]; //数据数组 }; template<typename T> class Ttree { public: Ttree(void); virtual ~Ttree(void); void clear(); //清空树 void _erase(TtreeNode<T>* pNode); //删除pNode以及其子节点 void freeNode(TtreeNode<T>* pNode); //删除当前节点 bool isEmpty(); //判断树是否为空 void insert(const T key,const T data); //插入操作 void remove(T key); T find(T key); //查找 virtual int keycompare(T key1,T key2); //键值的比较 void traverseTree(int order); protected: void preOrderTraverse(TtreeNode<T>* pNode)const; //遍历,const说明该函数不能修改类中任何非const函数 void inOrderTraverse(TtreeNode<T>* pNode)const; void postOrderTraverse(TtreeNode<T>* pNode)const; TtreeNode<T>* root; //当前root指针 int m_nSize; //当前已分配的节点数目 private: TtreeNode<T>* mallocNode(); int balanceFactor(TtreeNode<T>* pNode)const; int Depth(TtreeNode<T>* pNode)const; bool _insert(TtreeNode<T>* &pNode,const T key,const T data); //插入操作 int _remove(TtreeNode<T>* &pNode,T key); //删除操作 //树的四种旋转情况,调整树以适应平衡环境 TtreeNode<T>* SingleRotateLeft(TtreeNode<T>* pNode); //左左 TtreeNode<T>* SingleRotateRight(TtreeNode<T>* pNode); //右右 TtreeNode<T>* DoubleRotateLeft(TtreeNode<T>* pNode); //左右 TtreeNode<T>* DoubleRotateRight(TtreeNode<T>* pNode); //右左 int balanceLeftBranch(TtreeNode<T>* &pNode); //调整左子树 int balanceRightBranch(TtreeNode<T>* &pNode); //调整右子树 }; template<typename T> Ttree<T>::Ttree(void) //构造函数 { root=NULL; m_nSize=0; } template<typename T> //释构函数 Ttree<T>::~Ttree(void) { clear(); root=NULL; m_nSize=0; } template<typename T> void Ttree<T>::clear() //清空树 { _erase(root); } template<typename T> void Ttree<T>::_erase(TtreeNode<T>* pNode) //删除pnode节点及其子节点 { if(pNode==NULL) { return; } _erase(pNode->left); _erase(pNode->right); freeNode(pNode); } template<typename T> void Ttree<T>::freeNode(TtreeNode<T>* pNode) //删除当前节点 { if(pNode) { delete pNode; pNode=NULL; } } template<typename T> bool Ttree<T>::isEmpty() //判断是否为空 { if(root==NULL)return true; else return false; } template<typename T> TtreeNode<T>* Ttree<T>::mallocNode() //分配空间 { TtreeNode<T>* pNode=new TtreeNode<T>; memset(pNode, 0, sizeof(TtreeNode<T>)); pNode->balance=0; pNode->left=NULL; pNode->right=NULL; pNode->nItems=0; m_nSize+=1; return pNode; } template<typename T> int Ttree<T>::keycompare(T key1, T key2) { int p=key1; int q=key2; return p<q?-1:(p==q?0:1); } template<typename T> void Ttree<T>::traverseTree(int order) { switch(order) { case 1: preOrderTraverse(root); break; case 2: inOrderTraverse(root); break; case 3: postOrderTraverse(root); break; } } template<typename T> void Ttree<T>::preOrderTraverse(TtreeNode<T> *pNode) const //先序遍历 { if(pNode) { for(int i=0;i<pNode->nItems;++i) { cout<<pNode->item[i]<<" "; //cout<<pNode->data[i]<<" "; } cout<<endl; preOrderTraverse(pNode->left); preOrderTraverse(pNode->right); } } template<typename T> void Ttree<T>::inOrderTraverse(TtreeNode<T> *pNode) const //中序遍历 { if(pNode) { inOrderTraverse(pNode->left); for(int i=0;i<pNode->nItems;++i) { cout<<pNode->item[i]<<" ";// cout<<pNode->data[i]<<" "; } cout<<endl; inOrderTraverse(pNode->right); } } template<typename T> void Ttree<T>::postOrderTraverse(TtreeNode<T> *pNode) const //后序遍历 { if(pNode) { postOrderTraverse(pNode->left); postOrderTraverse(pNode->right); for(int i=0;i<pNode->nItems;++i) { cout<<pNode->item[i]<<" ";//cout<<pNode->data[i]<<" "; }cout<<endl; } } template<typename T> //平衡因子 int Ttree<T>::balanceFactor(TtreeNode<T> *pNode) const { return Depth(pNode->right)-Depth(pNode->left); } template<typename T> //求树的深度 int Ttree<T>::Depth(TtreeNode<T> *pNode) const { if(pNode==NULL)return 0; int l=Depth(pNode->left); int r=Depth(pNode->right); return 1+(l>r?l:r); } template<typename T> TtreeNode<T>* Ttree<T>::SingleRotateLeft(TtreeNode<T> *pNode) //左左情况(右旋) { TtreeNode<T>* pl=pNode->left; pNode->left=pl->right; pl->right=pNode; //调整平衡因子 pNode->balance=balanceFactor(pNode); pl->balance=balanceFactor(pl); return pl; } template<typename T> TtreeNode<T>* Ttree<T>::SingleRotateRight(TtreeNode<T> *pNode) //右右情况(左旋) { TtreeNode<T>* pr=pNode->right; pNode->right=pr->left; pr->left=pNode; //调整平衡因子 pNode->balance=balanceFactor(pNode); pr->balance=balanceFactor(pr); return pr; } template<typename T> TtreeNode<T>* Ttree<T>::DoubleRotateLeft(TtreeNode<T> *pNode) //左右情况(先左旋后右旋) { pNode->left=SingleRotateRight(pNode->left); //left rotation pNode->balance=balanceFactor(pNode); //Adjust the balance factor return SingleRotateLeft(pNode); //right rotation } template<typename T> TtreeNode<T>* Ttree<T>::DoubleRotateRight(TtreeNode<T> *pNode) //右左情况(先右旋后左旋) { pNode->right=SingleRotateLeft(pNode->right); //right rotation pNode->balance=balanceFactor(pNode); //Adjust the balance factor return SingleRotateRight(pNode); //left rotation } template<typename T> T Ttree<T>::find(T key) //查找节点 { TtreeNode<T>* pNode=root; while(pNode) { int n=pNode->nItems; T keymin=pNode->item[0]; T keymax=pNode->item[n>0?n-1:0]; int ncmp1=keycompare(key,keymin); int ncmp2=keycompare(key,keymax); if(ncmp1>=0&&ncmp2<=0) //二分查找 { int l=0,r=n-1; while(l<=r) { int i=(l+r)>>1; T itemkey=pNode->item[i]; int ncmp=keycompare(key,itemkey); if(ncmp==0) { return pNode->data[i]; } else if(ncmp>0) {l=i+1;} else {r=i-1;} } break; } else if(ncmp1<0) { pNode=pNode->left; } else if(ncmp2>0) { pNode=pNode->right; } } return -1; } template<typename T> void Ttree<T>::insert(const T key,const T data) //插入节点 { if(root==NULL) { root=mallocNode(); root->item[0]=key; root->data[0]=data; root->nItems=1; root->left=NULL; root->right=NULL; } else { TtreeNode<T>* pNode=root; //根据具体情况插入节点 _insert(pNode,key,data); if(pNode!=root) { root=pNode; } } } template<typename T> bool Ttree<T>::_insert(TtreeNode<T> * &pNode,const T key,const T data) { int n=pNode->nItems; T keymin=pNode->item[0]; T keymax=pNode->item[n>0?n-1:0]; //////////////////////////////////////////// //compare to the minnimum key int nDifMin=keycompare(key,keymin); if(nDifMin<=0) //如果key小于等于keymin { TtreeNode<T>* pl=pNode->left; if((nDifMin==0||pl==NULL)&&pNode->nItems<MaxSize) //在当前节点插入新数据 { for(int i=n;i>0;--i) { pNode->item[i]=pNode->item[i-1]; pNode->data[i]=pNode->data[i-1]; } pNode->item[0]=key; pNode->data[0]=data; pNode->nItems+=1; return false; } if(pl==NULL) //当前键值数目已经达到最大值,而且左子树为空的情况下,新建左子树并插入数据 { pl=mallocNode(); pl->item[0]=key; pl->data[0]=data; pl->nItems+=1; pNode->left=pl; } else //其他情况下,继续递归 { TtreeNode<T>* plchild=pl; bool isbfGrow=_insert(plchild,key,data); if(plchild!=pl) { pNode->left=pl=plchild; //relocation } if(!isbfGrow) //如果左子树深度不增加,则返回false { return false; } } //在左子树深度加1的情况下,程序才运行到此处,则需要更新balance factor if(pNode->balance>0) { pNode->balance=0; return false; } if(pNode->balance==0) { pNode->balance=-1; return true; } else { if(pl->balance<0) //遇到左左情况,执行右旋 { pNode=SingleRotateLeft(pNode); } else { pNode=DoubleRotateLeft(pNode); //遇到左右情况,先左旋再右旋 } return false; } } //////////////////////////////////////////// //compare to the maxmum key value int nDifMax=keycompare(key,keymax); if(nDifMax>=0) //如果key大于等于keymax { TtreeNode<T>* pr=pNode->right; if((pr==NULL||nDifMax)&&pNode->nItems<MaxSize) //在当前节点插入数据 { pNode->item[n]=key; pNode->data[n]=data; pNode->nItems+=1; return false; } else if(pr==NULL) //创建新的右子树 { pr=mallocNode(); pr->item[0]=key; pr->data[0]=data; pr->nItems+=1; pNode->right=pr; } else { //继续递归查找并插入 TtreeNode<T>* prchild=pr; bool isbfGrow=_insert(prchild,key,data); if(prchild!=pr) { pNode->right=pr=prchild; } if(!isbfGrow) { return false; } } //在右子树深度加1的情况下,程序才运行到此处,则需要更新balance factor if(pNode->balance<0) { pNode->balance=0; return false; } else if(pNode->balance==0) { pNode->balance=1; return true; } else { if(pr->balance>0) { pNode=SingleRotateRight(pNode); } else { pNode=DoubleRotateRight(pNode); } return false; } } //////////////////////////////////////////// //新的键值在数组的中间,用二分法查找 int l=0,r=n-1; while(l<r) { int mid=(l+r)>>1; T cur_key=pNode->item[mid]; int cmp=keycompare(key,cur_key); if(cmp>0) { l=mid+1; } else if(cmp>0) { r=mid; } else{break;} } if(pNode->nItems<MaxSize) //数组长度没达到最大值 { for(int i=n;i>r;--i) { pNode->item[i]=pNode->item[i-1]; pNode->data[i]=pNode->data[i-1]; } pNode->item[r]=key; pNode->data[r]=data; pNode->nItems+=1; return false; } else { T keyID,dataID; //考虑平平衡因子的大小做出不同的选择 if(pNode->balance>=0) { //由于数组长度达到最大,在当前节点中插入新数据,并将数组原第一个元素插入到左子树中 keyID=pNode->item[0]; dataID=pNode->data[0]; for(int i=1;i<r;++i) { pNode->item[i-1]=pNode->item[i]; pNode->data[i-1]=pNode->data[i]; } pNode->item[r-1]=key; pNode->data[r-1]=data; return _insert(pNode,keyID,dataID); } else{ //在当前节点中插入新数据,并将数组原第一个元素插入到有子树中。当前是左子树深度较大,因此往右子树添加元素 keyID=pNode->item[n-1]; dataID=pNode->data[n-1]; for(int i=n-1;i>r;--i) { pNode->item[i]=pNode->item[i-1]; pNode->data[i]=pNode->data[i-1]; } pNode->item[r]=key; pNode->data[r]=data; return _insert(pNode,keyID,dataID); } } return 0; } template<typename T> int Ttree<T>::balanceLeftBranch(TtreeNode<T>* &pNode)//平衡左子树,更新节点信息 { if(pNode->balance<0){pNode->balance=0;return 1;} //返回1表示当前调整的情况对当前节点的父节点以及祖先节点的平衡因子产生影响 else if(pNode->balance==0){pNode->balance=1;return 0;} //返回0则对父节点及祖先节点无影响 else { TtreeNode<T>* pr=pNode->right; if(pr->balance>=0) { pNode=SingleRotateRight(pNode); //右旋 //return 0; } else { pNode=DoubleRotateRight(pNode); //先右旋后左旋 //return 1; } return 1; } return 0; } template<typename T> int Ttree<T>::balanceRightBranch(TtreeNode<T>* &pNode)//平衡右子树,更新节点信息 { if(pNode->balance>0){pNode->balance=0;return 1;} else if(pNode->balance==0){pNode->balance=-1;return 0;} else { TtreeNode<T>* pl=pNode->left; if(pl->balance<=0) { pNode=SingleRotateLeft(pNode); //左旋 } else { pNode=DoubleRotateLeft(pNode); //先左旋后右旋 } return 1; } } template<typename T> void Ttree<T>::remove(T key) { int isOK=_remove(root,key); if(isOK==-1){cout<<"fail to remove such data"<<endl;} } template<typename T> int Ttree<T>::_remove(TtreeNode<T>* &pNode,T key) //删除操作 { if(pNode==NULL)return -1; int n=pNode->nItems; T keymin=pNode->item[0]; T keymax=pNode->item[n>0?n-1:0]; int nDifMin=keycompare(key,keymin); if(nDifMin<0) //继续搜索左子树 { TtreeNode<T>* pl=pNode->left; if(pl!=NULL) { TtreeNode<T>* plchild=pl; int flag=_remove(plchild,key); if(pl!=plchild) { pNode->left=plchild; } if(flag>0) //flag>0表明树的层次由于remove操作而改变,则重新调整 { return balanceLeftBranch(pNode); } else return flag; } else return -1; //表示没有找到要删除的key } int nDifMax=keycompare(key,keymax); if(nDifMax<=0) //在当前节点删除数据 { int i=0; for(i=0;i<n;++i) { if(key==pNode->item[i])break; } if(pNode->item[i]!=key)return -1; //表示没有找到要删除的key if(n<=1) { if(pNode->left==NULL) //如果左子树为空,此种情况对于左右子树皆为空也适用 { TtreeNode<T>* pNewNode=pNode->right; freeNode(pNode); pNode=pNewNode; } else if(pNode->right==NULL)//如果右子树为空 { TtreeNode<T>* pNewNode=pNode->left; freeNode(pNode); pNode=pNewNode; } return 1; //树层次改变,返回1 } else { //在当前节点内删除 if(pNode->nItems<=MinSize) //当前节点键值数目小于或等于最低限制值 { TtreeNode<T>* plchild=pNode->left,*prchild=pNode->right; //如果结点N中的键值数量少于最小值,则根据N的平衡因子决定从结点N的左子树中移出最大的键值或者右子树中移出最小值来填充。 if(plchild!=NULL&&pNode->balance<=0) { while(plchild->right!=NULL) { plchild=plchild->right; } while(i>0) { pNode->item[i]=pNode->item[i-1]; pNode->data[i]=pNode->data[i-1]; --i; } pNode->item[0]=plchild->item[plchild->nItems-1]; pNode->data[0]=plchild->data[plchild->nItems-1]; key=pNode->item[0]; TtreeNode<T>* plTmp=plchild; int flag=_remove(plTmp,key); if(plTmp!=plchild) {pNode->left=plTmp;} if(flag>0){flag=balanceLeftBranch(pNode);} return flag; } else if(prchild!=NULL) { while(prchild->left!=NULL) { prchild=prchild->left; } while(i<n-1) { pNode->item[i]=pNode->item[i+1]; pNode->data[i]=pNode->data[i+1]; ++i; } pNode->item[n-1]=plchild->item[0]; pNode->data[n-1]=plchild->data[0]; key=pNode->item[n-1]; TtreeNode<T>* prTmp=prchild; int flag=_remove(prTmp,key); if(prTmp!=prchild) {pNode->right=prTmp;} if(flag>0){flag=balanceRightBranch(pNode);} return flag; } } //当前节点键值数目大于最小限制值 int k=i; while(k<n-1) { pNode->item[k]=pNode->item[k+1]; pNode->data[k]=pNode->data[k+1]; k++; } pNode->nItems-=1; return 0; //树的层次不变,返回0 } } else{ //搜索右子树 TtreeNode<T>* pr=pNode->right; if(pr!=NULL) { TtreeNode<T>* prchild=pr; int flag=_remove(prchild,key); if(pr!=prchild) {pNode->right=prchild;} if(flag>0) //树层次改变 { return balanceRightBranch(pNode); } else return flag; //树层次不变 } } return -1; }
主要参考资料来源于csdn博客:
http://blog.csdn.net/liuxuezong/archive/2010/12/03/6052686.aspx
http://blog.csdn.net/liuxuezong/archive/2010/12/06/6058373.aspx
发表评论
-
C++ 消息序列化与反序列化
2011-07-31 11:09 23431. 消息序列化 将具有一定结构的数据转换成可以存取或 ... -
const的几个用法
2011-06-10 22:33 999(1)const定义常量: const dat ... -
懂得实现字符串的操作(strcpy函数等)(一)
2011-05-21 11:33 3228一般面试的时候,如果要考查你的C++基本功,关于字符串的实现的 ... -
C++ String类会用,也要会实现
2011-05-11 11:19 2136面试的时候被问及了String类的实现,结果没写好... 就当 ... -
C++ String类会使用,也要会实现
2011-05-11 11:01 2面试的时候被问及了String类的实现,结果没写好... 就当 ... -
C++中指针和引用的区别
2011-04-19 19:28 739C++中参数传递的方式有 ... -
Qt crearor中添加背景图片的问题
2011-04-11 19:18 3754在对话框中添加背景图片的一种方法: 右键点击窗体区域--> ... -
C++ STL遍历二维数组的问题
2011-03-19 00:08 4042今天在书上学会了用vector创建和输出二维数组的另一种好方法 ...
相关推荐
描述: 实现红黑树、二叉搜索树相关算法:插入(红黑树涉及树的调整:左旋右旋等),删除,搜索(指定Key值节点)。 另外,红黑树实现计算树黑高的算法。 1).插入测试,输入 8,11,17,15,6,1,22,25,27,...
### C++实现二叉树类知识点详解 #### 一、二叉树简介 二叉树是一种树形数据结构,其中每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树在计算机科学中有着广泛的应用,如文件系统、编译器设计、快速...
在C++源码中,你可能会看到以下模块: - 数据加载模块:读取数据集,将数据转换为程序可处理的格式。 - 样本和特征结构体:定义数据结构,存储样本的特征值和权重。 - 弱学习器类:包含训练和预测的方法,可能包括...
本文详细介绍了如何使用C++实现Trie树,并重点分析了插入、删除和查找操作的具体实现过程。Trie树是一种非常有用的数据结构,尤其适合于处理大量的字符串数据。通过合理的设计和实现,Trie树可以大大提高字符串搜索...
### 实现Trie树的C/C++模板 在计算机科学领域,Trie树(又称前缀树或字典树)是一种用于存储具有共同前缀的字符串的高效数据结构。它广泛应用于各种场景,如自动补全、拼写检查以及IP路由表等。本文将详细介绍如何...
在C++中实现B树涉及许多关键概念和技术,下面我们将详细讨论这些知识点。 首先,B树的特性: 1. 分支因子:B树中的每个节点可以有多个子节点,这个数量通常被称为分支因子或度数。每个节点最多包含`2 * t - 1`个...
广义表是一种非常重要的数据结构,它是一种可以包含其他数据结构(如列表、元组等)的数据结构。在计算机科学中,广义表通常用于表示递归...同时,这些源码也是学习和练习C++面向对象编程以及C语言指针操作的好素材。
在C++中实现RTree,可以利用模板类(Template)来创建一个通用且可扩展的数据结构。下面将详细讨论RTree的基本原理以及C++实现的关键点。 1. RTree基本原理: RTree是一种动态的、自平衡的树状数据结构,用于管理...
key_t key; rb_node_t *root=NULL,*node=NULL; srand(time(NULL)); for(i=1;i;++i){ key=rand()%count; if((root=rb_insert(key,i,root))){ printf("[i=%d] insert key %d success!\n",i,key); } else...
标题中提到的“国外一个很好的C++ tree库”可能指的是STL中的`std::set`或`std::map`,它们在内部实现为红黑树,或者是其他第三方库,如` Boost.Graph`库中的树结构。不过,由于具体库名未给出,我们将以一般性的...
标题中的“MS41929_demo程序,ms932,C,C++源码”表明这是一个与编程相关的项目,特别是涉及到C和C++语言的源代码。MS41929可能是一个特定的项目编号或者模块标识,"demo程序"意味着这是一份演示或示例代码,用于展示...
本压缩包“基于C++模板实现的数据结构代码.zip”包含了一组用C++模板实现的数据结构源码,这对于学习C++高级特性,特别是对于进行毕业设计或课程设计的程序员来说,是非常有价值的资源。 1. **模板基础**: - **...
二叉搜索树(Binary Search Tree,BST)是一种特殊的二叉树数据结构,其每个节点的值都大于其左子树中所有节点的值,并小于其右...这个实现充分展示了二叉搜索树的基本特性和操作,并利用了C++的模板机制实现泛型编程。
通过以上步骤,你可以在Visual C++ 6.0环境下实现一个基本的树形视图控件。实际开发中,还可以根据需求进行更深入的定制,如添加右键菜单、编辑节点文本、保存和恢复状态等。请参考提供的源码文件(source)以获取...
通过深入理解这些源码,开发者不仅可以学习心电信号处理的基本方法,还可以掌握如何在实际应用中运用C和C++实现高性能计算。这个资料包对于生物医学工程、信号处理以及机器学习领域的学习者具有很高的参考价值。
在实验中,通过使用802.3ad(链路聚合控制协议)来实现多条链路之间的冗余备份。 #### 实验配置 1. **在交换机A上配置聚合端口**: - 进入全局配置模式:`Switch#config t` - 创建聚合端口1:`Switch(config)#...
最后,压缩包中的“knearest”可能是源码文件夹名,包含了实现k-NN算法的C++源文件。这些文件可能包括了上述的数据结构、距离计算函数和分类器实现,以及其他辅助功能,如数据读取、结果输出等。
《Data Structures and Algorithms in C++, 4th edition》是由Michael T. Goodrich、Roberto Tamassia和Michael H. Goldwasser合著的一本经典教材,专注于C++编程语言中的数据结构与算法。这本书的第四版提供了全面...
超级下载 不过不是c++源码 1:综合FTP下载和HTTP(网络蚂蚁)(多线程). 2:FTP下载支持多个站点同时下载一个文件(同时支持断点续传). 3:可以在不下载ZIP.RAR.ISO文件的情况下查看文件里面的目录文件. 4:支持多语言. 5:...
在"htmlread"这个文件名中,我们可以假设这是实现上述功能的一个源码文件。这个文件可能包含了对libcurl或类似库的封装,用于发起HTTP/HTTPS请求,以及可能的HTML解析逻辑。具体实现会根据实际需求,如是否处理异步...