【无标题】

 

/**
    平衡二叉树（AVL树）满足每个结点的左右子树高度之差绝对值不会超过1，
    以使得每次访问一棵树的时间复杂度不会超过O(logn)；
*/

《算法笔记》：

主要操作：

BinTree NewNode(ElementType x); //新建一个节点
int getHeight(BinTree root); //获得结点的高度
int getBalanceFacter(BinTree root); //获得结点的平衡因子
void updateHeight(BinTree root); //更新结点的高度
void Searech(BinTree BST,ElementType x); //搜索一棵AVL树，查找数据域为x的结点，并打印信息
void L(BinTree &BST); //将结点进行左旋；
void R(BinTree &BST); //将结点进行右旋；
void Insert(BinTree &BST,ElementType x); //在一棵AVL树中插入一个值为x的结点
BinTree Create(ElementType *a,int n);  //建立一棵AVL树
void PreTraver(BinTree BST); //前序遍历一棵二叉树；
void LayTraver(BinTree BST); //层次遍历一棵二叉树；

/**
    平衡二叉树（AVL树）满足每个结点的左右子树高度之差绝对值不会超过1，
    以使得每次访问一棵树的时间复杂度不会超过O(logn)；
*/


#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>

using namespace std;

typedef int ElementType;
typedef struct TNode* BinTree;
struct TNode
{
    ElementType data;
    int height;
    BinTree lchild,rchild;
};
typedef BinTree Position;

BinTree NewNode(ElementType x); //新建一个节点
int getHeight(BinTree root); //获得结点的高度
int getBalanceFacter(BinTree root); //获得结点的平衡因子
void updateHeight(BinTree root); //更新结点的高度
void Searech(BinTree BST,ElementType x); //搜索一棵AVL树，查找数据域为x的结点，并打印信息
void L(BinTree &BST); //将结点进行左旋；
void R(BinTree &BST); //将结点进行右旋；
void Insert(BinTree &BST,ElementType x); //在一棵AVL树中插入一个值为x的结点
BinTree Create(ElementType *a,int n);  //建立一棵AVL树
void PreTraver(BinTree BST); //前序遍历一棵二叉树；
void LayTraver(BinTree BST); //层次遍历一棵二叉树；

int main()
{
    int n;
    printf("输入树的结点的个数：\n");
    scanf("%d",&n);
    int a[n];
    printf("输入 %d 个结点的数据域:\n",n);
    for(int i=0;i<n;++i)
        scanf("%d",&a[i]);
    BinTree BST=Create(a,n);
    printf("树的结点的前序遍历:\n");
    PreTraver(BST);
    cout << endl;
    printf("树的结点的层次遍历:\n");
    LayTraver(BST);
    cout << endl;
    int sear;
    printf("输入你要查找的结点的数据域:\n");
    scanf("%d",&sear);
    printf("你要查找的数据域 %d 的结果是:\n",sear);
    Searech(BST,sear);
    printf("再输入 %d 个要插入的结点的数据域:\n",n);
    for(int i=0;i<n;++i)
    {
        int val;
        scanf("%d",&val);
        Insert(BST,val);
    }
    printf("树的结点的前序遍历:\n");
    PreTraver(BST);
    cout << endl;
    printf("树的结点的层次遍历:\n");
    LayTraver(BST);
    cout << endl;
    return 0;
}

BinTree NewNode(ElementType x) //新建一个节点
{
    BinTree BST=new TNode;
    BST->data=x;
    BST->height=1;
    BST->lchild=BST->rchild = NULL;
    return BST;
}

int getHeight(BinTree root) //获得结点的高度
{
    if(root==NULL)
        return 0;
    else
        return root->height;
}

int getBalanceFacter(BinTree root) //获得结点的平衡因子
{
    return getHeight(root->lchild) - getHeight(root->rchild);
}

void updateHeight(BinTree root) //更新结点的高度
{
    root->height=max(getHeight(root->lchild),getHeight(root->rchild))+1;
}

void Searech(BinTree BST,ElementType x) //搜索一棵AVL树，查找数据域为x的结点，并打印信息
{
    while(BST)
    {
        if(x<BST->data)
            BST=BST->lchild;
        else if(x>BST->data)
            BST=BST->rchild;
        else
            break;
    }
    if(!BST)
        printf("search fail!\n");
    else
        printf("%d\n",BST->data);
}

void L(BinTree &BST) //将结点进行左旋；
{
    BinTree temp=BST->rchild;
    BST->rchild=temp->lchild;
    temp->lchild=BST;
    updateHeight(BST); //别忘了更新结点的高度
    updateHeight(temp);
    BST=temp;
}

void R(BinTree &BST) //将结点进行右旋；
{
    BinTree temp=BST->lchild;
    BST->lchild=temp->rchild;
    temp->rchild=BST;
    updateHeight(BST); //别忘了更新结点的高度
    updateHeight(temp);
    BST=temp;
}

void Insert(BinTree &BST,ElementType x) //在一棵AVL树中插入一个值为x的结点
{
    if(BST==NULL)
    {
        BST=NewNode(x);
        return ;
    }

    if(x > BST->data)
    {
        Insert(BST->rchild,x);
        updateHeight(BST);
        if(getBalanceFacter(BST)==-2)
        {
            if(getBalanceFacter(BST->rchild)==-1) //RR型
                L(BST);
            else if(getBalanceFacter(BST->rchild)==1) //RL型
            {
                R(BST->rchild);
                L(BST);
            }
        }
    }
    else
    {
        Insert(BST->lchild,x);
        updateHeight(BST);
        if(getBalanceFacter(BST)==2)
        {
            if(getBalanceFacter(BST->lchild)==1) //LL型
                R(BST);
            else if(getBalanceFacter(BST->lchild)==-1) //LR型
            {
                L(BST->lchild);
                R(BST);
            }
        }
    }
}

