支持HW团队,就支付宝领取下面的红包吧!(2018年3月31前,就几毛,也会几块,可以和其他红包叠加使用),你领取消费,HW有奖励。红包使用无条件限制,有条件请注意是不是有病毒。

小伙伴们,给大家发红包喽!人人可领,领完就能用。祝大家领取的红包金额大大大!#吱口令#长按复制此消息,打开支付宝就能领取!er1OEj73Uj

登入 注册 | 验证
| 搜索
HelloWorld论坛 : > 计算机科学、技术、教学> 编程专题> 开源免费项目> [原创]ACE内存分配——不定长数据,不定量个数分配(二)——平衡二叉树 模板
 
 
 
 
 
 
类别:ACE 阅读:8786 评论:0 时间:五月 21, 2013, 5:48 p.m. 关键字:AVL tree 平衡二叉树

 

我将用平衡二叉树(AVL)实现,让我们先学习一下基础知识吧,请看

[转]平衡二叉树

[转]一步一步写平衡二叉树(AVL树)

平衡二叉树调整方法整理如下:

    为了能使劳动成果得到最大限度的复用,我特别写了一个非递归平衡二叉树模板,里面的节点都有父节点,是为了删除节点方便,但是最终还是为这个不定长分配服务,如果你有其他特殊要求,请自己改写。代码如下:

/***************************************************************
version:  1.0
date: 22/5/2013   9:10
FileName:     hwnet_avl_tree.h
Author:       丁灵峰
Compiled on:   VC.net 2008
-------------------------------------------------------------
Description:
Modification history:
Other:

-------------------------------------------------------------
Copyright (C) 2010 - All Rights Reserved
***************************************************************
二叉搜索树的平衡因子定义为最左边子树深度和最右边子树深度之间的差。

TreeNode 是最基本的节点,m_Date要能复杂构造,并自己实现内存释放,如果需要。
AVLTree 是一颗允许有相同值的平衡二叉树,两个类型:节点、关键字,也就是节点的申请释放,AVLTree都不负责。
我们可以这样创建平衡二叉树  节点里面的m_Date能和关键字 比较大小
hwnet::AVLTree<hwnet::AllocatorNode<int>, int> avlTree;
或者自己实现包含TreeNode属性的节点

节点的 m_Date  要支持 > < 比较,都为false 就是=
m_Date TKey 也要支持 > < 比较
m_Date TKey 可以是同一个类型

遍历是提供给调试用的,默认不开启


在这里我们要实现非递归创建创建一颗平衡二叉树,下面是递归的思想,根节点的深度增加的时候,是要递归调整
(1) 若该树为一空树,那么插入的节点作为平衡二叉树的根节点,树的高度增加1。

(2) 若待插入的节点和平衡二叉树的根节点的关键字相等,那么就插入根节点的等值队列,树的深度不变。

(3) 若待插入的节点和平衡二叉树的根节点的关键字不相等,小于,插入在根节点的左子树上,大于,插入到根节点的右子树上,分别就下列情况处理之。

(a) 根节点的平衡因子为0(左右子树的深度相等):则根节点的深度不变。

(b) 根节点的平衡因子为1(左子树的深度大于右子树的深度),或者 -1(右子树的深度大于左子树的深度):则根节点的深度增加1。

(c) 根节点的平衡因子为2(左子树的深度大于右子树的深度):则根节点需要调整。
        若根节点的左子树根节点的平衡因子为1:左单旋转(LL)型调整
        若根节点的左子树根节点的平衡因子为-1:先左后右双向旋转(LR)型调整

(d) 根节点的平衡因子为-2(右子树的深度大于左子树的深度):则根节点需要调整。
        若根节点的右子树根节点的平衡因子为1:先右后左双向旋转(RL)型调整
        若根节点的右子树根节点的平衡因子为-1:右单旋转(RR)型调整

(e) 根节点做过调整的,树深度变化了,所以相连节点的平衡因子要重新判断是否需要调整。
****************************************************************/
#ifndef _H_hwnet_avl_tree_
#define _H_hwnet_avl_tree_

