登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Gamebaby Rock Sun的博客

我只知道一件事情,就是我一无所知。

 
 
 

日志

 
 
关于我

曾经拥有的,不要忘记, 已经得到的,更要珍惜, 属于自己的,不要放弃, 已经失去的,留着回忆, 想要得到的,必须努力, 但最重要的,是好好爱惜自己!

我实现的AVL树模版类  

2008-04-06 21:50:11|  分类: VC/VC++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

下面是我实现的AVL树C++模版类,充分利用了windows中的一些特性,关于AVL树的算法我不在赘述,大家自己搜索一下,满网络都是,此处的实现是一个非常好用的模版版本。可以免费用于任何用途,在版本升级或发生变动后,本人将不通知任何使用者,但是如果需要技术支持、升级服务和培训服务的可以与本人联系,QQ 41750362。

#include "GRSPublicDef.h"
#include "GRSNew.h"
#include "GRSList.h"
#pragma once

#pragma check_stack(off)
#ifdef GRS_USE_NS
namespace ns_mj
{
 namespace adt
 {
#endif
  template <class TKey,class TData>
  class CGRSAVLTreeNode
  {
  public:
   TKey m_Key;    //键值
   TData m_Data;   //数据
  
   INT m_iHeight;
   CGRSAVLTreeNode<TKey,TData>*m_pLeft;
   CGRSAVLTreeNode<TKey,TData>*m_pRight;
  public:
   CGRSAVLTreeNode(const TKey& Key,
    const TData& Data,
    CGRSAVLTreeNode<TKey,TData>*pLeft = NULL,
    CGRSAVLTreeNode<TKey,TData>*pRight = NULL)
    :m_iHeight(1),
    m_pLeft(pLeft),
    m_pRight(pRight)
   {
    m_Key = Key;
    m_Data = Data;
   }

   virtual ~CGRSAVLTreeNode()
   {
   }

  public:
   GRS_INLINE INT ReClacHeight()
   {
    int ihLeft = (NULL != m_pLeft)?m_pLeft->m_iHeight:0;
    int ihRight = (NULL != m_pRight)?m_pRight->m_iHeight:0;
    m_iHeight = (ihLeft > ihRight)?(ihLeft + 1):(ihRight + 1);
    return m_iHeight;
   }

   void PreOrder(void (*VisitNode)( CGRSAVLTreeNode<TKey,TData>* pNode,void* pData),void*pData)
   {// 对this进行前序遍历
    VisitNode(this,pData) ;      // 访问根节点
    if(NULL != m_pLeft)
    {
     m_pLeft->PreOrder(VisitNode,pData) ;  // 前序遍历左子树
    }
    if(NULL != m_pRight)
    {
     m_pRight->PreOrder(VisitNode,pData) ; // 前序遍历右子树
    }
    
   }

   void InOrder(void (*VisitNode)( CGRSAVLTreeNode<TKey,TData>* pNode,void* pData),void*pData)
   {// 对this进行中序遍历
    if(NULL != m_pLeft)
    {
     m_pLeft->InOrder(VisitNode,pData) ;  // 中序遍历左子树
    }

    VisitNode(this,pData ) ;    // 访问根节点

    if(NULL != m_pRight)
    {
     m_pRight->InOrder(VisitNode,pData) ; // 中序遍历右子树
    }
    
   }

   void PostOrder(void (*VisitNode)( CGRSAVLTreeNode<TKey,TData>* pNode,void* pData),void*pData)
   {// 对this进行后序遍历
    if(NULL != m_pLeft)
    {
     m_pLeft->PostOrder(VisitNode,pData) ; // 后序遍历左子树
    }
    if(NULL != m_pRight)
    {
     m_pRight->PostOrder(VisitNode,pData) ; // 后序遍历右子树
    }

    VisitNode( this,pData ) ;    // 访问根节点
   }

   
  public:
   GRS_HEAP_DEF();
  };

  template <class TKey,class TData>
  class CGRSAVLTree
  {
  protected:
   //AVL树的树根
   CGRSAVLTreeNode<TKey,TData>* m_pRoot;
   //树种节点的总数
   INT m_iCount;

#ifdef GRS_MT
   mutable CRITICAL_SECTION m_cs;
#endif