BinTree Create(ElementType *a,int n)  //建立一棵AVL树
{
    BinTree BST=NULL;
    for(int i=0;i<n;++i)
        Insert(BST,a[i]);
    return BST;
}

void PreTraver(BinTree BST) //前序遍历一棵二叉树；
{
    if(BST)
    {
        printf("%d ",BST->data);
        PreTraver(BST->lchild);
        PreTraver(BST->rchild);
    }
}

void LayTraver(BinTree BST)
{
    queue<BinTree> q;
    q.push(BST);
    while(!q.empty())
    {
        BST=q.front();
        q.pop();
        printf("%d ",BST->data);
        if(BST->lchild)
            q.push(BST->lchild);
        if(BST->rchild)
            q.push(BST->rchild);
    }
}

2）浙大代码：

/**
    浙大代码：
*/


//#include <iostream>
//#include <cstdlib>
//
//using namespace std;
//
//typedef int ElementType;
//typedef struct AVLNode *Position;
//typedef Position AVLTree; /* AVL树类型 */
//struct AVLNode{
//    ElementType Data; /* 结点数据 */
//    AVLTree Left;     /* 指向左子树 */
//    AVLTree Right;    /* 指向右子树 */
//    int Height;       /* 树高 */
//};
//
//int Max ( int a, int b )
//{
//    return a > b ? a : b;
//}
//
//int GetHeight(AVLTree root)
//{
//    if(root==NULL)
//        return 0;
//    else
//        return root->Height;
//}
//
//AVLTree SingleLeftRotation ( AVLTree A )
//{ /* 注意：A必须有一个左子结点B */
//  /* 将A与B做左单旋，更新A与B的高度，返回新的根结点B */
//
//    AVLTree B = A->Left;
//    A->Left = B->Right;
//    B->Right = A;
//    A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1;
//    B->Height = Max( GetHeight(B->Left), A->Height ) + 1;
//
//    return B;
//}
//
//AVLTree SingleRightRotation ( AVLTree A )
//{ /* 注意：A必须有一个左子结点B */
//  /* 将A与B做左单旋，更新A与B的高度，返回新的根结点B */
//
//    AVLTree B = A->Right;
//    A->Right = B->Left;
//    B->Left = A;
//    A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1;
//    B->Height = Max( GetHeight(B->Right), A->Height ) + 1;
//
//    return B;
//}
//
//AVLTree DoubleLeftRightRotation ( AVLTree A )
//{ /* 注意：A必须有一个左子结点B，且B必须有一个右子结点C */
//  /* 将A、B与C做两次单旋，返回新的根结点C */
//
//    /* 将B与C做右单旋，C被返回 */
//    A->Left = SingleRightRotation(A->Left);
//    /* 将A与C做左单旋，C被返回 */
//    return SingleLeftRotation(A);
//}
//
///*************************************/
///* 对称的右单旋与右-左双旋请自己实现 */
//
//
//
//AVLTree DoubleRightLeftRotation ( AVLTree A )
//{ /* 注意：A必须有一个左子结点B，且B必须有一个右子结点C */
//  /* 将A、B与C做两次单旋，返回新的根结点C */
//
//    /* 将B与C做右单旋，C被返回 */
//    A->Right = SingleLeftRotation(A->Right);
//    /* 将A与C做左单旋，C被返回 */
//    return SingleRightRotation(A);
//}
///*************************************/
//
//AVLTree Insert( AVLTree T, ElementType X )
//{ /* 将X插入AVL树T中，并且返回调整后的AVL树 */
//    if ( !T ) { /* 若插入空树，则新建包含一个结点的树 */
//        T = (AVLTree)malloc(sizeof(struct AVLNode));
//        T->Data = X;
//        T->Height = 0;
//        T->Left = T->Right = NULL;
//    } /* if (插入空树) 结束 */
//
//    else if ( X < T->Data ) {
//        /* 插入T的左子树 */
//        T->Left = Insert( T->Left, X);
//        /* 如果需要左旋 */
//        if ( GetHeight(T->Left)-GetHeight(T->Right) == 2 )
//            if ( X < T->Left->Data )
//               T = SingleLeftRotation(T);      /* 左单旋 */
//            else
//               T = DoubleLeftRightRotation(T); /* 左-右双旋 */
//    } /* else if (插入左子树) 结束 */
//
//    else if ( X > T->Data ) {
//        /* 插入T的右子树 */
//        T->Right = Insert( T->Right, X );
//        /* 如果需要右旋 */
//        if ( GetHeight(T->Left)-GetHeight(T->Right) == -2 )
//            if ( X > T->Right->Data )
//               T = SingleRightRotation(T);     /* 右单旋 */
//            else
//               T = DoubleRightLeftRotation(T); /* 右-左双旋 */
//    } /* else if (插入右子树) 结束 */
//
//    /* else X == T->Data，无须插入 */
//
//    /* 别忘了更新树高 */
//    T->Height = Max( GetHeight(T->Left), GetHeight(T->Right) ) + 1;
//
//    return T;
//}
//
//void PreorderTraversal(AVLTree AVL)
//{
//    if(AVL)
//    {
//        cout << AVL->Data << ' ';
//        PreorderTraversal(AVL->Left);
//        PreorderTraversal(AVL->Right);
//    }
//}
//
//int main()
//{
//    int n;
//    cin >> n;
//    AVLTree AVL=NULL;
//    for(int i=0;i<n;++i)
//    {
//        int val;
//        scanf("%d",&val);
//        AVL=Insert(AVL,val);
//    }
//    PreorderTraversal(AVL);
//    cout << "\nHello World\n";
//    return 0;
//}