搜索二叉树和平衡二叉树

搜索二叉树及操作

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode
{
    ElementType Data;
    BinTree Left;
    BinTree Right;

};
Position Find(ElementType X, BinTree BST) //尾递归都可以用循环实现
{
    if(!BST) return NULL;
    if(X>BST->Data) return Find(X,BST->Right);
    else if(X>BST->Data) return Find(X,BST->Left);
    else return BST;

}

Position IterFind(ElementType X, BinTree BST)
{
    while(BST){
        if(X>BST->Data)
            BST=BST->Right;
        else if(X<BST->Data)
            BST=BST->Left;
        else
            return BST;
    }
    return NULL;
}

Position FindMin(BinTree BST)
{
    if(!BST) return NULL;
    else if(!BST->Left)
        return BST; //找到最左叶节点并返回
    else
        return FindMin(BST->Left);
}

Position FinMax(BinTree BST)
{
    if(BST)
        while(BST->Right) BST=BST->Right;
    return BST;
}

BinTree Insert(ElementType X,BinTree BST)
{
    if(!BST){
        BST=malloc(sizeof(struct TNode));
        BST->Data=X;
        BST->Left=BST->Right=NULL;
    }else{
        if(X<BST->Data)
            BST->Left=Insert(X,BST->Left);
        else if(X>BST->Data)
            BST->Right=Insert(X,BST->Right);
     }   /*else X已经存在就什么都不做 */
    return BST;
}

BinTree Delete(ElementType X,BinTree BST)
{
    Position Tmp;
    if(!BST) printf("要删除的元素未找到");
    else if(X<BST->Data)
        BST->Left=Delete(X,BST->Left); //左子树递归删除
    else if(X>BST->Data)
        BST->Right=Delete(X,BST->Right); //右子树递归删除
    else
        if(BST->Left&&BST->Right){ //被删除的节点有左右两个儿子
            Tmp=FindMin(BST->Right); //在右子树中找到最小的元素填充删除节点
            BST->Data=Tmp->Data;
            BST->Right=Delete(BST->Data,BST->Right);//在右子树中删除最小元素
        }else{ //被删除节点有一个或无子结点
            Tmp=BST;
            if(!BST->Left) //有右孩子或无子结点
                BST=BST->Right;
            else if(!BST->Right) //有左孩子或无子结点
                BST=BST->Left;
            free(Tmp);
        }
    return BST;
}
           

平衡二叉树 

typedef struct AVLNode *Position;
typedef Position AVLTree;
typedef int ElementType;
struct AVLNode
{
    ElementType Data;
    AVLTree Left;
    AVLTree Right;
    int Height;
};

int Max(int a ,int b)
{
    return a>b?a:b;
}

int GetHeight(AVLTree A)
{
    int HL,HR,MAXH;
    if(A)
    {
        HL=GetHeight(A->Left);
        HR=GetHeight(A->Right);
        MAXH=(HL>HR)?HL:HR;
        return MAXH+1;
    }
    else return -1; //空树高度为-1，只有一个根节点高度为0
}

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 )
{

    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->Left),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->Right = SingleLeftRotation(A->Left);
    /* 将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;
    }

    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(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 X == T->Data，无须插入 */
    /* 别忘了更新树高 */
    T->Height = Max( GetHeight(T->Left), GetHeight(T->Right) ) + 1;
    return T;
}
           

右单旋

左单旋

左右双旋

右左双旋