Demo entry 6686607

c

   

Submitted by anonymous on Dec 24, 2017 at 08:50
Language: C. Code size: 5.5 kB.

#include <stdio.h>
#include <stdlib.h>
typedef struct AVL_Node
{
    int data; //数据
    int height;//节点高度
    struct AVL_Node *llink;
    struct AVL_Node *rlink;
}Node;
typedef Node* PNode;
int R(PNode *node);
int L(PNode *node );
void LL(PNode *node);
void RR(PNode *node);
int Height(PNode *node);
int Insert(PNode *node,int x);
int search(PNode node,int x);
void Delete(PNode *node,int x);

int R(PNode *node)
{
    PNode temp = (*node)->rlink;
    if(Height(&(temp->llink)) - Height(&(temp->rlink)) == 1)   //结点的左儿子比右儿子高
        {
           // printf("*\n");
            LL(&((*node)->rlink));
            RR(node);
        }
    else RR(node);
    return 0;
}
int L(PNode *node )
{
    PNode temp = (*node)->llink;
    if(Height(&(temp->llink)) - Height(&(temp->rlink)) == -1)
    {
       // printf("*\n");
        RR(&((*node)->llink));
       // printf("*\n");
        LL(node);
    }
    else LL(node);
    return 0;
}
void LL(PNode *node)
{
    PNode temp =(*node)->llink;
    (*node)->llink = temp->rlink;
    temp->rlink = *node;
    if(Height(&((*node)->llink)) > Height(&((*node)->rlink)))
         (*node)->height = Height(&((*node)->llink)) +1;
    else (*node)->height = Height(&((*node)->rlink)) +1;
    if(Height(&(temp->llink)) > Height(&(temp->rlink)))
         temp->height = Height(&(temp->llink)) +1;
    else temp->height = Height(&(temp->rlink)) +1;
    *node = temp;
}
void RR(PNode *node)
{

    PNode temp = (*node)->rlink;

    (*node)->rlink = temp->llink;
//    printf("!!!\n");
    temp->llink = *node;

    if(Height(&((*node)->llink)) > Height(&((*node)->rlink)))
         (*node)->height = Height(&((*node)->llink)) +1;
    else (*node)->height = Height(&((*node)->rlink)) +1;
    if(Height(&(temp->llink)) > Height(&(temp->rlink)))
         temp->height = Height(&(temp->llink)) +1;
    else temp->height = Height(&(temp->rlink)) +1;
    *node = temp;

}
int Height(PNode* node)
{
//    printf("***\n");
    return (*node)== NULL ? -1 : (*node)->height;
}
int Insert(PNode *node,int x)
{
    if((*node)==NULL)//节点为空插入这里
    {
        (*node) = (PNode)malloc(100*sizeof(Node));
        (*node)->data = x;
        (*node)->llink = NULL;
        (*node)->rlink = NULL;
        (*node)->height = 0;
        return 1;
    }
    else if(x == (*node)->data)//原来存在该节点返回0,递归结束
            return 0;
    else if(x<(*node)->data)//待插入节点的值小于当前的节点
    {
        if(Insert(&((*node)->llink),x)==0)//找寻左子树,返回0则说明该节点原来就存在
            return 0;  //返回0
        else if(Height(&((*node)->llink)) - Height(&((*node)->rlink))==2)//插入成功,说明还向左走了一步,如果失衡,只能为2
            {
//                printf("#1\n");
                L(node); //左边高,再判断是LL型旋转还是LR型旋转
            }
//        else printf("PP\n");
    }
    else if(x>(*node)->data)
    {
            if(Insert(&((*node)->rlink),x)==0)//找寻右子树
            return 0;
            else if(Height(&((*node)->llink)) - Height(&((*node)->rlink))==-2)//能走到这一步,说明还向右走了一步,如果失衡,只能为-2
             {
                 R(node);
//             printf("#2\n");
             }
    }
    if(Height(&((*node)->rlink)) > Height(&((*node)->llink)))
         (*node)->height =Height(&((*node)->rlink)) +1;
    else (*node)->height =Height(&((*node)->llink)) +1;//更新节点高度
//    printf("*\n");
    return 1;//返回1,保证递归继续向下走
    }

int search(PNode node,int x)//查找
{
        //PNode temp;
    while(node!=NULL)
    {
    //  temp = node;
        if(node->data == x)
        {
            if(node->llink!=NULL && node->rlink!=NULL)
                printf("节点数据:%d  高度:%d  左儿子:%d  右儿子%d 因子%d \n",node->data,node->height + 1,node->llink->data,node->rlink->data,Height(&(node->llink)) - Height(&(node->rlink)));
            if(node->llink==NULL && node->rlink!=NULL)
                printf("节点数据:%d  高度:%d  左儿子为空  右儿子%d    因子%d\n",node->data,node->height + 1,node->rlink->data,Height(&(node->llink)) - Height(&(node->rlink)));
            if(node->llink!=NULL && node->rlink==NULL)
                printf("节点数据:%d  高度:%d  左儿子%d  右儿子为空    因子%d\n",node->data,node->height + 1,node->llink->data,Height(&(node->llink)) - Height(&(node->rlink)));
            if(node->llink==NULL && node->rlink==NULL)
                printf("节点数据:%d  高度:%d  左儿子为空  右儿子为空  因子%d\n",node->data,node->height + 1,Height(&(node->llink)) - Height(&(node->rlink)));
            return 1;
        }
        else if(x>node->data)
        {
            node = node->rlink;
        }
        else if(x<node->data)
        {
            node = node->llink;
        }
    }
    return 0;
}
void Inoreder(PNode tree)//中序遍历,打印树
{
    if(tree == NULL)
        return ;
    else
    {
    Inoreder(tree->llink);
    printf("%d  ",tree->data);
    Inoreder(tree->rlink);
    }
}
void Delete(PNode *node,int x)//删除节点
{
if((*node)==NULL)//节点为空,不存在删除节点
        return ;
    else if(x>(*node)->data)
        Delete(&(*node)->rlink,x);//左递归
    else if(x<(*node)->data)
        Delete(&(*node)->llink,x);//右递归
    else if(x == (*node)->data)
    {
        if((*node)->llink == NULL)//没有左孩子
        {
            PNode temp = (*node);
            (*node)=(*node)->rlink;
            free(temp);
        }
        else if((*node)->rlink == NULL)//没有右孩子
        {
            PNode temp = (*node);
            (*node)=(*node)->llink;
            free(temp);
        }
        else
        {
            PNode temp = (*node)->llink;

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).