namespace hwnet
{
        //AVL树节点信息
        template<class T>
        class TreeNode
        {
        public:
                TreeNode(T date): m_Date(date),m_ihgt(0), m_pFather(NULL), m_pLchild(NULL), m_pRchild(NULL), m_pNode(NULL){}
                T m_Date;//值
                size_t m_ihgt;//以此节点为根的树的高度
                TreeNode<T>* m_pFather;//指向父节点的地址
                TreeNode<T>* m_pLchild;//指向左儿子的地址
                TreeNode<T>* m_pRchild;//指向右儿子的地址
                TreeNode<T>* m_pNode;//指向等值节点的地址
        };
        //AVL树类
        template<class TNode, class TKey>
        class AVLTree
        {
                // 友元
                // 静态属性
                // 静态函数
                //计算节点的高度
                static int Height(TNode* node)
                {
                        if(node!=NULL)
                                return node->m_ihgt;
                        return -1;
                }
                //求最大值
                static int AVLMax(int cmpa,int cmpb)
                {
                        return cmpa>cmpb?cmpa:cmpb;
                }
                // 静态工具
                // 接口实现

                // 构造于析构
        public:
                virtual ~AVLTree(void);
                AVLTree(void);

                // 操作函数
        public:
                void Insert(TNode*); // 插入节点
                TNode* Find(TKey); // 等值查找
                TNode* FindLessOrGreater(TKey, bool = true); // 大于等于查找  小于等于查找 默认 true  大于找最小 及 TKey <= TNode->m_Date
                void Delete(TNode*); // 删除
#if 0
                void Traversal(); // 遍历
#endif
                // 得到根节点,如果有必要,外部递归释放资源
                TNode* GetRoot() { return m_pRoot; }
                // 得到节点个数
                size_t size() { return m_uSim; }

                // 工具函数
        private:
        protected:
                void Chick(TNode*); // 调整
                void ReplaceRelation(TNode*, TNode*, TNode*); // 替换节点关系
                void SingRotateLeft(TNode*); // 左单旋转(LL)型调整
                void SingRotateRight(TNode*); // 右单旋转(RR)型调整
                void DoubleRotateLR(TNode*); // 先左后右双向旋转(LR)型调整
                void DoubleRotateRL(TNode*); // 先右后左双向旋转(RL)型调整
#if 0
                void insubtree(TNode* node);//中序遍历
#endif

                // 禁止
        private:
                AVLTree(const AVLTree&); //复制构造
                AVLTree & operator= (const AVLTree&); // 等于重载

                // 属性
        public:
        protected:
                TNode* m_pRoot;//根节点
                size_t m_uSim; // 节点个数
        };
}
#include "hwnet_avl_tree.cpp"
#endif // #ifndef _H_hwnet_avl_tree
/***************************************************************
version:  1.0
date: 22/5/2013   14:03
FileName:     hwnet_avl_tree.cpp
Author:       丁灵峰
Compiled on:   VC.net 2003
-------------------------------------------------------------
Description:
Modification history:
Other:

-------------------------------------------------------------
Copyright (C) 2010 - All Rights Reserved
***************************************************************/
#include "stdafx.h"
#ifndef _CPP_hwnet_avl_tree_
#define _CPP_hwnet_avl_tree_
#include "hwnet_avl_tree.h"

namespace hwnet
{
        //////////////////////////////////////////////////////////////////////////
        // 静态属性
        //////////////////////////////////////////////////////////////////////////
        // 静态函数
        //////////////////////////////////////////////////////////////////////////
        // 静态工具
        //////////////////////////////////////////////////////////////////////////
        // 接口实现
        //////////////////////////////////////////////////////////////////////////
        // 析构
        template<class TNode, class TKey>
        AVLTree<TNode, TKey>::~AVLTree(void)
        {
        }

        // 默认构造
        template<class TNode, class TKey>
        AVLTree<TNode, TKey>::AVLTree(void)
                : m_pRoot(NULL)
                , m_uSim(0) // 节点个数
        {
        }

