binary tree.c

利用随机函数产生100个(不大于100且各不相同的)随机整数

#include<stdio.h>
#include<malloc.h>
#include<math.h>
#define TRUE 1 
#define FALSE 0
#define OK 1
#define ERROR 0 
#define FORMAT "%d  "   /*输出格式与ElemType对应 */

typedef int Status ;         /*函数状态类型 */
typedef int ElemType ;       /*二叉树结点数据类型为整型*/

/*模块一：随机函数模块*/
void RandomHundred(int data[100])
/*产生100个不大于100且各不相同的整数，存放在data[100]中*/
{
    int j,temp,subscript;
    /*temp用于交换，subscript为随机下标*/
    for(j=1;j<101;++j)data[j-1]=j;
    /*先把1－100按顺序放入数组中*/
    for(j=100;j>0;--j)
    {
        subscript=rand()%j ;
        /*产生随机下标*/
        temp=data[j-1];
        data[j-1]=data[subscript];
        data[subscript]=temp ;
        /*交换data[j-1]与data[subscript] */
    }

}

/*模块二：建立二叉树*/
/*平衡二叉排序树的类型定义*/

typedef struct BSTNode 
{
    ElemType data ;
    int bf ;
    /*结点的平衡因子*/
    struct BSTNode*lchild,*rchild ;
    /* 左、右孩子指针 */
}
BSTNode,*BSTree ;
#define EQ(a,b)((a)==(b))
#define LT(a,b)((a)<(b))

#define Lh +1  /* 左高 */
#define Eh 0   /* 等高 */
#define Rh -1  /* 右高 */
void R_Rotate(BSTree*p)
{
    /* 对以*p为根的二叉排序树作右旋处理，处理之后p指向新的树根结点，即旋转 */
    /* 处理之前的左子树的根结点。算法9.9 */
    BSTree lc ;
    lc=(*p)->lchild ;
    /* lc指向p的左子树根结点 */
    (*p)->lchild=lc->rchild ;
    /* lc的右子树挂接为p的左子树 */
    lc->rchild=*p ;
    *p=lc ;
    /* p指向新的根结点 */
}

void L_Rotate(BSTree*p)
{
    /* 对以*p为根的二叉排序树作左旋处理，处理之后p指向新的树根结点，即旋转 */
    /* 处理之前的右子树的根结点。算法9.10 */
    BSTree rc ;
    rc=(*p)->rchild ;
    /* rc指向p的右子树根结点 */
    (*p)->rchild=rc->lchild ;
    /* rc的左子树挂接为p的右子树 */
    rc->lchild=*p ;
    *p=rc ;
    /* p指向新的根结点 */
}


void LeftBalance(BSTree*T)
{
    /* 对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时， */
    /* 指针T指向新的根结点。算法9.12 */
    BSTree lc,rd ;
    lc=(*T)->lchild ;
    /* lc指向*T的左子树根结点 */
    switch(lc->bf)
    {
        /* 检查*T的左子树的平衡度，并作相应平衡处理 */
        case Lh :
        /* 新结点插入在*T的左孩子的左子树上，要作单右旋处理 */
        (*T)->bf=lc->bf=Eh ;
        R_Rotate(T);
        break ;
        case Rh :
        /* 新结点插入在*T的左孩子的右子树上，要作双旋处理 */
        rd=lc->rchild ;
        /* rd指向*T的左孩子的右子树根 */
        switch(rd->bf)
        {
            /* 修改*T及其左孩子的平衡因子 */
            case Lh :
            (*T)->bf=Rh ;
            lc->bf=Eh ;
            break ;
            case Eh :
            (*T)->bf=lc->bf=Eh ;
            break ;
            case Rh :
            (*T)->bf=Eh;
            lc->bf=Lh;
            break ;
        }
        rd->bf=Eh ;
        L_Rotate(&(*T)->lchild);
        /* 对*T的左子树作左旋平衡处理 */
        R_Rotate(T);
        /* 对*T作右旋平衡处理 */
    }
}

