- 浏览: 44202 次
- 性别:
- 来自: 广州
最新评论
-
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 22921. 消息序列化 将具有一定结构的数据转换成可以存取或 ... -
const的几个用法
2011-06-10 22:33 959(1)const定义常量: const dat ... -
懂得实现字符串的操作(strcpy函数等)(一)
2011-05-21 11:33 3188一般面试的时候,如果要考查你的C++基本功,关于字符串的实现的 ... -
C++ String类会用,也要会实现
2011-05-11 11:19 2086面试的时候被问及了String类的实现,结果没写好... 就当 ... -
C++ String类会使用,也要会实现
2011-05-11 11:01 2面试的时候被问及了String类的实现,结果没写好... 就当 ... -
C++中指针和引用的区别
2011-04-19 19:28 702C++中参数传递的方式有 ... -
Qt crearor中添加背景图片的问题
2011-04-11 19:18 3678在对话框中添加背景图片的一种方法: 右键点击窗体区域--> ... -
C++ STL遍历二维数组的问题
2011-03-19 00:08 4012今天在书上学会了用vector创建和输出二维数组的另一种好方法 ...
相关推荐
描述: 实现红黑树、二叉搜索树相关算法:插入(红黑树涉及树的调整:左旋右旋等),删除,搜索(指定Key值节点)。 另外,红黑树实现计算树黑高的算法。 1).插入测试,输入 8,11,17,15,6,1,22,25,27,...
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++源码 1:综合FTP下载和HTTP(网络蚂蚁)(多线程). 2:FTP下载支持多个站点同时下载一个文件(同时支持断点续传). 3:可以在不下载ZIP.RAR.ISO文件的情况下查看文件里面的目录文件. 4:支持多语言. 5:...
基于C++实现的单目多视图立体重建系统源码+项目说明.zip 1、该资源内项目代码都是经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、...
基于C和C++实现的单目多视图立体重建系统源码+项目说明.zip * 数据读取 * 特征点提取和匹配 * 稀疏重建,生成稀疏点云以及估计视图位姿 * 稠密重建,生成每张视图对应的深度图(这里可以进一步生成稠密点云,通过...
'soapcpp2’存根及架构编译器是可以生成构建C++ SOAP客户端所需的C++源码的预编译器。该预编译器的输入参数是一个标准的C/C++头文件 。这个头文件可以由WSDL解析器根据相关的WSDL文档自动生成。 参见下面的...
在1)-4)的红黑树算法基础上修改完成P307 14.1-4算法 OS_Key_Rank(T,k). 输入 1,2,3,4,5,6,7,8 建树, k=6, 输出OS_Key_Rank的返回值。 文档要点:总结红黑树和二叉搜索树在查找上的性能分析,描述此类算法的应用。...
库要不就添加其所有源码到你的工程里面.你必须确保LuaBind目录在你的编译器包含目录中. LuaBind需要Boost 1.32.0 或者 1.33.0 (只需要头文件即可). LuaBind还需要Lua. 官方的构建LuaBind的方式是通过 Boost.Build ...
1.2.1 Visual Studio 2005的Visual C++——Windows CE开发环境概述 1.2.2 示例程序HelloWorld 1.3 Windows CE附带远程工具概述 第2章 图形编程 2.1 设备环境类 2.2 图形对象类(GDI) 2.3 绘制各种图形 2.4...
2012-06-12 12:49 8,323,796 Visual C++实现图像获取、处理与分析.rar 2012-06-12 12:49 6,275,839 Visual C++实现数字图像处理源代码.rar 2012-06-12 11:57 182 Visual C++技术内幕摘要笔记.rar 2012-06-12 11:50 3...
此目录里包括了一书中所有23种设计模式的实现(Java 版)源码 关于代码的几点说明: 1. 代码为根据个人对Design Pattern的学习理解写出(>90%原创), 难免有错误的地方,希望大家指出。 2. 每个Pattern均是一个...
HashMap是Hashtable的轻量级实现(非线程安全的实现),他们都完成了Map接口,主要区别在于HashMap允许空(null)键值(key),由于非线程安全,效率上可能高于Hashtable。 HashMap允许将null作为一个entry的key或者...
HashMap是Hashtable的轻量级实现(非线程安全的实现),他们都完成了Map接口,主要区别在于HashMap允许空(null)键值(key),由于非线程安全,效率上可能高于Hashtable。 HashMap允许将null作为一个entry的key或者...
GoF 的《设计模式》是所有面向对象语言(C++ Java C#)的基础,只不过不同的语言将之实现得更方便地使用。 GOF 的设计模式是一座"桥" 就 Java 语言体系来说,GOF 的设计模式是 Java 基础知识和 J2EE 框架知识之间一...
2.18.6 TObject:所有对象的祖先 63 2.18.7 接口 63 2.19 结构化异常处理 66 2.19.1 异常类 68 2.19.2 执行的流程 70 2.19.3 重新触发异常 71 2.20 运行期类型信息 72 2.21 总结 72 第3章 Win32 API 73 3.1 对象:...
第一篇 面试题 ................................1.6.6. 用 C++设计一个不能被继承的类 .......................................................136 1.6.7. 给定链表的头指针和一个结点指针,在 O(1)时间删除该结点 ....