当前位置: 代码迷 >> 综合 >> AVL树前传
  详细解决方案

AVL树前传

热度:55   发布时间:2024-01-17 21:42:00.0

实现插入和记录平衡因子,不调整。

难点在尾递归,可能修改节点平衡因子

#include<iostream>
using namespace std;
template <class T> class AvlTree;
template <class T>
class AvlNode
{ T data;  //关键码AvlNode *leftChild;AvlNode *rightChild;int balance;//平衡因子public:AvlNode():leftChild(NULL),rightChild(NULL),balance(0){};AvlNode(const T& e,AvlNode<T> *lt=NULL):data(e),leftChild(lt),rightChild(lt),balance(0){};//默认缺省参数值int getBalance() const	{ return balance;}AvlNode<T>* getLeftChild() const{return leftChild;}AvlNode<T>* getrightChild() const{return rightChild;}T getData() const{return data;}bool Insert(T x);bool Insert(AvlNode<T> *&rt,T x,bool taller);friend class AvlTree<T>;
};
template <class T>
class AvlTree
{ AvlNode<T> *root;bool Insert(AvlNode<T> *& rt,T x,bool &taller);bool Remove(AvlNode<T> * &rt,T x ,bool &shorter);void RotateLeft(AvlNode<T> * &node);void RotateRight(AvlNode<T> *&node);void RightBalanceAfterInsert(AvlNode<T> * &sRoot,bool &taller);void LeftBalanceAfterDeltete(AvlNode<T> *&sRoot,bool &shorter);public:AvlTree():root(NULL)  {}AvlNode<T>* getRoot() const{return root;}bool Insert(T x){ bool taller=false;return Insert(root,x,taller);}bool Remove(T x){ bool shorter=false;return Remove(root,x,shorter);}void DisplayTree(AvlNode<T> *t,int layer) const;
};
//关于 Insert,如果在本节点插入后,由平衡状态0变成+1或-1,
// 将对上一级的平衡产生影响,对应是+1或-1.
// 另一种情况是本级插入后由不平衡状态+1、-1变成平衡0,
//对上一级的平衡状态不产生影响。
template<typename T>
void AvlTree<T>::RotateLeft(AvlNode<T> * & node)
{ //这个左旋好复杂??//原来的node节点的地址被上一级指向,不能更换,只能替换数据if((node==NULL)||(node->rightChild==NULL)) return ;AvlNode<T> * tmpNode=new AvlNode<T>(node->data);if(tmpNode==NULL) return;tmpNode->lefChild=node->leftChild;//新增的节点将替代node向Left下沉node->leftChild=tmpNode;tmpNode->rightChild=node->rightChild->leftChild;AvlNode<T> *toDelete=node->rightChild;node->data=toDelete->data;//node节点将被原来右子节点替代node->rightChild=toDelete->rightChild;delete toDelete;//删除原来的右子结点
}
template<typename T>
void AvlTree<T>::RotateRight(AvlNode<T> *& node)
{  if((node==NULL) || (node->leftChild==NULL)) return;AvlNode<T> *tmpNode=new AvlNode<T>(node->data);if( tmpNode==NULL) return;//新节点将替代node向Right下沉tmpNode->rightChild=node->rightChild;node->rightChild=tmpNode;tmpNode->leftChild=node->leftChild->rightChild;//原来的Node Left子节点转移(上升)到NodeAvlNode<T> *toDelete=node->leftChild;node->data=toDelete->data;node->leftChild=toDelete->leftChild;}template<typename T>
bool  AvlTree<T>:: Insert(AvlNode<T> *& rt,T x,bool &taller)
{//递归插入,成功则返回True,若插入使树长高,taller为true.bool success=false;if( rt==NULL ) //边界条件,插入节点{ rt=new AvlNode<T>(x);taller=true;return true;}else{ if(x<=rt->data){  if( success=Insert(rt->leftChild,x,taller) ){/* switch(rt->balance)//插入左边成功{case 1: if(taller) {rt->balance=0;taller=false;}break;case 0:if(taller) rt->balance=-1;break;case -1:if(taller) rt->balance=-2;//此处要调整break;  }*/if(taller) rt->balance--;if(rt->balance>=0) taller=false;}}else if(success=Insert(rt->rightChild,x,taller)){ /*   switch(rt->balance)//右插成功{  case 1:if(taller) rt->balance=2;//此处要调整break;case 0:if(taller) rt->balance=1;break;case -1:if(taller) {rt->balance=0; taller=false;}break;} */if(taller)  rt->balance++;if(rt->balance<=0)taller=false;}  }return success;}template<typename T>
void AvlTree<T>::DisplayTree(AvlNode<T> *t,int layer) const
//深度优先,输出信息。
{  cout<<endl;if(t==NULL) return;cout<<"level---"<<layer<<endl;cout<<"       data:"<<t->data<<"     balance:"<<t->balance<<endl;DisplayTree(t->leftChild,layer+1);DisplayTree(t->rightChild,layer+1);
}
int main()
{  AvlTree<int> a;for(int i=1;i<=10;i++){	int b;cin>>b;a.Insert(b);}AvlNode<int>* rt;rt=a.getRoot();a.DisplayTree(rt,1);return 0;
}

  相关解决方案