        //////////////////////////////////////////////////////////////////////////
        // 操作函数
        // 插入
        template<class TNode, class TKey>
        void AVLTree<TNode, TKey>::Insert(TNode* pNode)
        {
                if (pNode == NULL)
                {
                        return ;
                }
                m_uSim++;
                pNode->m_ihgt = 0;//以此节点为根的树的高度
                pNode->m_pFather = NULL;//指向父节点的地址
                pNode->m_pLchild = NULL;//指向左儿子的地址
                pNode->m_pRchild = NULL;//指向右儿子的地址
                pNode->m_pNode = NULL;//指向等值节点的地址
                // 如果节点为空,就在此节点处加入pNode信息
                if(this->m_pRoot==NULL)
                {
                        this->m_pRoot = pNode;
                        return;
                }
                TNode* pRoot = this->m_pRoot;
                do 
                {
                        // 如果pNode小于节点的值,就继续在pRoot的左子树中插入pNode
                        if(pNode->m_Date < pRoot->m_Date)
                        {
                                // 如果节点为空,就在此节点处加入pNode信息
                                if(pRoot->m_pLchild==NULL)
                                {
                                        pRoot->m_pLchild = pNode;
                                        pNode->m_pFather = pRoot;
                                        break;
                                }
                                else
                                {
                                        pRoot = pRoot->m_pLchild;
                                        continue;
                                }
                        }
                        // 如果pNode大于节点的值,就继续在pRoot的右子树中插入pNode
                        else if(pRoot->m_Date < pNode->m_Date)
                        {
                                // 如果节点为空,就在此节点处加入pNode信息
                                if(pRoot->m_pRchild==NULL)
                                {
                                        pRoot->m_pRchild = pNode;
                                        pNode->m_pFather = pRoot;
                                        break;
                                }
                                else
                                {
                                        pRoot = pRoot->m_pRchild;
                                        continue;
                                }
                        }
                        else
                        {
                                // 如果相等
                                pNode->m_pNode = pRoot->m_pNode;
                                if (pNode->m_pNode)
                                {
                                        pNode->m_pNode->m_pFather = pNode;
                                }
                                pRoot->m_pNode = pNode;
                                pNode->m_pFather = pRoot;
                                return ;
                        }
                } while (true);
                // 调整树深度 调整
                return Chick(pRoot);
        }
        // 等值查找
        template<class TNode, class TKey>
        TNode* AVLTree<TNode, TKey>::Find(TKey xKey)
        {
                TNode* pNode = this->m_pRoot;
                do
                {
                        // 如果节点为空说明没找到,返回NULL
                        if(pNode==NULL)
                        {
                                return NULL;
                        }
                        // 如果小于节点的值,就继续在节点的左子树中查找
                        if(xKey < pNode->m_Date)
                        {
                                pNode = pNode->m_pLchild;
                                continue;
                        }
                        else if(pNode->m_Date < xKey)//如果iSize大于节点的值,就继续在节点的右子树中查找x
                        {
                                pNode = pNode->m_pRchild;
                                continue;
                        }
                        else
                        {
                                // 如果相等,就找到了此节点
                                // 看看有没有等值节点
                                if (pNode->m_pNode)
                                {
                                        return pNode->m_pNode;
                                }
                                return pNode;
                        }
                } while (true);
                return NULL;
        }
        // 大于等于查找  小于等于查找 默认 true 大于等于查找 及 TKey >= TNode->m_Date
        // true 大于找最小
        // false 小于找最大
        template<class TNode, class TKey>
        TNode* AVLTree<TNode, TKey>::FindLessOrGreater(TKey xKey, bool bF)
        {
                TNode* pNode = this->m_pRoot;
                TNode* pNodeMax = NULL; // 小于xKey最大
                TNode* pNodeMin = NULL; // 大于xKey最小
                do
                {
                        // 如果节点为空说明没找到,返回NULL
                        if(pNode==NULL)
                        {
                                if (bF)
                                {
                                        // 大于xKey最小
                                        return pNodeMin;
                                }
                                else
                                {
                                        // 小于xKey最大
                                        return pNodeMax;
                                }
                        }
                        // 如果小于节点的值,就继续在节点的左子树中查找
                        if(xKey < pNode->m_Date)
                        {
                                // 大于xKey最小
                                if (pNodeMin)
                                {
                                        if (pNode->m_Date < pNodeMin->m_Date)
                                        {
                                                pNodeMin = pNode;
                                        }
                                }
                                else
                                {
                                        pNodeMin = pNode;
                                }
                                pNode = pNode->m_pLchild;
                                continue;
                        }
                        //如果大于节点的值,就继续在节点的右子树中查找x
                        else if(pNode->m_Date < xKey)
                        {
                                // 小于xKey最大
                                if (pNodeMax)
                                {
                                        if (pNode->m_Date > pNodeMax->m_Date)
                                        {
                                                pNodeMax = pNode;
                                        }
                                }
                                else
                                {
                                        pNodeMax = pNode;
                                }
                                pNode = pNode->m_pRchild;
                                continue;
                        }
                        else
                        {
                                // 如果相等,就找到了此节点
                                // 看看有没有等值节点
                                if (pNode->m_pNode)
                                {
                                        return pNode->m_pNode;
                                }
                                return pNode;
                        }
                } while (true);
                return NULL;
        }
        // 删除
        template<class TNode, class TKey>
        void AVLTree<TNode, TKey>::Delete(TNode* pRoot)
        {
                if (pRoot == NULL)
                {
                        return ;
                }
                m_uSim--;
                // 是等值节点
                if((pRoot->m_pFather) && (pRoot->m_pFather->m_pNode == pRoot))
                {
                        pRoot->m_pFather->m_pNode = pRoot->m_pNode;
                        if (pRoot->m_pNode)
                        {
                                pRoot->m_pNode->m_pFather = pRoot->m_pFather;
                        }
                }
                // 有等值节点
                else if (pRoot->m_pNode)
                {
                        if (pRoot->m_pFather)
                        {
                                if (pRoot->m_pFather->m_pLchild == pRoot)
                                {
                                        pRoot->m_pFather->m_pLchild = pRoot->m_pNode;
                                }
                                else if (pRoot->m_pFather->m_pRchild == pRoot)
                                {
                                        pRoot->m_pFather->m_pRchild = pRoot->m_pNode;
                                }
                                else
                                {
                                        pRoot->m_pFather->m_pNode = pRoot->m_pNode;
                                }
                                pRoot->m_pNode->m_pFather = pRoot->m_pFather;
                        } 
                        else
                        {
                                this->m_pRoot = pRoot->m_pNode;
                                pRoot->m_pNode->m_pFather = NULL;
                        }
                        pRoot->m_pNode->m_pLchild = pRoot->m_pLchild;
                        if (pRoot->m_pLchild)
                        {
                                pRoot->m_pLchild->m_pFather = pRoot->m_pNode;
                        }
                        pRoot->m_pNode->m_pRchild = pRoot->m_pRchild;
                        if (pRoot->m_pRchild)
                        {
                                pRoot->m_pRchild->m_pFather = pRoot->m_pNode;
                        }
                        pRoot->m_pNode->m_ihgt = pRoot->m_ihgt;
                }
                else
                {
                        // 此节点有两个儿子
                        if(pRoot->m_pLchild && pRoot->m_pRchild)
                        {
                                // temp指向节点的右儿子
                                TNode* pNode=pRoot->m_pRchild;
                                // 找到右子树中值最小的节点
                                while(pNode->m_pLchild != NULL) pNode=pNode->m_pLchild;
                                // 替换两个节点
                                ReplaceRelation(pNode, pRoot->m_pLchild, NULL);
                                pRoot->m_pLchild = NULL;
                                if (pNode->m_pFather == pRoot)
                                {
                                        pRoot->m_pRchild = pNode->m_pRchild;
                                        pNode->m_pRchild = pRoot;
                                        TNode* pFather = pRoot->m_pFather;
                                        pRoot->m_pFather = pNode;
                                        pNode->m_pFather = pFather;
                                        if (pFather != NULL)
                                        {
                                                if (pFather->m_pLchild == pRoot)
                                                {
                                                        pFather->m_pLchild = pNode;
                                                }
                                                else
                                                {
                                                        pFather->m_pRchild = pNode;
                                                }
                                        }
                                        else
                                        {
                                                this->m_pRoot = pNode;
                                        }
                                        pNode->m_ihgt = pRoot->m_ihgt;
                                }
                                else
                                {
                                        {
                                                TNode* pFather = pRoot->m_pFather;
                                                pRoot->m_pFather = pNode->m_pFather;
                                                assert(pRoot->m_pFather);
                                                if (pRoot->m_pFather->m_pLchild == pNode)
                                                {
                                                        pRoot->m_pFather->m_pLchild = pRoot;
                                                }
                                                else
                                                {
                                                        pRoot->m_pFather->m_pRchild = pRoot;
                                                }
                                                pNode->m_pFather = pFather;
                                                if (pFather != NULL)
                                                {
                                                        if (pFather->m_pLchild == pRoot)
                                                        {
                                                                pFather->m_pLchild = pNode;
                                                        }
                                                        else
                                                        {
                                                                pFather->m_pRchild = pNode;
                                                        }
                                                }
                                                else
                                                {
                                                        this->m_pRoot = pNode;
                                                }
                                        }
                                        {
                                                TNode* pRchild = pRoot->m_pRchild;
                                                TNode* pRchild2 = pNode->m_pRchild;
                                                ReplaceRelation(pRoot, pNode->m_pRchild, pRchild);
                                                ReplaceRelation(pNode, pRchild, pRchild2);
                                        }
                                        pNode->m_ihgt = AVLMax(Height(pNode->m_pLchild),Height(pNode->m_pRchild))+1;
                                }
                        }
                        // 此节点有1个或0个儿子
                        //if(pRoot->m_pLchild || pRoot->m_pRchild)
                        {
                                // 有右儿子或者没有儿子
                                if(pRoot->m_pLchild==NULL)
                                        ReplaceRelation(pRoot->m_pFather, pRoot->m_pRchild, pRoot);
                                // 有左儿子
                                else if(pRoot->m_pRchild==NULL)
                                        ReplaceRelation(pRoot->m_pFather, pRoot->m_pLchild, pRoot);
                                pRoot = pRoot->m_pFather;
                        }
                        // 调整树深度 调整
                        return Chick(pRoot);
                }
                return ;
        }
#if 0
        //中序遍历接口
        template<class TNode, class TKey>
        void AVLTree<TNode, TKey>::Traversal()
        {
                insubtree(m_pRoot);
                std::cout << std::endl;
        }
#endif
        // 调整
        template<class TNode, class TKey>
        void AVLTree<TNode, TKey>::Chick(TNode* pRoot)
        {
                static const size_t m_uSizeAllocator = 64;
                size_t m_uUsedAllocator = 0;
                TNode* deqNode[m_uSizeAllocator] = {0};
                while (pRoot)
                {
                        //long i=Height(pRoot->m_pLchild)-Height(pRoot->m_pRchild);
                        //if (i < -1)
                        //{
                        //      if(Height(pRoot->m_pRchild->m_pLchild) < Height(pRoot->m_pRchild->m_pRchild))
                        //              SingRotateRight(pRoot);
                        //      else
                        //              DoubleRotateRL(pRoot);
                        //      return ;
                        //}
                        //else if (i < 1)
                        //{
                        //      if (pRoot->m_ihgt == AVLMax(Height(pRoot->m_pLchild),Height(pRoot->m_pRchild))+1)
                        //      {
                        //              // 不用调整
                        //              return ;
                        //      }
                        //      pRoot->m_ihgt = AVLMax(Height(pRoot->m_pLchild),Height(pRoot->m_pRchild))+1;
                        //      pRoot = pRoot->m_pFather;
                        //} 
                        //else
                        //{
                        //      if(Height(pRoot->m_pLchild->m_pLchild) < Height(pRoot->m_pLchild->m_pRchild))
                        //              DoubleRotateLR(pRoot);
                        //      else
                        //              SingRotateLeft(pRoot);
                        //      return ;
                        //}
                        switch (Height(pRoot->m_pLchild)-Height(pRoot->m_pRchild))
                        {
                        case 0:
                        case 1:
                        case -1:
                                {
                                        if (pRoot->m_ihgt == AVLMax(Height(pRoot->m_pLchild),Height(pRoot->m_pRchild))+1)
                                        {
                                                // 不用调整
                                                pRoot = NULL;
                                                break ;
                                        }
                                        pRoot->m_ihgt = AVLMax(Height(pRoot->m_pLchild),Height(pRoot->m_pRchild))+1;
                                        pRoot = pRoot->m_pFather;
                                }
                                break;
                        case 2:
                                {
                                        TNode* pFather = pRoot->m_pFather;
                                        if(Height(pRoot->m_pLchild->m_pLchild) < Height(pRoot->m_pLchild->m_pRchild))
                                        {
                                                TNode* pNodeA = pRoot;
                                                TNode* pNodeB = pRoot->m_pLchild;
                                                DoubleRotateLR(pRoot);
                                                if (pNodeA && abs(Height(pNodeA->m_pLchild)-Height(pNodeA->m_pRchild)) > 1)
                                                {
                                                        if (m_uUsedAllocator < m_uSizeAllocator)
                                                        {
                                                                deqNode[m_uUsedAllocator] = pNodeA;
                                                                m_uUsedAllocator++;
                                                        }
                                                        else
                                                        {
                                                                this->Chick(pNodeA);
                                                        }
                                                        pFather = NULL;
                                                }
                                                if (pNodeB && abs(Height(pNodeB->m_pLchild)-Height(pNodeB->m_pRchild)) > 1)
                                                {
                                                        if (m_uUsedAllocator < m_uSizeAllocator)
                                                        {
                                                                deqNode[m_uUsedAllocator] = pNodeB;
                                                                m_uUsedAllocator++;
                                                        }
                                                        else
                                                        {
                                                                this->Chick(pNodeB);
                                                        }
                                                        pFather = NULL;
                                                }
                                        }
                                        else
                                        {
                                                TNode* pNodeA = pRoot;
                                                TNode* pNodeX = pRoot->m_pLchild->m_pLchild;
                                                SingRotateLeft(pRoot);
                                                if (pNodeA && abs(Height(pNodeA->m_pLchild)-Height(pNodeA->m_pRchild)) > 1)
                                                {
                                                        if (m_uUsedAllocator < m_uSizeAllocator)
                                                        {
                                                                deqNode[m_uUsedAllocator] = pNodeA;
                                                                m_uUsedAllocator++;
                                                        }
                                                        else
                                                        {
                                                                this->Chick(pNodeA);
                                                        }
                                                        pFather = NULL;
                                                }
                                                if (pNodeX && abs(Height(pNodeX->m_pLchild)-Height(pNodeX->m_pRchild)) > 1)
                                                {
                                                        if (m_uUsedAllocator < m_uSizeAllocator)
                                                        {
                                                                deqNode[m_uUsedAllocator] = pNodeX;
                                                                m_uUsedAllocator++;
                                                        }
                                                        else
                                                        {
                                                                this->Chick(pNodeX);
                                                        }
                                                        pFather = NULL;
                                                }
                                        }
                                        if (pFather)
                                        {
                                                if (m_uUsedAllocator < m_uSizeAllocator)
                                                {
                                                        deqNode[m_uUsedAllocator] = pFather;
                                                        m_uUsedAllocator++;
                                                }
                                                else
                                                {
                                                        this->Chick(pFather);
                                                }
                                        }
                                        pRoot = NULL;
                                }
                                break;
                        case -2:
                                {
                                        TNode* pFather = pRoot->m_pFather;
                                        if(Height(pRoot->m_pRchild->m_pLchild) < Height(pRoot->m_pRchild->m_pRchild))
                                        {
                                                TNode* pNodeA = pRoot;
                                                TNode* pNodeX = pRoot->m_pRchild->m_pRchild;
                                                SingRotateRight(pRoot);
                                                if (pNodeA && abs(Height(pNodeA->m_pLchild)-Height(pNodeA->m_pRchild)) > 1)
                                                {
                                                        if (m_uUsedAllocator < m_uSizeAllocator)
                                                        {
                                                                deqNode[m_uUsedAllocator] = pNodeA;
                                                                m_uUsedAllocator++;
                                                        }
                                                        else
                                                        {
                                                                this->Chick(pNodeA);
                                                        }
                                                        pFather = NULL;
                                                }
                                                if (pNodeX && abs(Height(pNodeX->m_pLchild)-Height(pNodeX->m_pRchild)) > 1)
                                                {
                                                        if (m_uUsedAllocator < m_uSizeAllocator)
                                                        {
                                                                deqNode[m_uUsedAllocator] = pNodeX;
                                                                m_uUsedAllocator++;
                                                        }
                                                        else
                                                        {
                                                                this->Chick(pNodeX);
                                                        }
                                                        pFather = NULL;
                                                }
                                        }
                                        else
                                        {
                                                TNode* pNodeA = pRoot;
                                                TNode* pNodeB = pRoot->m_pRchild;
                                                DoubleRotateRL(pRoot);
                                                if (pNodeA && abs(Height(pNodeA->m_pLchild)-Height(pNodeA->m_pRchild)) > 1)
                                                {
                                                        if (m_uUsedAllocator < m_uSizeAllocator)
                                                        {
                                                                deqNode[m_uUsedAllocator] = pNodeA;
                                                                m_uUsedAllocator++;
                                                        }
                                                        else
                                                        {
                                                                this->Chick(pNodeA);
                                                        }
                                                        pFather = NULL;
                                                }
                                                if (pNodeB && abs(Height(pNodeB->m_pLchild)-Height(pNodeB->m_pRchild)) > 1)
                                                {
                                                        if (m_uUsedAllocator < m_uSizeAllocator)
                                                        {
                                                                deqNode[m_uUsedAllocator] = pNodeB;
                                                                m_uUsedAllocator++;
                                                        }
                                                        else
                                                        {
                                                                this->Chick(pNodeB);
                                                        }
                                                        pFather = NULL;
                                                }
                                        }
                                        if (pFather)
                                        {
                                                if (m_uUsedAllocator < m_uSizeAllocator)
                                                {
                                                        deqNode[m_uUsedAllocator] = pFather;
                                                        m_uUsedAllocator++;
                                                }
                                                else
                                                {
                                                        this->Chick(pFather);
                                                }
                                        }
                                        pRoot = NULL;
                                }
                                break;
                        default:
                                {
                                        pRoot = pRoot;
                                }
                                break;
                        }
                        if (pRoot == NULL)
                        {
                                if (m_uUsedAllocator > 0)
                                {
                                        m_uUsedAllocator--;
                                        pRoot = deqNode[m_uUsedAllocator];
                                }
                        }
                }
                return ;
        }

