特别声明：
建议使用google游览器,火狐也可以
论坛处于测试阶段，一切资料都为测试资料，在论坛正式运行的时候，会尽量保存网友的劳动成果！
HelloWorld论坛秉持互惠互利，共同学习与进步，一个人的梦想大家实现的理想，一直坚持着，望广大网友多多支持，提供宝贵意见
来论坛做什么？
可以先转载你平时学习查找的资料（先论坛查找），自己可以写写体会
把平时碰到的问题，如何解决可以先记录在论坛，以备后来的人学习
可以和会员一起参加一些开源项目的学习，汉化，推广，甚至可以加入团队
|
|
|
我将用平衡二叉树（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 | ||
|
||
|
|
||
Please Login (or Sign Up) to leave a comment |
个人签名--------------------------------------------------------------------------------