dosavl.cpp

这是一个数据结构的小程序

#include<iostream>
#include <cstdlib>
#include <ctime>
#include<windows.h>
using namespace std;


/**
 *节点类
 */

template<typename Type>
class AvlNode
{
public:
    Type Data;
    AvlNode *LChild;//左儿子
    AvlNode *RChild;//右儿子
    int BalanceFactor;
    AvlNode()
    {
	LChild = NULL;
	RChild = NULL;
	BalanceFactor = 0;
    }
    AvlNode(const Type &theData, AvlNode *lc=NULL, AvlNode *rc=NULL, int bf=0)
	:Data(theData),LChild(lc), RChild(rc),BalanceFactor(bf){}
};

template<typename Type>
class AvlTree
{
public:
    typedef Type Data;//数据
    typedef AvlNode<Type> Node;//节点
    typedef Node* pNode;//节点指针

    enum {LEFT,RIGHT};

    AvlTree():head(new Node){}
    ~AvlTree()
    {
	CleanAll();
    }

    int Insert(const Type &it); //插入操作 成功1 失败0
    int Delete(const Type &it);//删除操作 成功1 失败0
    int GetMax(Type &it);//最大值it 成功1 失败0
    int GetMin(Type &it);
    void InOrder();//中序遍历
    
    void CleanAll(pNode head);
    void CleanAll();
/**
 * 内函数用于转置何删除是修改必要的BanlanceFactor
 * 还有转置何删除是指针的变化
 */

 private:
    //ll
    inline void LChangeBalanceI(pNode theselect);//转置后BalanceFactor的修改
    inline void LChangeBalanceD(pNode theselect);//删除时BalanceFactor的修改
    inline pNode LRotate(pNode theselect);
    //lr
    inline void LRChangeBalanceI(pNode theselect);
    inline void LRChangeBalanceD(pNode theselect);
    inline pNode LRRotate(pNode theselect);
    //rl
    inline void RLChangeBalanceI(pNode theselect);
    inline void RLChangeBalanceD(pNode theselect);
    inline pNode RLRotate(pNode theselect);
    //rr
    inline void RChangeBalanceI(pNode theselect);
    inline void RChangeBalanceD(pNode theselect);
    inline pNode RRotate(pNode theselect);
   

    inline void ChangeChild(pNode parent, pNode oldchild, pNode newchild);//parent由指向oldchild 指向newchild

    pNode head;

};



template<typename Type>
int AvlTree<Type>::Insert(const Type &it)
{
    pNode Parent = head;//指向hand的父节点
    pNode Hand = Parent->LChild;//欲处理的节点的指针
	//转置都是在最后一个不平衡点出发生的，记录最后一个不平衡点及其父节点
    pNode LastNot = NULL, ParentLastNot = NULL;
    
    //找插入位置
    while(Hand)
    {
	if(Hand->Data == it) 
	    return 0;
	if(Hand->BalanceFactor)
	{
	    LastNot = Hand;
	    ParentLastNot = Parent;
	}
	Parent = Hand;
	if(it < Hand->Data)
	    Hand = Hand -> LChild;
	else
	    Hand = Hand -> RChild;
    }

    pNode NewNode = new Node(it);

    if( Parent == head)
    {
	head->LChild = NewNode;
	return 1;
    }
    else if(it < Parent->Data)
	Parent -> LChild = NewNode;
    else
	Parent -> RChild = NewNode;


    if(!LastNot)
	Hand = head->LChild;
    else
	Hand = LastNot;

// 插入
    while(Hand != NewNode)
    {
	if(it < Hand->Data)
	{
	     ++Hand->BalanceFactor;
             Hand = Hand -> LChild;
	}
	else
	{
	    --Hand->BalanceFactor;
	    Hand = Hand -> RChild;
	}
    }
    
  
//修改插入后节点的balanceFactor

    if(!LastNot || (LastNot->BalanceFactor < 2&&LastNot -> BalanceFactor > -2))
        return 1;
    else
    {
	if(it < LastNot -> Data)
	{
	    if(it < LastNot->LChild -> Data)
	    {
		LChangeBalanceI(LastNot);
		ChangeChild(ParentLastNot, LastNot, LRotate(LastNot));
	    }
	    else
	    {
		LRChangeBalanceI(LastNot);
		ChangeChild(ParentLastNot, LastNot, LRRotate(LastNot));
	    }
	}
	else
	{
	    if(it > LastNot->RChild->Data)
	    {
		RChangeBalanceI(LastNot);
		ChangeChild(ParentLastNot, LastNot, RRotate(LastNot));
	    }
	    else
	    {
		RLChangeBalanceI(LastNot);
		ChangeChild(ParentLastNot, LastNot, RLRotate(LastNot));
	    }
	}
    }
    return 1;
}