        //////////////////////////////////////////////////////////////////////////
        // 工具函数
        // 建立节点关系
        template<class TNode, class TKey>
        void AVLTree<TNode, TKey>::ReplaceRelation(TNode* pRoot, TNode* pNode, TNode* pNodeOld)
        {
                if (pRoot == NULL)
                {
                        this->m_pRoot = pNode;
                        if (pNode)
                        {
                                pNode->m_pFather = NULL;
                        }
                }
                else if (pNode == NULL)
                {
                        if (pRoot->m_pLchild == pNodeOld)
                        {
                                pRoot->m_pLchild = NULL;
                        }
                        else
                        {
                                pRoot->m_pRchild = NULL;
                        }
                }
                else
                {
                        // 如果pNode < pRoot
                        if(pNode->m_Date < pRoot->m_Date)
                        {
                                pRoot->m_pLchild = pNode;
                                pNode->m_pFather = pRoot;
                        }
                        // 如果pNode大于节点的值,就继续在pRoot的右子树中插入pNode
                        else if(pRoot->m_Date < pNode->m_Date)
                        {
                                pRoot->m_pRchild = pNode;
                                pNode->m_pFather = pRoot;
                        }
                        // 如果相等
                        else
                        {
                                assert(false);
                        }
                }
        }
        // 左单旋转(LL)型调整
        template<class TNode, class TKey>
        void AVLTree<TNode, TKey>::SingRotateLeft(TNode* pNodeA)
        {
                TNode* pNodeB = pNodeA->m_pLchild;
                TNode* pNode2 = pNodeB->m_pRchild;
                // 先调整父节点
                ReplaceRelation(pNodeA->m_pFather, pNodeB, pNodeA);
                // B
                ReplaceRelation(pNodeB, pNodeA, pNode2);
                // X没变
                // A
                ReplaceRelation(pNodeA, pNode2, pNodeB);

                pNodeA->m_ihgt=AVLMax(Height(pNodeA->m_pLchild),Height(pNodeA->m_pRchild))+1;
                pNodeB->m_ihgt=AVLMax(Height(pNodeB->m_pLchild),pNodeA->m_ihgt)+1;
        }
        // 右单旋转(RR)型调整
        template<class TNode, class TKey>
        void AVLTree<TNode, TKey>::SingRotateRight(TNode* pNodeA)
        {
                TNode* pNodeB = pNodeA->m_pRchild;
                TNode* pNode2 = pNodeB->m_pLchild;
                // 先调整父节点
                ReplaceRelation(pNodeA->m_pFather, pNodeB, pNodeA);
                // B
                ReplaceRelation(pNodeB, pNodeA, pNode2);
                // X没变
                // A
                ReplaceRelation(pNodeA, pNode2, pNodeB);

                pNodeA->m_ihgt=AVLMax(Height(pNodeA->m_pLchild),Height(pNodeA->m_pRchild))+1;
                pNodeB->m_ihgt=AVLMax(pNodeA->m_ihgt,Height(pNodeB->m_pRchild))+1;
        }
        // 先左后右双向旋转(LR)型调整
        template<class TNode, class TKey>
        void AVLTree<TNode, TKey>::DoubleRotateLR(TNode* pNodeA)
        {
                SingRotateRight(pNodeA->m_pLchild);
                SingRotateLeft(pNodeA);
        }
        // 先右后左双向旋转(RL)型调整
        template<class TNode, class TKey>
        void AVLTree<TNode, TKey>::DoubleRotateRL(TNode* pNodeA)
        {
                SingRotateLeft(pNodeA->m_pRchild);
                SingRotateRight(pNodeA);
        }
#if 0
        //中序遍历函数
        template<class TNode, class TKey>
        void AVLTree<TNode, TKey>::insubtree(TNode* pNode)
        {
                if(pNode==NULL) return;
                insubtree(pNode->m_pLchild);//先遍历左子树
                if (pNode->m_pNode)
                {
                        long i=1;
                        TNode* pNodeEx = pNode->m_pNode;
                        while (pNodeEx)
                        {
                                i++;
                                pNodeEx = pNodeEx->m_pNode;
                        }
                        std::cout << pNode->m_Date << "(" << i << ")  "; // 输出根节点
                }
                else
                {
                        std::cout << pNode->m_Date << "  "; // 输出根节点
                }
                insubtree(pNode->m_pRchild);//再遍历右子树
        }
#endif

