猫史档案馆

代码模板直接摆出来，不多bb

//AVL.h
#pragma once
//平衡二叉树模板
//SJ2050
#include "BinTree.h"

#define OK 1
#define FALSE 0

//平衡二叉树类模板定义
template <class ElemType>
class AVL : public BinTree<ElemType>
{
public:
void Print(); //将二叉树中的内容打印出来
BinTreeNode<ElemType>* Search(ElemType data); //搜索节点函数
bool Insert(ElemType data); //插入节点函数
bool Delete(ElemType data); //删除节点函数

private:
void Rotate(BinTreeNode<ElemType> &unbalancedNode); //旋转函数
void Connect34(BinTreeNode<ElemType> *a, BinTreeNode<ElemType> *b, BinTreeNode<ElemType> *c,\
BinTreeNode<ElemType> *T0, BinTreeNode<ElemType> *T1, BinTreeNode<ElemType> *T2,\
BinTreeNode<ElemType> *T3); //3+4重构函数
int CalculateBF(BinTreeNode<ElemType> &node); //计算失衡值
void PrintOut(BinTreeNode<ElemType> *beginNode); //采用中序遍历对二叉树进行打印
};

//函数功能：搜索待查找的节点，并返回其位置（供用户调用）
//函数参数：待查找的值
//函数返回值：待查找的节点的指针或该节点应该出现位置的父节点的指针，若树为空返回nullptr
template <class ElemType>
BinTreeNode<ElemType>* AVL<ElemType>::Search(ElemType data) //搜索节点函数
{
if (this->root == nullptr)
{ //当树还为空时
return nullptr;
}

BinTreeNode<ElemType> *x = this->root; //x节点
BinTreeNode<ElemType> *p = x->parent; //p为x的父节点

while (x != nullptr && x->data != data )
{
p = x;
if (data > x->data)
{ 
x = x->rightChild;
}
else
{
x = x->leftChild;
}
}

if (x == nullptr)
{ //当搜索不到要查找的节点时，返回应出现位置的父节点的指针
return p;
}
else
{ //当搜索到要查找的节点时，返回该节点的指针
return x;
}
}

//函数功能：3+4重构实现旋转操作（Private）
//函数参数：三个节点和四棵子树的二级指针
//函数返回值：void
template <class ElemType>
void AVL<ElemType>::Connect34(BinTreeNode<ElemType> *a, BinTreeNode<ElemType> *b, \
BinTreeNode<ElemType> *c, \
BinTreeNode<ElemType> *T0, BinTreeNode<ElemType> *T1, \
BinTreeNode<ElemType> *T2, BinTreeNode<ElemType> *T3)
{ //a,c为b的左右孩子，T0,T1,T2,T3又分别为a,c的左右子树
b->leftChild = a;
a->parent = b;
b->rightChild = c;
c->parent = b;

a->leftChild = T0;
if (T0) T0->parent = a; //T0可能为空
a->rightChild = T1;
if (T1) T1->parent = a; //T1可能为空

c->leftChild = T2;
if (T2) T2->parent = c; //T2可能为空
c->rightChild = T3;
if (T3) T3->parent = c; //T3可能为空

//更新三个节点的树高
UpdateHeight(*a);
UpdateHeight(*c);
UpdateHeight(*b);
}

//函数功能：计算节点的失衡值（Private）
//函数参数：要计算的节点的引用
//函数返回值：计算得到的失衡值
template <class ElemType>
int AVL<ElemType>::CalculateBF(BinTreeNode<ElemType> &node)
{ //失衡值计算方法为左子树高减去右子树高
int leftTreeHeight = (node.leftChild == nullptr ? 0 : node.leftChild->height); //左子树的高
int rightTreeHeight = (node.rightChild == nullptr ? 0 : node.rightChild->height); //右子树的高

return leftTreeHeight - rightTreeHeight;
}

