#pragma once
//AVL 树实现 二叉平衡搜素树
//性质就是树的高度差不超过2 保证查找效率为O(log2n) 且左子树 < 根节点 < 右子树
//难点为插入跟删除操作 需要保持树的平衡
//代码有问题，先备份，有时间再来修改
#include "stdio.h"
#include "Queue.h"
namespace SF
{
template<class T>
struct AVLNode
{
T data;
AVLNode<T> *left;
AVLNode<T> *right;
AVLNode()
{
this->left = this->right = nullptr;
}
};
template<class T>
class AVLTree
{
public:
AVLTree();
~ AVLTree();
void Insert(const T& val)
{
if(this->count==0)
{
root->data = val;
}
else
{
InsertNode(root, val);
root = TreeRebalance(root);
}
this->count++;
};
void Delete(const T& val)
{
DeleteNode(root, val);
root = TreeRebalance(root);
};
void Size() { this->count; }
void PreOrder() { PreOrderTraverse(root); };
void InOrder() { InOrderTraverse(root); };
void PostOrder() { PostOrderTraverse(root); };
void SequenceOrder() ; //层序遍历
void Release() { ReleaseTree(root); };
private:
int count;
AVLNode<T> *root;
void PreOrderTraverse(AVLNode<T> *node);
void InOrderTraverse(AVLNode<T> *node);
void PostOrderTraverse(AVLNode<T> *node);
void ReleaseTree(AVLNode<T> *node);
AVLNode<T> *InsertNode(AVLNode<T> *node, const T& val);
AVLNode<T> *DeleteNode(AVLNode<T> *node, const T& val);
AVLNode<T>* RotateLeft(AVLNode<T> *node);
AVLNode<T>* RotateRight(AVLNode <T> *node);
//找最小节点
AVLNode<T> *FindMin(AVLNode<T> *node);
//树重新平衡
AVLNode<T> *TreeRebalance(AVLNode<T> *node);
int max(int a, int b)
{
return a > b ? a : b;
};
int GetTreeHeight(const AVLNode<T>* node);
//计算平衡因子 平衡因子不能大于2 任一节点 左右子树高度差
int TreeBalanceFector(const AVLNode<T>* node);
};
//层序遍历
template<class T>
void AVLTree<T>::SequenceOrder()
{
AVLNode<T> *temp;
Queue<AVLNode<T>> queue;
queue.Enqueue(*root);
while (queue.IsEmtpy())
{
temp = &(queue.Dequeue()->data);
printf("%i\n", temp->data);
if (temp->left) queue.Enqueue(*temp->left);
if (temp->right) queue.Enqueue(*temp->right);
}
}
template<class T>
void AVLTree<T>::PreOrderTraverse(AVLNode<T> *node)
{
if (node)
{
printf("%i\n", node->data);
PreOrderTraverse(node->left);
PreOrderTraverse(node->right);
}
}
template<class T>
void AVLTree<T>::InOrderTraverse(AVLNode<T> *node)
{
if (node)
{
InOrderTraverse(node->left);
printf("%i\n", node->data);
InOrderTraverse(node->right);
}
}
template<class T>
void AVLTree<T>::PostOrderTraverse(AVLNode<T> *node)
{
if (node)
{
PostOrderTraverse(node->left);
PostOrderTraverse(node->right);
printf("%i\n", node->data);
}
}
template<class T>
void AVLTree<T>::ReleaseTree(AVLNode<T> *node)
{
if (node)
{
ReleaseTree(node->left);
ReleaseTree(node->right);
delete node;
}
}
template<class T>
AVLNode<T>* AVLTree<T>::InsertNode(AVLNode<T> *node,const T& val)
{
if (node)
{
if (val > node->data)
{
node->right = InsertNode(node->right, val);
}
else
{
node->left = InsertNode(node->left, val);
}
}
else
{
node = new AVLNode<T>();
node->data = val;
node->left = node->right = nullptr;
}
return node;
}
template<class T>
AVLNode<T>* AVLTree<T>::DeleteNode(AVLNode<T> *node,const T& val)
{
if (!node)
{
printf("要删除的元素不存在")；
}
else if (val > node->data)
{
node->right = DeleteNode(node->right, val);
}
else if (val < node->data)
{
node->left = DeleteNode(node->left, val);
}
else //找到需要删除的元素
{
AVLNode<T> *tmp;
//需要做区分
if (node->left && node->right) //左右儿子都在 可以从左子树中找一个最大的来，或者是从右子树中找一个最小的来
{
tmp = FindMin(node->right);
node->data = tmp->data;
node->right = DeleteNode(node->right,node->data); //换位置，然后去删掉右子树中最小的节点
}
else
{
tmp = node; //保存当前node指向地址
if (!node->left) //只有右子树
{
node = node->right; //修改指针
}
if (!node->right) //只有左子树
{
node = node->left;
}
delete tmp;
}
}
return node;
}
template<class T>
AVLNode<T> *AVLTree<T>::FindMin(AVLNode<T> *node)
{
AVLNode<T> *tmp = node;
while (tmp->left)
{
tmp = tmp->left;
}
return tmp;
}
template<class T>
int AVLTree<T>::TreeBalanceFector(const AVLNode<T>* node)
{
if (!node) return 0;
return GetTreeHeight(node->left) - GetTreeHeight(node->right); //结果为正 表示为左插 结果为负 表示为右插
}
template<class T>
int AVLTree<T>::GetTreeHeight(const AVLNode<T>* node)
{
if (!node) return 0;
return max(GetTreeHeight(node->left), GetTreeHeight(node->right)) + 1; //先递归到底，然后出一层就加1 就很妙
}
template<class T>
AVLNode<T>* AVLTree<T>::RotateRight(AVLNode <T> *node)
{
AVLNode<T> *tmp = node->left;
node->left = tmp->right;
tmp->right = node;
return tmp;
}
template<class T>
AVLNode<T>* AVLTree<T>:: RotateLeft(AVLNode<T> *node)
{
AVLNode<T> *tmp = node->right;
node->right = tmp->left;
tmp->left = node;
return tmp;
}
template<class T>
AVLNode<T>* AVLTree<T>::TreeRebalance(AVLNode<T> *node)
{
int fector = TreeBalanceFector(node);
if (fector > 1 && TreeBalanceFector(root->left) > 0) //LL旋转
{
return RotateRight(node);
}
if (fector > 1 && TreeBalanceFector(node->left) <= 0) //LR旋转
{
node->left = RotateLeft(node->left);
return RotateRight(node);
}
if (fector < -1 && TreeBalanceFector(node->right) <= 0) //RR旋转
{
return RotateLeft(node);
}
if (fector < -1 && TreeBalanceFector(node->right) > 0) //RL旋转
{
root->right = RotateRight(node->right);
return RotateLeft(node);
}
return node;
}
template<class T>
AVLTree<T>:: AVLTree()
{
root = new AVLNode<T>();
}
template<class T>
AVLTree<T>::~ AVLTree()
{
Release();
}
}
网友评论