void RightBalance(BSTree*T)
{
    /* 对以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时， */
    /* 指针T指向新的根结点 */
    BSTree rc,rd ;
    rc=(*T)->rchild ;
    /* rc指向*T的右子树根结点 */
    switch(rc->bf)
    {
        /* 检查*T的右子树的平衡度，并作相应平衡处理 */
        case Rh :
        /* 新结点插入在*T的右孩子的右子树上，要作单左旋处理 */
        (*T)->bf=rc->bf=Eh ;
        L_Rotate(T);
        break ;
        case Lh :
        /* 新结点插入在*T的右孩子的左子树上，要作双旋处理 */
        rd=rc->lchild ;
        /* rd指向*T的右孩子的左子树根 */
        switch(rd->bf)
        {
            /* 修改*T及其右孩子的平衡因子 */
            case Rh :
            (*T)->bf=Lh ;
            rc->bf=Eh ;
            break ;
            case Eh :
            (*T)->bf=rc->bf=Eh ;
            break ;
            case Lh :
            (*T)->bf=Eh ;
            rc->bf=Rh ;
            break ;
        }
        rd->bf=Eh ;
        R_Rotate(&(*T)->rchild);
        /* 对*T的右子树作右旋平衡处理 */
        L_Rotate(T);
        /* 对*T作左旋平衡处理 */
    }
}

Status InsertAVL(BSTree*T,ElemType e,Status*taller)
{
    /* 若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个 */
    /* 数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树 */
    /* 失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。算法9.11 */
    if(!*T)
    {
        /* 插入新结点，树"长高"，置taller为TRUE */
        *T=(BSTree)malloc(sizeof(BSTNode));
        (*T)->data=e ;
        (*T)->lchild=(*T)->rchild=NULL ;
        (*T)->bf=Eh ;
        *taller=TRUE ;
    }
    else 
    {
        if(EQ(e,(*T)->data))
        {
            /* 树中已存在和e有相同关键字的结点则不再插入 */
            *taller=FALSE ;
            return FALSE ;
        }
        if(LT(e,(*T)->data))
        {
            /* 应继续在*T的左子树中进行搜索 */
            /* 未插入 */
            if(!InsertAVL(&(*T)->lchild,e,taller))return FALSE ;
            /*  已插入到*T的左子树中且左子树"长高" */
            /* 检查*T的平衡度 */
            if(*taller)switch((*T)->bf)
            {
                case Lh :
                /* 原本左子树比右子树高，需要作左平衡处理 */
                LeftBalance(T);
                *taller=FALSE ;
                break ;
                case Eh:
                /* 原本左、右子树等高，现因左子树增高而使树增高 */
                (*T)->bf=Lh ;
                *taller=TRUE ;
                break ;
                case Rh :
                (*T)->bf=Eh;
                /* 原本右子树比左子树高，现左、右子树等高 */
                *taller=FALSE ;
            }
        }
        else 
        {
            /* 应继续在*T的右子树中进行搜索 */
            /* 未插入 */
            if(!InsertAVL(&(*T)->rchild,e,taller))return FALSE ;
            /* 已插入到T的右子树且右子树"长高" */
            /* 检查T的平衡度 */
            if(*taller)switch((*T)->bf)
            {
                case Lh :
                (*T)->bf=Eh ;
                /* 原本左子树比右子树高，现左、右子树等高 */
                *taller=FALSE ;
                break ;
                case Eh :
                /* 原本左、右子树等高，现因右子树增高而使树增高 */
                (*T)->bf=Rh ;
                *taller=TRUE ;
                break ;
                case Rh :
                /* 原本右子树比左子树高，需要作右平衡处理 */
                RightBalance(T);
                *taller=FALSE ;
            }
        }
    }
    return TRUE ;
}


/*模块四：栈的操作:供非递归先序遍历用*/
typedef BSTree SElemType;    /*定义栈的元素类型为二叉树结点指针BSTree */
/*栈的顺序存储表示*/

 #define STACK_INIT_SIZE 100 /* 存储空间初始分配量 */
 #define STACKINCREMENT 10 /* 存储空间分配增量 */
 typedef struct SqStack
 {
   SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
   SElemType *top; /* 栈顶指针 */
   int stacksize; /* 当前已分配的存储空间，以元素为单位 */
 }SqStack; /* 顺序栈 */

 Status InitStack(SqStack *S)
 { /* 构造一个空栈S */
   (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
   if(!(*S).base)
     exit(OVERFLOW); /* 存储分配失败 */
   (*S).top=(*S).base;
   (*S).stacksize=STACK_INIT_SIZE;
   return OK;