//函数功能：进行旋转操作（Private）
//函数参数：失衡节点引用
//函数返回值：void
template <class ElemType>
void AVL<ElemType>::Rotate(BinTreeNode<ElemType> &unbalancedNode)
{
int bf = CalculateBF(unbalancedNode); //计算出失衡节点的平衡值

if (bf > 0)
{
if (CalculateBF(*unbalancedNode.leftChild) >= 0)
{ //zig型
BinTreeNode<ElemType> *x = unbalancedNode.leftChild->leftChild; //失衡节点的孙节点
BinTreeNode<ElemType> *p = unbalancedNode.leftChild; //失衡节点的子节点
BinTreeNode<ElemType> *g = &unbalancedNode; //失衡节点
//p顶替g的位置
p->parent = g->parent;
if (g->parent != nullptr)
{ //失衡节点有父节点时
if (g->parent->leftChild == g) g->parent->leftChild = p;
else g->parent->rightChild = p;
}
else
{ //失衡节点无父节点时
this->root = p;
}

Connect34(x, p, g, x->leftChild, x->rightChild, p->rightChild, g->rightChild);
}
else
{ //zag-zig型
BinTreeNode<ElemType> *x = unbalancedNode.leftChild->rightChild; //失衡节点的孙节点
BinTreeNode<ElemType> *p = unbalancedNode.leftChild; //失衡节点的子节点
BinTreeNode<ElemType> *g = &unbalancedNode; //失衡节点
//x顶替g的位置
x->parent = g->parent;
if (g->parent != nullptr)
{ //失衡节点有父节点时
if (g->parent->leftChild == g) g->parent->leftChild = x;
else g->parent->rightChild = x;
}
else
{ //失衡节点无父节点时
this->root = x;
}

Connect34(p, x, g, p->leftChild, x->leftChild, x->rightChild, g->rightChild);
}
}
else if (bf < 0)
{
if (CalculateBF(*unbalancedNode.rightChild) <= 0)
{ //zag型
BinTreeNode<ElemType> *x = unbalancedNode.rightChild->rightChild; //失衡节点的孙节点
BinTreeNode<ElemType> *p = unbalancedNode.rightChild; //失衡节点的子节点
BinTreeNode<ElemType> *g = &unbalancedNode; //失衡节点
//p顶替g的位置
p->parent = g->parent;
if (g->parent != nullptr)
{ //失衡节点有父节点时
if (g->parent->leftChild == g) g->parent->leftChild = p;
else g->parent->rightChild = p;
}
else
{ //失衡节点无父节点时
this->root = p;
}

Connect34(g, p, x, g->leftChild, p->leftChild, x->leftChild, x->rightChild);
}
else
{ //zig-zag型
BinTreeNode<ElemType> *x = unbalancedNode.rightChild->leftChild; //失衡节点的孙节点
BinTreeNode<ElemType> *p = unbalancedNode.rightChild; //失衡节点的子节点
BinTreeNode<ElemType> *g = &unbalancedNode; //失衡节点
//x顶替g的位置
x->parent = g->parent;
if (g->parent != nullptr)
{ //失衡节点有父节点时
if (g->parent->leftChild == g) g->parent->leftChild = x;
else g->parent->rightChild = x;
}
else
{ //失衡节点无父节点时
this->root = x;
}

Connect34(g, x, p, g->leftChild, x->leftChild, x->rightChild, p->rightChild);
}
}
}

//函数功能：插入操作（供用户调用）
//函数参数：要插入的节点的数据
//函数返回值：bool类型，返回OK or FALSE
template <class ElemType>
bool AVL<ElemType>::Insert(ElemType data)
{
BinTreeNode<ElemType> *posi = Search(data); //记录待插入节点的位置
if (posi != nullptr && posi->data == data)
{ //当要插入的数据已经存在时
return FALSE;
}

BinTreeNode<ElemType> *node; 
node = new BinTreeNode<ElemType>;

//将待插入的数据包装成节点
node->data = data;
node->height = 1;
node->leftChild = node->rightChild = nullptr;
node->parent = posi;
if (posi != nullptr)
{ //当树不为空时
(data < posi->data ? posi->leftChild : posi->rightChild) = node;
}
else
{ //当树还为空时
this->root = node;
}

UpdateHeight(*node);

BinTreeNode<ElemType> *g; //g为插入节点的爷节点
g = node->parent;

if (g != nullptr)
{
while (g != nullptr&&abs(CalculateBF(*g)) <= 1)
{ //向上查找失衡节点
g = g->parent;
}

if (g != nullptr)
{ //当存在失衡节点时，进行旋转操作
Rotate(*g); //若爷节点的失衡值的绝对值大于1,进行旋转操作
}
}
return OK;
}

