为啥这个AVL树输出不正确？

Question

调试后感觉是getheight那里有问题？好像每次进入都给height赋值为-1

#include <stdio.h>
#include <stdlib.h>

struct AVLNode;
typedef struct AVLNode* AVLT;
typedef struct AVLNode* AVLPosition;
typedef int ElementType;

int GetHeight(AVLPosition P);
int Max0(int a, int b);
AVLT LeftRotation(AVLT T);
AVLT RightRotation(AVLT T);
AVLT LeftRightRotation(AVLT T);
AVLT RightLeftRotation(AVLT T);
AVLT AVLInsert(AVLT T, ElementType X);
void PrintAVL(AVLT T);

struct AVLNode {
    ElementType Data;
    int height;
    AVLPosition Left;
    AVLPosition Right;
};

#include "AVL.h"

int GetHeight(AVLPosition P) {
    if (P == NULL)
        return -1;
    else
        return P->height;
}
int Max0(int a, int b) {
    return a > b ? a : b;
}
AVLT LeftRotation(AVLT T) {
    AVLPosition B = T->Left;
    T->Left = B->Right;
    B->Right = T;

    T->height = Max0(GetHeight(T->Left), GetHeight(T->Right) + 1);
    B->height = Max0(GetHeight(B->Left), T->height) + 1;
    return B;
}
AVLT RightRotation(AVLT T) {
    AVLPosition B = T->Right;
    T->Right = B->Left;
    B->Left = T;

    T->height = Max0(GetHeight(T->Left), GetHeight(T->Right)) + 1;
    B->height = Max0(GetHeight(B->Right), T->height) + 1;
    return B;
}
AVLT LeftRightRotation(AVLT T) {
    AVLPosition B = T->Left;
    B = RightRotation(B);
    return LeftRotation(T);
}
AVLT RightLeftRotation(AVLT T) {
    AVLPosition B = T->Right;
    B = LeftRotation(B);
    return RightRotation(T);
}
AVLT AVLInsert(AVLT T, ElementType X) {
    if (!T)
    {
        T = (AVLT)malloc(sizeof(struct AVLNode));
        T->Left = T->Right = NULL;
        T->Data = X;
        T->height = 0;
    }
    else if (X < T->Data)
    {
        T->Left = AVLInsert(T->Left, X);
        if ((T->Left->height - T->Right->height) == 2)
        {
            if (X < T->Left->Data)
                T = LeftRotation(T);
            else
                T = LeftRightRotation(T);
        }
    }
    else if (X > T->Data)
    {
        T->Right = AVLInsert(T->Right, X);
        if (GetHeight(T->Right) - GetHeight(T->Left) == 2)
        {
            if (X > T->Right->Data)
                T = RightRotation(T);
            else
                T = RightLeftRotation(T);
        }
    }
    else    //X = T->Data
        ;
    T->height = Max0(GetHeight(T->Left), GetHeight(T->Right)) + 1;  //从叶子（已由旋转函数进行更新）到根部，必须更新每个节点的height
    return T;
}
void PrintAVL(AVLT T) {
    if (!T)
        return;
    else
    {
        printf("%d\n", T->Data);
        PrintAVL(T->Left);
        PrintAVL(T->Right);
    }
}

#include "AVL.h"

int main() {
    AVLT T = malloc(sizeof(struct AVLNode));
    T->Data = 7;
    T->Left = T->Right = NULL;
    AVLInsert(T, 8);
    AVLInsert(T, 9);
    PrintAVL(T);
    return 0;
}

Answer 1

如果你要叶子结点高度为1的话，就把GetHeight函数return -1；改成 return 0；，否则不用

int GetHeight(AVLPosition P) {
    if (P == NULL)
        return 0;
    else
        return P->height;
}

主函数修改

int main() {
    AVLT T = NULL;
    T = AVLInsert(T, 7);
    T = AVLInsert(T, 8);
    T = AVLInsert(T, 9);
    PrintAVL(T);
    return 0;
}

望采纳