template<typename Type> 
int AvlTree<Type>::Delete(const Type& it)
{
     pNode SearchHistory[64];
     int       SearchDirection[64];
     int       CurrIdx;
     
     pNode Curr = head->LChild;
     SearchHistory[0] = head;
     SearchDirection[0] = 0;
     CurrIdx = 1;
     
     while (Curr && Curr->Data != it)
     {
         SearchHistory[CurrIdx] = Curr;
         it < Curr->Data ?
             (Curr = Curr->LChild, SearchDirection[CurrIdx] = LEFT): 
             (Curr = Curr->RChild, SearchDirection[CurrIdx] = RIGHT);
         ++CurrIdx;
     }
     
     if (!Curr) return 0;
     
     pNode ToBeDeleted = Curr;
     if (Curr->LChild && Curr->RChild)
     {
         pNode  CurrT = Curr->LChild;
         SearchHistory[CurrIdx] = Curr;
         SearchDirection[CurrIdx++] = LEFT;
         while (CurrT->RChild)
         {
             SearchHistory[CurrIdx] = CurrT;
             SearchDirection[CurrIdx++] = RIGHT;
             CurrT = CurrT->RChild;
         }
         Curr->Data = CurrT->Data;
         ToBeDeleted = CurrT;
     }
     
     
     {
         pNode Temp = 
             ToBeDeleted->LChild ?
                 ToBeDeleted->LChild :
                     (ToBeDeleted->RChild  ? ToBeDeleted->RChild : NULL);
         delete ToBeDeleted;
         --CurrIdx;//   指向欲删除节点的父节点
         SearchDirection[CurrIdx] == RIGHT ?
             SearchHistory[CurrIdx]->RChild = Temp:
             SearchHistory[CurrIdx]->LChild = Temp;
     }

     for (int HeightChanged = 1; HeightChanged && CurrIdx; --CurrIdx)
     {   
         pNode ToBeAdjusted = SearchHistory[CurrIdx];
         pNode ParentToBeAdjusted = SearchHistory[CurrIdx-1];
         int       ChangedChild = SearchDirection[CurrIdx];
         if (ToBeAdjusted->BalanceFactor == 0)
         {
             ToBeAdjusted->BalanceFactor = ChangedChild == LEFT? -1 : 1;
             HeightChanged = 0;
         }
         else if (ToBeAdjusted->BalanceFactor == -1)
         {
             if (ChangedChild == RIGHT)
             {
                 ToBeAdjusted->BalanceFactor = 0;
                 HeightChanged = 1;
             }
             else
             {
                 switch (ToBeAdjusted->RChild->BalanceFactor)
                 {
                 case 0:
                     HeightChanged = 0;
                     RChangeBalanceD(ToBeAdjusted);
                     ChangeChild(ParentToBeAdjusted, ToBeAdjusted, RRotate(ToBeAdjusted));
                     break;
                 case -1:
                     HeightChanged = 1;
                     RChangeBalanceD(ToBeAdjusted);
                     ChangeChild(ParentToBeAdjusted, ToBeAdjusted, RRotate(ToBeAdjusted));
                     break;
                 case 1:
                     HeightChanged = 1;
                     RLChangeBalanceD(ToBeAdjusted);
                     ChangeChild(ParentToBeAdjusted, ToBeAdjusted, RLRotate(ToBeAdjusted));
                 }
             }
         }
         else
         {
             if (ChangedChild == LEFT)
             {
                 ToBeAdjusted->BalanceFactor = 0;
                 HeightChanged = 1;
             }
             else
             {
                 switch (ToBeAdjusted->LChild->BalanceFactor)
                 {
                 case 0:
                     HeightChanged = 0;
                     LChangeBalanceD(ToBeAdjusted);
                     ChangeChild(ParentToBeAdjusted, ToBeAdjusted, LRotate(ToBeAdjusted));
                     break;
                 case 1:
                     HeightChanged = 1;
                     LChangeBalanceD(ToBeAdjusted);
                     ChangeChild(ParentToBeAdjusted, ToBeAdjusted, LRotate(ToBeAdjusted));
                     break;
                 case -1:
                     HeightChanged = 1;
                     LRChangeBalanceD(ToBeAdjusted);
                     ChangeChild(ParentToBeAdjusted, ToBeAdjusted, LRRotate(ToBeAdjusted));
                 }
             }
         }       
     }
     
     return 1;
 }


template<typename Type>
void AvlTree<Type>::InOrder()
 {
     pNode Curr = head->LChild;
     
     while (true)
     {
         if (Curr == NULL) break;
         
         pNode q = Curr->LChild;
         if (q == NULL)
         {
             cout<<Curr->Data<<' ';
             Curr = Curr->RChild;
         }
         else
         {
             while (q->RChild != NULL && q->RChild != Curr)