c - 如何创建AVL

Question

我输入了几个数字(2,1,4,5,9,3,6,7)，当我输入数字“3”后，出现问题，函数无法正确返回。

#include <stdio.h>
#include <stdlib.h>
typedef struct AVLNode
{
    int data;
    int height;
    struct AVLNode *LChild;
    struct AVLNode *RChild;
}*AVLTree;
typedef struct AVLNode *Position;

static int Height(Position T)
{
    if (T == NULL)
        return -1;
    else
        return T->height;
}

static Position SingleLeft(Position k2)
{
    Position k1;
    k1 = k2->LChild;
    k2->LChild = k1->RChild;
    k1->RChild = k2;

    k2->height = max(Height(k2->LChild), Height(k2->RChild)) + 1;
    k1->height = max(Height(k1->LChild), Height(k1->RChild)) + 1;

    return k1;
}

static Position SingleRight(Position k1)
{
    Position k2;
    k2 = k1->RChild;
    k1->RChild = k2->LChild;
    k2->LChild = k1;

    k1->height = max(Height(k1->LChild), Height(k1->RChild)) + 1;
    k2->height = max(Height(k2->LChild), Height(k2->RChild)) + 1;

    return k2;
}

static Position DoubleLeft(Position k3)
{
    k3->LChild = SingleRight(k3->LChild);

    return SingleLeft(k3);
}

static Position DoubleRight(Position k1)
{
    k1->RChild = SingleLeft(k1->RChild);

    return SingleRight(k1);
}

void PrePrint(AVLTree T)
{
    if (T != NULL)
    {
        printf("%d  ", T->data);
        PrePrint(T->LChild);
        PrePrint(T->RChild);
    }
}

AVLTree Insert(int x, AVLTree T)
{
    if (T == NULL)
    {
        T = (AVLTree)malloc(sizeof(struct AVLNode));
        T->data = x;
        T->LChild = T->RChild = NULL;
    }
    else if (x < T->data)
    {
        T->LChild = Insert(x, T->LChild);
        if (Height(T->LChild) - Height(T->RChild) == 2)
        {
            if (x<T->LChild->data)
                T = SingleLeft(T);
            else
                T = DoubleLeft(T);
        }
    }
    else if (x > T->data)
    {
        T->RChild = Insert(x, T->RChild);
        if (Height(T->RChild) - Height(T->LChild) == 2)
        {
            if (x>T->RChild->data)
                T = SingleRight(T);
            else
                T = DoubleRight(T);
        }
    }

    T->height = max(Height(T->LChild), Height(T->RChild)) + 1;

    return T;
}

我认为我的主要功能有问题，我认为我不应该写

 T=(AVLTree)malloc(sizeof(struct AVLNode));
    T->LChild = T->RChild = NULL;

在mian函数中的那些代码中，我尝试添加“Init”函数，但它不起作用。它总是说“'T'正在使用而没有初始化”

int main()
{
    AVLTree T;
    T=(AVLTree)malloc(sizeof(struct AVLNode));I think there is wrong
    T->LChild = T->RChild = NULL;
    int x;
    printf("please enter the data(0 to quit):");
    scanf("%d", &x);
    T->data = x;
    while (x != 0)
    {
        Insert(x, T);
        printf("enter a number(0 to quit):");
        scanf("%d", &x);
    } 
    PrePrint(T);
}

Answer 1

当您的插入创建一个新的根节点时，这个事实不会以任何方式传播回main。 Insert 函数中 T 的值发生变化，但 main 有自己的名为 T 的变量，该变量并没有改变更改后，这就是您用来打印树的那个。

我注意到您的 Insert 函数返回一个 AVLTree，但是当 main 调用它时，它不会对返回值执行任何操作。

(这不是代码中唯一的错误，但它是一个很好的起点。)