#include <stdlib.h>

template<typename T>

class CAVLTree;

template<typename T>

class CAVLTreeNode

{

public:

    CAVLTreeNode(const T& item,CAVLTreeNode<T>* lptr = NULL,CAVLTreeNode<T>* rptr = NULL,int balfac=0):data(item),left(lptr),right(rptr),balanceFactor(balfac)

    {

    }

    CAVLTreeNode<T>* Left(void)const

    {

        return left;

    }

    CAVLTreeNode<T>* Right(void)const

    {

        return right;

    }

    int GetBalanceFactor()const

    {

        return this->balanceFactor;

    }

    friend class CAVLTree<T>;

public:

    T data;//数据

private:

    CAVLTreeNode<T>* left;//左子树

    CAVLTreeNode<T>* right;//右子树

    int balanceFactor;//平衡因子

    CAVLTreeNode<T>* & Left(void)

    {

        return left;

    }

    CAVLTreeNode<T>* & Right(void)

    {

        return right;

    }

};

const int LEFTHEAVY = -1;

const int BALANCE = 0;

const int RIGHTHEAVY = 1;

template<typename T>

class CAVLTree

{

public:

    CAVLTree(void);

    CAVLTree(const CAVLTree<T>& tree);

    CAVLTree& operator = (const CAVLTree& rhs);

    void Insert(const T& item);

    void ClearTree();//清空树

    bool Contains(const T& item);//是否包含数据

    CAVLTreeNode<T>* FindNode(const T& item,CAVLTreeNode<T>* &parent)const;//寻找节点

    CAVLTreeNode<T>* FindMin()const;//找最小值

    CAVLTreeNode<T>* FindMax()const;//找最大值

    void PrintTree();//前序遍历树(非递归)

    virtual ~CAVLTree(void);

protected:

    CAVLTreeNode<T>* GetAVLTreeNode(const T& item,CAVLTreeNode<T> *lptr=NULL,CAVLTreeNode<T> *rptr=NULL);

    CAVLTreeNode<T>* CopyTree(CAVLTreeNode<T>* t);//拷贝树

    void FreeTreeNode(CAVLTreeNode<T>* p);//释放树节点

    void DeleteTree(CAVLTreeNode<T>* t);//删除树

    //旋转

    void SingleRotateLeft(CAVLTreeNode<T> * &p);

    void SingleRotateRight(CAVLTreeNode<T> *&p);

    void DoubleRotateLeft(CAVLTreeNode<T> *&p);

    void DoubleRotateRight(CAVLTreeNode<T> *&p);

    void UpdateLeftTree(CAVLTreeNode<T>* &tree,int &reviseBalanceFactor);

    void UpdateRightTree(CAVLTreeNode<T>* &tree,int &reviseBalanceFactor);

    void AVLInsert(CAVLTreeNode<T> * &tree,CAVLTreeNode<T> *newnode,int &reviseBalanceFactor);

private:

    CAVLTreeNode<T> *root;//平衡二叉树树根

    int size;//树节点个数

};

复制代码

 

平衡二叉树实现代码

测试代码

复制代码

#include "BinSTree.cpp"

#include <iostream>

using namespace std;

CAVLTree<int>* MakeSampleTree()

{//示例AVL树

    CAVLTree<int> *tree1 = new CAVLTree<int>();

    int a = 5;

    tree1->Insert(a);

    tree1->Insert(30);

    tree1->Insert(65);

    tree1->Insert(25);

    tree1->Insert(35);

    tree1->Insert(50);

    tree1->Insert(10);

    tree1->Insert(28);

    tree1->Insert(26);

    tree1->Insert(33);

    return tree1;

}

int main(int argc, char* argv[])

{

    CAVLTree<int> *tree1 = MakeSampleTree();

    tree1->PrintTree();

    cout<<tree1->Contains(40)<<endl;

    CAVLTreeNode<int> *p = tree1->FindMin();

    cout<<p->data<<endl;

    system("pause");

    return 0;

}

复制代码