//函数功能：删除节点操作（供用户调用）
//函数参数：待删除的数据
//函数返回值：bool类型，OK or FALSE
template <class ElemType>
bool AVL<ElemType>::Delete(ElemType data)
{
BinTreeNode<ElemType> *posi = this->Search(data); //查找待删除的节点

if (posi == nullptr || posi->data != data)
{ //当找不到要删除的节点时，返回FALSE
return FALSE;
}

BinTreeNode<ElemType> *succ; //待删除节点的接替节点，这里用它的前驱结点
BinTreeNode<ElemType> *unbalancedCheckNode; //失衡检查节点 

if (posi->leftChild == nullptr)
{ //当删除节点的左孩子为空时
succ = posi->rightChild;
if (posi->parent == nullptr)
{ //当要删除的节点即为根节点时
this->root = succ; //将树的根节点替换成要删除节点的接替节点
if (succ != nullptr) succ->parent = nullptr; //修改接替节点的父节点
}
else
{ //当要删除的节点不为根节点时
(posi->parent->leftChild == posi ? posi->parent->leftChild : posi->parent->rightChild) = succ; //posi的父节点的孩子替换为succ
if (succ != nullptr) succ->parent = posi->parent; //修改接替节点的父节点
} 
unbalancedCheckNode = posi->parent; //向上检查失衡
delete posi; //删除节点
posi = nullptr; //将节点置空
}
else if (posi->leftChild->rightChild == nullptr)
{ //当删除节点的左孩子的右孩子为空时
succ = posi->leftChild;
if (posi->parent == nullptr)
{ //当要删除的节点即为根节点时
this->root = succ; //将树的根节点替换成要删除节点的接替节点
succ->parent = nullptr; //修改接替节点的父节点
succ->rightChild = posi->rightChild; //接替节点的右孩子变为删除节点的右孩子
if (posi->rightChild != nullptr) posi->rightChild->parent = succ;
}
else
{ //当要删除的节点不为根节点时
(posi->parent->leftChild == posi ? posi->parent->leftChild : posi->parent->rightChild) = succ; //posi的父节点的孩子替换为succ
succ->parent = posi->parent;
succ->rightChild = posi->rightChild; //接替节点的右孩子变为删除节点的右孩子
if (posi->rightChild != nullptr) posi->rightChild->parent = succ;
}
unbalancedCheckNode = succ; //向上检查失衡
delete posi; //删除节点
posi = nullptr; //将节点置空
}
else
{ //当删除结点的左孩子不为空且左孩子的右孩子不为空
succ = posi->leftChild;
while (succ->rightChild != nullptr)
{ //寻找删除节点的前驱结点
succ = succ->rightChild;
}

posi->data = succ->data; //将删除结点的数据用接替结点的数据代替
unbalancedCheckNode = succ->parent;
succ->parent->rightChild = succ->leftChild; //接替节点的左孩子替代接替节点的父节点的右孩子
if (succ->leftChild != nullptr) succ->leftChild->parent = succ->parent; //更新接替节点左孩子的父节点
delete succ; //删除结点
succ = nullptr; //将指针置空
}

UpdateHeight(*unbalancedCheckNode); //更新树高
BinTreeNode<ElemType> *ancestorNode = unbalancedCheckNode; //删除节点的祖先结点
while (ancestorNode != nullptr)
{ //由于删除操作可能回引起失衡传播，所以要一直向上检查是否失衡
if (abs(CalculateBF(*ancestorNode))>1)
{ //当失衡值的绝对值大于1时进行旋转操作
Rotate(*ancestorNode);
}
ancestorNode = ancestorNode->parent;
}

return OK;
}

//函数功能：将平衡二叉树的节点数据打印出来（供用户调用）
//函数参数：无
//函数返回值：void
template <class ElemType>
void AVL<ElemType>::Print()
{
PrintOut(this->root);
}

//函数功能：将平衡二叉树的节点数据打印出来（Private）
//函数参数：开始打印的节点的指针
//函数返回值：void
template <class ElemType>
void AVL<ElemType>::PrintOut(BinTreeNode<ElemType> *beginNode)
{ //采用中序遍历
if (beginNode != nullptr)
{
this->PrintOut(beginNode->leftChild);
std::cout << beginNode->data << "\t";
this->PrintOut(beginNode->rightChild);
}
}