搜尋二叉樹和平衡二叉樹

搜尋二叉樹及操作

#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;
}
           

右單旋

左單旋

左右雙旋

右左雙旋