        //// 禁止
        //// 复制构造
        //template<class TNode, class TKey>
        //AVLTree<TNode, TKey>::AVLTree<TNode, TKey>(const hwnet_avl_tree& inOther)
        //{
        //      this->operator =(inOther);
        //}
        //
        //// 等于重载
        //template<class TNode, class TKey>
        //AVLTree<TNode, TKey> & AVLTree<TNode, TKey>::operator= (const hwnet_avl_tree& inOther)
        //{
        //      if (this != &inOther)
        //      {
        //      }
        //      return (*this);
        //}
}
#endif // #ifndef _CPP_hwnet_avl_tree_

    用转载文章里面的一个例子做测试用例,开启遍历。

hwnet::AVLTree<hwnet::TreeNode<int>, int> avlTree;
hwnet::TreeNode<int>* pNode = new hwnet::TreeNode<int>(20);
avlTree.Insert(new hwnet::TreeNode<int>(16));
avlTree.Insert(new hwnet::TreeNode<int>(3));
avlTree.Traversal();
avlTree.Insert(new hwnet::TreeNode<int>(7));
avlTree.Traversal();
avlTree.Insert(new hwnet::TreeNode<int>(11));
avlTree.Traversal();
avlTree.Insert(new hwnet::TreeNode<int>(9));
avlTree.Traversal();
avlTree.Insert(new hwnet::TreeNode<int>(26));
avlTree.Traversal();
avlTree.Insert(new hwnet::TreeNode<int>(18));
avlTree.Traversal();
avlTree.Insert(new hwnet::TreeNode<int>(14));
avlTree.Traversal();
avlTree.Insert(new hwnet::TreeNode<int>(15));
avlTree.Traversal();
avlTree.Insert(pNode);
hwnet::TreeNode<int>* pNodeEx = avlTree.Find(20);
assert(pNode == pNodeEx);
avlTree.Delete(pNode);
{
        hwnet::TreeNode<int>* pNodeFind = avlTree.Find(7);
        avlTree.Delete(pNodeFind);
}
{
        hwnet::TreeNode<int>* pNodeFind = avlTree.Find(18);
        avlTree.Delete(pNodeFind);
}
avlTree.Traversal();

 附上原图:

 

 
 
[挂载人]初学MPEG [审核人]初学MPEG 推荐

个人签名--------------------------------------------------------------------------------

Please Login (or Sign Up) to leave a comment