| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4196 人关注过本帖, 1 人收藏
标题:avl树的新算法,欢迎测试并指出不足
只看楼主 加入收藏
marlow
Rank: 6Rank: 6
等 级:侠之大者
威 望:2
帖 子:125
专家分:419
注 册:2016-7-18
结帖率:75%
收藏(1)
已结贴  问题点数:100 回复次数:21 
avl树的新算法,欢迎测试并指出不足
程序代码:
#include "avltree.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define FALSE 0
#define TRUE  1


struct element{
    char key[15];
};

struct treeNode{
    treePointer leftChild;
    element data;
    short int bf;
    treePointer rightChild;
};

     typedef struct treeNode *treePointer;
       
    void avlInsert(treePointer *parent, element x, int *unbalancedp);/*插入结点函数*/
    void leftRotation(treePointer *parent, int *unbalancedp);    /* 左旋函数*/
    void rightRotation(treePointer *parent, int *unbalancedp);    /* 右旋函数*/
    void preprintree(treePointer ptr);  /* 前序打印二叉树 */
    void inprintree(treePointer ptr);  /* 中序打印二叉树 */
    void avlDelete(treePointer *parent, element x, int *balanced); /* 删除结点函数*/
    void leftMaxNode(treePointer *parent, treePointer *maxNode, int *balanced); /* 查找左子树最大元*/

int main(void)
{
    treePointer rootp = NULL;
    int unbalanced = FALSE;
    element mydata;
    int i;
   
    for(i = 1; i < 13; i++){
        printf("请输入月份名称%d:\n", i);
        scanf("%s",mydata.key);
        avlInsert(&rootp, mydata, &unbalanced);
    }
    preprintree(rootp);
    printf("\n");
    inprintree(rootp);
    for(i = 1; i < 2; i++){
        printf("\n请输入需删除的月份名称%d:\n", i);
        scanf("%s",mydata.key);
        avlDelete(&rootp, mydata, &unbalanced);
    }
    preprintree(rootp);
    printf("\n");
    inprintree(rootp);
   
}

void avlInsert(treePointer *parent, element x, int *unbalancedp)
{
    if(!*parent){    /* insert element into null tree */
        *unbalancedp = TRUE;
        *parent = (treePointer)malloc(sizeof(struct treeNode));
        (*parent)->leftChild = (*parent)->rightChild = NULL;
        (*parent)->bf = 0;
        (*parent)->data = x;
    }else if(strcmp(x.key, (*parent)->data.key) < 0){
        avlInsert(&(*parent)->leftChild, x, unbalancedp);
        if(*unbalancedp)        /* left branch has grown higher */
        switch((*parent)->bf){
            case -1:    (*parent)->bf = 0;    *unbalancedp = FALSE; break;
            case  0:    (*parent)->bf = 1;    break;
            case  1:    leftRotation(parent, unbalancedp);
        }
    }else if(strcmp(x.key, (*parent)->data.key) > 0){
        avlInsert(&(*parent)->rightChild, x, unbalancedp);
        if(*unbalancedp)        /* right branch has grown higher */
        switch((*parent)->bf){
            case  1:    (*parent)->bf = 0;    *unbalancedp = FALSE; break;
            case  0:    (*parent)->bf = -1;    break;
            case -1:    rightRotation(parent, unbalancedp);
        }
    }else{
        *unbalancedp = FALSE;
        printf("The key is already in the tree!\n");
    }
}

void leftRotation(treePointer *parent, int *unbalancedp)
{
    treePointer grandChild, child;
    child = (*parent)->leftChild;
    if(child->bf == 1){        /* LL rotation */
        (*parent)->leftChild = child->rightChild;
        child->rightChild = *parent;
        (*parent)->bf = 0;
        (*parent) = child;
    }else{                    /* LR rotation */
        grandChild = child->rightChild;
        child->rightChild = grandChild->leftChild;
        grandChild->leftChild = child;
        (*parent)->leftChild = grandChild->rightChild;
        grandChild->rightChild = *parent;
        switch(grandChild->bf){
            case  1:    (*parent)->bf = -1; child->bf = 0; break;
            case  0:    (*parent)->bf = child->bf= 0; break;
            case -1:    (*parent)->bf =  0; child->bf = 1;
        }
        *parent = grandChild;
    }
    (*parent)->bf = 0;
    *unbalancedp = FALSE;
}

