如何创建AVL(How to create AVL)

我输入几个数字（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); }

I enter several numbers(2,1,4,5,9,3,6,7),after I enter the number '3', there something wrong,the function can not return correctly.

#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; }

I think there is something wrong in my main function, I think I shouldn't write

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

those code in mian function, I try to add a 'Init' function, but it doesn't work. It always said "'T' is being used without initialized"

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); }

最满意答案

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

我注意到你的Insert函数返回一个AVLTree ，但是当main调用它时它不会对返回值做任何事情。

（这不是代码中唯一不对的问题，但它是一个很好的起点。）

When your insertion makes a new root node, this fact is not propagated back to main in any way. The value of T inside the Insert function changes, but main has its own variable called T that isn't changed, and that's the one that you then use to print out the tree.

I notice that your Insert function returns an AVLTree, but when main calls it it doesn't do anything with the return value.

(This is not the only thing that's amiss in your code, but it would be a good place to start.)

更多推荐