  public:
   CGRSAVLTree()
    :m_pRoot(NULL),
    m_iCount(0)
   {
#ifdef GRS_MT
    ::ZeroMemory(&m_cs,sizeof(m_cs));
    //初始化关键代码段结构对象,用于多线程的并发控制
    ::InitializeCriticalSection(&m_cs); 
#endif
   };
   ~CGRSAVLTree()
   {
#ifdef GRS_MT
    //释放关键代码段结构对象
    ::DeleteCriticalSection(&m_cs); 
#endif
   }
  protected:
   void Core_Insert(const TKey& Key,const TData& Data, CGRSAVLTreeNode<TKey,TData>*& pNode)
   {//内核插入函数
    if(NULL == pNode)
    {//插入的节点为空,就让此节点生成
     pNode = new CGRSAVLTreeNode<TKey,TData>(Key,Data);
     return;
    }

    if( Key < pNode->m_Key )
    {//待插入的值小于当前值,就插到左子树
     Core_Insert( Key, Data, pNode->m_pLeft);
     Code_Balance( pNode);//使树恢复平衡
    }   

    if( Key > pNode->m_Key)
    {//待插入值大于当前值,插入到右子树
     Core_Insert( Key, Data, pNode->m_pRight);
     Code_Balance( pNode );//使树恢复平衡
    }

   }

   GRS_INLINE void Code_Balance( CGRSAVLTreeNode<TKey,TData>*& pNode )
   {
    GRS_ASSERT(NULL != pNode);

    INT ihLeft = Core_Height(pNode->m_pLeft);
    INT ihRight = Core_Height(pNode->m_pRight);

    //检查子树是否是平衡的
    if((( ihLeft - ihRight) <= 1) && (( ihRight - ihLeft) <= 1))
    {//树是平衡的
     //    @
     //  /   \
     // @     @
     pNode->ReClacHeight();
     return;
    }
    else if(( ihLeft - ihRight) > 1)
    {//左子树比右子树高2
     if( Core_Height( pNode->m_pLeft->m_pLeft)
       >= Core_Height( pNode->m_pLeft->m_pRight))
     {
      //      @
      //    /   \
      //   @     @
      //  /
      //    @
      //   /
      //   @
      CGRSAVLTreeNode<TKey,TData>* pTmpLeft = pNode->m_pLeft;
      
      pNode->m_pLeft = pTmpLeft->m_pRight;
      pTmpLeft->m_pRight = pNode;  
      pNode = pTmpLeft;

      pNode->m_pRight->ReClacHeight();
      pNode->ReClacHeight();
     }
     else
     {
      //      @
      //    /   \
      //   @     @
      //    \
      //        @
      //         \
      //           @
      CGRSAVLTreeNode<TKey,TData>* pTmpLeft = pNode->m_pLeft;
      CGRSAVLTreeNode<TKey,TData>* pTmpRight = pTmpLeft->m_pRight;

      pNode->m_pLeft = pTmpRight->m_pRight;
      pTmpLeft->m_pRight = pTmpRight->m_pLeft; 
      pTmpRight->m_pLeft = pTmpLeft;   
      pTmpRight->m_pRight = pNode;  
      pNode = pTmpRight;

      pTmpLeft->ReClacHeight();
      pNode->m_pRight->ReClacHeight();
      pNode->ReClacHeight();
     }
    }
    else
    {//右子树高2
     if( Core_Height( pNode->m_pRight->m_pRight)
      >= Core_Height( pNode->m_pRight->m_pLeft))
     {
      CGRSAVLTreeNode<TKey,TData>* pTmpRight = pNode->m_pRight;
      pNode->m_pRight = pTmpRight->m_pLeft;
      pTmpRight->m_pLeft = pNode;
      pNode = pTmpRight;

      pNode->m_pLeft->ReClacHeight();
      pNode->ReClacHeight();
     }
     else
     {
      CGRSAVLTreeNode<TKey,TData>* pTmpRight = pNode->m_pRight;
      CGRSAVLTreeNode<TKey,TData>* pTmpLeft = pTmpRight->m_pLeft;

      pNode->m_pRight = pTmpLeft->m_pLeft;
      pTmpRight->m_pLeft = pTmpLeft->m_pRight;
      pTmpLeft->m_pLeft = pNode;
      pTmpLeft->m_pRight = pTmpRight;
      pNode = pTmpLeft;

      pNode->m_pRight->ReClacHeight();
      pNode->m_pLeft->ReClacHeight();
      pNode->ReClacHeight();
     }
    }
   }

   void Core_Remove(const TKey& Key,TData& Data, CGRSAVLTreeNode<TKey,TData>*& pNode)
   {
    if( Key < pNode->m_Key)
    {//比节点值小,朝左子树搜索
     Core_Remove( Key,Data, pNode->m_pLeft);
     Code_Balance( pNode);
    }
    else if( Key > pNode->m_Key)
    {//比节点值大,朝右子树搜索
     Core_Remove(Key, Data, pNode->m_pRight);
     Code_Balance( pNode);
    }
    else
    {//待删除的就是当前节点
     CGRSAVLTreeNode<TKey,TData>* pTmpNode = NULL;

     if( !pNode->m_pLeft )
     {
      pTmpNode = pNode->m_pRight;
      Data = pNode->m_Data;

      delete pNode;
      pNode = pTmpNode;
      return;
     }

     if( !pNode->m_pRight )
     {
      pTmpNode = pNode->m_pLeft;
      Data = pNode->m_Data;
      delete pNode;
      pNode = pTmpNode;
      return;
     }
     else
     {
      pTmpNode = pNode->m_pLeft;
      while( pTmpNode->m_pRight )
      {
       pTmpNode = pTmpNode->m_pRight;
      }

      pNode->m_Key = pTmpNode->m_Key;
      pNode->m_Data = pTmpNode->m_Data;

      Core_Remove(pTmpNode->m_Key,Data, pNode->m_pLeft);
      Code_Balance( pNode );
     }
    }
   }

   GRS_INLINE INT Core_Height( CGRSAVLTreeNode<TKey,TData>* pNode)
   {
    return (NULL != pNode)?pNode->ReClacHeight():0;
   }

   void Core_DelTree( CGRSAVLTreeNode<TKey,TData>*& pNode)
   {
    if(NULL != pNode)
    {
     CGRSAVLTreeNode<TKey,TData>* pTmp = pNode->m_pRight;
     Core_DelTree( pNode->m_pLeft);
     delete pNode;
     pNode = NULL;
     Core_DelTree(pTmp);
    }
   }

   void Core_TreeHealth( CGRSAVLTreeNode<TKey,TData>* pNode)
   {
    if( NULL != pNode )
    {
     INT ihLeft= 0 ;
     INT ihRight = 0;

     Core_TreeHealth( pNode->m_pLeft );

     if( !pNode->m_pLeft )
     {
      ihLeft = 0;
     }
     else
     {
      ihLeft = pNode->m_pLeft->m_iHeight;
     }

     if( !pNode->m_pRight )
     {
      ihRight = 0;
     }
     else
     {
      ihRight = pNode->m_pRight->m_iHeight;
     }

     GRS_ASSERT( !( ihLeft - ihRight > 1));

     Core_TreeHealth( pNode->m_pRight );
    }
   }
  public:
   BOOL Add(const TKey& Key,const TData& Data )
   {
#ifdef GRS_MT
    //进入关键代码段
    ::EnterCriticalSection(&m_cs);
#endif
    if( IsHave( Key ) )
    {
     return FALSE;
    }
    else
    {
     m_iCount++;
     Core_Insert(Key, Data, m_pRoot );
     return TRUE;
    }
#ifdef GRS_MT
    //离开关键代码段
    ::LeaveCriticalSection(&m_cs);
#endif
   }

   BOOL Del(const TKey& Key,TData& Data )
   {
#ifdef GRS_MT
    //进入关键代码段
    ::EnterCriticalSection(&m_cs);
#endif
    if( IsHave( Key ) )
    {
     m_iCount--;
     Core_Remove(Key, Data, m_pRoot);
     return TRUE;
    }
    else
    {
     return FALSE;
    }
#ifdef GRS_MT
    //进入关键代码段
    ::LeaveCriticalSection(&m_cs);
#endif
   }

   BOOL IsHave( const TKey& Key ) const
   {
#ifdef GRS_MT
    //进入关键代码段
    ::EnterCriticalSection(&m_cs);
#endif
    BOOL bHave = FALSE;
    CGRSAVLTreeNode<TKey,TData>* pTmpNode = m_pRoot;

    while( pTmpNode && !bHave )
    {
     if( Key < pTmpNode->m_Key )
     {
      pTmpNode = pTmpNode->m_pLeft;
     }
     else if( Key > pTmpNode->m_Key )
     {
      pTmpNode = pTmpNode->m_pRight;
     }
     else
     {
      bHave = true;
     }
    }
#ifdef GRS_MT
    //进入关键代码段
    ::LeaveCriticalSection(&m_cs);
#endif
    return bHave;
   }
   
//   void UnionTree(const T& Data,CGRSAVLTree<T>& Left,CGRSAVLTree<T>& Right)
//   {//合并两棵树为一颗
//#ifdef GRS_MT
//    //进入关键代码段
//    ::EnterCriticalSection(&m_cs);
//#endif
//    Destroy();
//
//    GRS_ASSERT(NULL == m_pRoot && 0 == m_iCount);
//
//    m_pRoot = new CGRSAVLTreeNode<TKey,TData>(Data,Left.m_pRoot,Right.m_pRoot);
//    m_iCount = Left.m_iCount + Right.m_iCount;
//
//    Core_Balance(m_pRoot);
//
//#ifdef GRS_MT
//    //进入关键代码段
//    ::LeaveCriticalSection(&m_cs);
//#endif
//   }

   GRSPOSITION Search( const TKey&Key,TData& Data )
   {
#ifdef GRS_MT
    //进入关键代码段
    ::EnterCriticalSection(&m_cs);
#endif
    CGRSAVLTreeNode<TKey,TData>* pRet = NULL;
    CGRSAVLTreeNode<TKey,TData>* pTmpNode = m_pRoot;
    
    while( NULL != pTmpNode )
    {
     if( Key < pTmpNode->m_Key )
     {
      pTmpNode = pTmpNode->m_pLeft;
     }
     else if( Key > pTmpNode->m_Key )
     {
      pTmpNode = pTmpNode->m_pRight;
     }
     else
     {
      pRet = pTmpNode;
      Data = pRet->m_Data;
      break;
     }
    }
#ifdef GRS_MT
    //离开关键代码段
    ::LeaveCriticalSection(&m_cs);
#endif
    return (GRSPOSITION) pRet;
   }
   
   void Destroy()
   {
#ifdef GRS_MT
    //进入关键代码段
    ::EnterCriticalSection(&m_cs);
#endif
    if( m_pRoot )
    {
     Core_DelTree( m_pRoot );
     m_iCount = 0;
    }
#ifdef GRS_MT
    //离开关键代码段
    ::LeaveCriticalSection(&m_cs);
#endif
   }
  
   GRS_INLINE INT GetSize() const
   {
    return m_iCount;
   }

   GRS_INLINE INT GetHeight() const
   {
    return (NULL == m_pRoot)?0:m_pRoot->m_iHeight; 
   }

   BOOL IsEmpty() const
   {
    return (NULL == m_pRoot);
   }
   
   void Health() const
   {
#ifdef GRS_MT
    //进入关键代码段
    ::EnterCriticalSection(&m_cs);
#endif
    Core_TreeHealth( m_pRoot);
#ifdef GRS_MT
    //离开关键代码段
    ::LeaveCriticalSection(&m_cs);
#endif
   }

   void PreOrder(void (*VisitNode)( CGRSAVLTreeNode<TKey,TData>* pNode,void* pData),void* pData)
   {
#ifdef GRS_MT
    //进入关键代码段
    ::EnterCriticalSection(&m_cs);
#endif
    if(NULL != m_pRoot)
    {
     m_pRoot->PreOrder(VisitNode,pData) ;
    }
#ifdef GRS_MT
    //离开关键代码段
    ::LeaveCriticalSection(&m_cs);
#endif
   }
   
   void InOrder(void (*VisitNode)( CGRSAVLTreeNode<TKey,TData>* pNode,void* pData),void*pData)
   {
#ifdef GRS_MT
    //进入关键代码段
    ::EnterCriticalSection(&m_cs);
#endif
    if(NULL != m_pRoot)
    {
     m_pRoot->InOrder(VisitNode,pData);
    }
#ifdef GRS_MT
    //离开关键代码段
    ::LeaveCriticalSection(&m_cs);
#endif
   }

   void PostOrder(void (*VisitNode)(CGRSAVLTreeNode<TKey,TData>* pNode,void* pData),void*pData)
   {
#ifdef GRS_MT
    //进入关键代码段
    ::EnterCriticalSection(&m_cs);
#endif
    if(NULL != m_pRoot)
    {
     m_pRoot->PostOrder(VisitNode,pData);
    }
#ifdef GRS_MT
    //离开关键代码段
    ::LeaveCriticalSection(&m_cs);
#endif
   }

   void LevelOrder( void (*VisitNode)(CGRSAVLTreeNode<TKey,TData>* pNode,void* pData),void*pData)
   {// 逐层遍历
#ifdef GRS_MT
    //进入关键代码段
    ::EnterCriticalSection(&m_cs);
#endif
    CGRSList<CGRSAVLTreeNode<TKey,TData>*> NodeQuery;
    CGRSAVLTreeNode<TKey,TData> *pTmp = m_pRoot;
    while (NULL != pTmp)
    {
     VisitNode(pTmp,pData) ;
     if (NULL != pTmp->m_pLeft)
     {
      NodeQuery.AddTail(pTmp->m_pLeft);
     }

     if (NULL != pTmp->m_pRight)
     {
      NodeQuery.AddTail(pTmp->m_pRight);
     }

     pTmp = NodeQuery.RemoveHead();
    }
#ifdef GRS_MT
    //离开关键代码段
    ::LeaveCriticalSection(&m_cs);
#endif
   }


  };
#ifdef GRS_USE_NS
 }
}
#endif

 

  评论这张
 
阅读(1019)| 评论(0)

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018