void rightRotation(treePointer *parent, int *unbalancedp)
{
    treePointer grandChild, child;
    child = (*parent)->rightChild;
    if(child->bf == -1){        /* RR rotation */
        (*parent)->rightChild = child->leftChild;
        child->leftChild = *parent;
        (*parent)->bf = 0;
        (*parent) = child;
    }else{                    /* RL rotation */
        grandChild = child->leftChild;
        child->leftChild = grandChild->rightChild;
        grandChild->rightChild = child;
        (*parent)->rightChild = grandChild->leftChild;
        grandChild->leftChild = *parent;
        switch(grandChild->bf){
            case  1:    (*parent)->bf = 0; child->bf = -1; break;
            case  0:    (*parent)->bf = child->bf= 0; break;
            case -1:    (*parent)->bf =  1; child->bf = 0;
        }
        *parent = grandChild;
    }
    (*parent)->bf = 0;
    *unbalancedp = FALSE;
}

void preprintree(treePointer ptr)
{
    if(ptr == NULL)  /* 为空树则返回 */
        return ;
    printf("  %s ", ptr->data.key);
    if(ptr->leftChild != NULL)
        preprintree(ptr->leftChild);
    if(ptr->rightChild != NULL)
        preprintree(ptr->rightChild);
}
void inprintree(treePointer ptr)
{
    if(ptr == NULL)  /* 为空树则返回 */
        return ;
    if(ptr->leftChild != NULL)
        inprintree(ptr->leftChild);
    printf("  %s ", ptr->data.key);
    if(ptr->rightChild != NULL)
        inprintree(ptr->rightChild);
}

void avlDelete(treePointer *parent, element x, int *unbalanced)
{
    treePointer temp;
    treePointer* delp;

    if(!*parent){
        *unbalanced = FALSE;
        printf("未查找到要删除的节点!\n");
        return 0;
    }
    if(strcmp(x.key, (*parent)->data.key) == 0){
        if(((*parent)->leftChild == NULL) && ((*parent)->rightChild == NULL))
        {    //情况1:无孩子
            free(*parent);
            *parent = NULL;
             *unbalanced = TRUE;
        }else if(((*parent)->leftChild == NULL) && ((*parent)->rightChild != NULL))
        {    //情况2:无左孩子
            temp = *parent;
            *parent = (*parent)->rightChild;
            free(temp);
             *unbalanced = TRUE;
        }else if(((*parent)->leftChild != NULL) && ((*parent)->rightChild == NULL))
        {    //情况3:无右孩子
            temp = *parent;
            *parent = (*parent)->leftChild;
            free(temp);
             *unbalanced = TRUE;
        }else{    //情况4:有俩孩子
            if((*parent)->leftChild->rightChild == NULL){//左孩无右孙
                temp = *parent;
                *parent = (*parent)->leftChild;
                free(temp);
                 *unbalanced = TRUE;
            }else{    //左孩有右孙
                leftMaxNode(parent, &(*parent)->leftChild, unbalanced);
                if(*unbalanced)
                    if((*parent)->leftChild->bf == -1){
                        (*parent)->leftChild->bf = 0;
                    }else if((*parent)->leftChild->bf == 0){
                        (*parent)->leftChild->bf = 1;
                    }else if((*parent)->leftChild->bf == 1){
                        leftRotation(&(*parent)->leftChild, unbalanced);
                    }       
            }
        }
    }else if(strcmp(x.key, (*parent)->data.key) < 0){
        avlDelete(&(*parent)->leftChild, x, unbalanced);
        if(*unbalanced)
            if((*parent)->bf == 1){
                (*parent)->bf = 0;
            }else if((*parent)->bf == 0){
                (*parent)->bf = -1;
            }else if((*parent)->bf == -1){
                rightRotation(parent, unbalanced);
            }
    }else if(strcmp(x.key, (*parent)->data.key) > 0){
        avlDelete(&(*parent)->rightChild, x, unbalanced);
        if(*unbalanced)
            if((*parent)->bf == -1){
                (*parent)->bf = 0;
            }else if((*parent)->bf == 0){
                (*parent)->bf = 1;
            }else if((*parent)->bf == 1){
                leftRotation(parent, unbalanced);
            }
    }
}

void leftMaxNode(treePointer *parent, treePointer *maxNode, int *unbalanced)
{            /* 与左子树最大元交换,并删除结点 */
    if((*maxNode)->rightChild->rightChild == NULL){
        treePointer temp;
        struct treeNode tempn;
       
        temp = *parent;
        tempn = *(*maxNode)->rightChild;
        *parent = (*maxNode)->rightChild;
        (*parent)->leftChild = temp->leftChild;
        (*parent)->rightChild = temp->rightChild;
        (*parent)->bf = temp->bf;
        (*maxNode)->rightChild = tempn.leftChild;
        free(temp);
        *unbalanced = TRUE;
    }else{
        leftMaxNode(parent, &(*maxNode)->rightChild, unbalanced);
        if(*unbalanced)
            if((*maxNode)->bf == -1){
                (*maxNode)->bf = 0;
            }else if((*maxNode)->bf == 0){
                (*maxNode)->bf = 1;
            }else if((*maxNode)->bf == 1){
                leftRotation(maxNode, unbalanced);
        }       
    }
}
搜索更多相关主题的帖子: key int void parent NULL 
2017-07-30 00:17
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:40 
先顶一下~最近没啥弄编程了~现阶段看来我就顶多支持一下了~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-07-30 07:57
marlow
Rank: 6Rank: 6
等 级:侠之大者
威 望:2
帖 子:125
专家分:419
注 册:2016-7-18
收藏
得分:0 
回复 2楼 九转星河
有空正好帮我测试一下

一切都在学习、尝试、摸索中
2017-07-30 08:58
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 3楼 marlow
你还真是不客气呢~不过你这个学习态度让我腾出空来试一下也是值得的~~

当然~你那个avltree.h到底在哪里呢~
删了无论.c和.cpp都不能正常通过编译~
那就先看你怎么解释咯~

@renkejun1942

或者有空可以来看一下吧~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-07-30 12:03
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 4楼 九转星河
哇~看来我的编程能力还是有点生疏了~改改就能通过编译了~或许是楼主的编译环境问题~我到时再看看具体情况~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-07-30 12:13
marlow
Rank: 6Rank: 6
等 级:侠之大者
威 望:2
帖 子:125
专家分:419
注 册:2016-7-18
收藏
得分:0 
回复 5楼 九转星河
多谢版主啦没放头文件,直接在主函数前声明了

一切都在学习、尝试、摸索中
2017-07-30 12:43
杨阳11111
Rank: 2
等 级:论坛游民
威 望:1
帖 子:20
专家分:59
注 册:2017-5-4
收藏
得分:5 
路过一下,学了一个学期的c 感觉还是不熟练,看来要继续拿起来看啦。
2017-07-30 13:16
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:40 
虽然还未理解,但是高度修正好赞的样子。

在插入函数和删除函数中的 strcmp(x.key, (*parent)->data.key)
这个每个函数可以只写一次,使用一个变量保存strcmp的返回值就可以了,可以省掉一次函数调用。

[此贴子已经被作者于2017-7-30 18:47编辑过]


09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-07-30 18:45
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:0 
程序代码:
void avlDelete(treePointer *parent, element x, int *unbalanced)
{
    treePointer temp;
    treePointer* delp;

    if(!*parent){
        *unbalanced = FALSE;
        printf("未查找到要删除的节点!\n");
        return 0;//删掉这个0,avlDelete函数没有返回值,因此这里会有一个错误信息。
    }

09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-07-30 18:49
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:0 
if(*unbalanced)//删除函数中有多个这样的if语句缺少花括号,
{//每个这样的if语句都有一个警告信息。
            if((*parent)->bf == -1){//只有一条语句的if花括号可以不写,花括号多了,追踪起来很麻烦。
                (*parent)->bf = 0;
            }else if((*parent)->bf == 0){
                (*parent)->bf = 1;
            }else if((*parent)->bf == 1){
                leftRotation(parent, unbalanced);
            }
}

[此贴子已经被作者于2017-7-30 18:52编辑过]


09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-07-30 18:50
快速回复:avl树的新算法,欢迎测试并指出不足
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.028802 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved