建立平衡二叉树出错，不知道错在哪

Question

感觉逻辑没出错，可是运行不出来

抱歉，没有c币了。。。。。希望还是能有人帮忙解答下，万分感谢

#include <iostream>
using namespace std;
#include <stdlib.h>

typedef int Elemtype;

typedef struct AVLTree{
    int height;          //节点高度
    Elemtype data;
    struct AVLTree *LTree;
    struct AVLTree *RTree;
}; 

void init(AVLTree *tree){   //初始化一个AVL树，为它开辟空间
    tree=(AVLTree *)malloc(sizeof(AVLTree));
    tree->height=0;
    tree->LTree=NULL;
    tree->RTree=NULL;
}

int max(int x,int y){    //用于比较两个节点的高度
    return x>y?x:y;
}

AVLTree *RRotate(AVLTree *root){//当不平衡时顺时针旋转（右旋）
    if(root==NULL)
        return NULL;
    AVLTree *left=root->LTree;
    root->LTree=left->RTree;
    left->RTree=root;

    root->height=max(root->LTree->height,root->RTree->height)+1;
    left->height=max(left->LTree->height,left->RTree->height)+1;
    return left;
}

AVLTree *LRotate(AVLTree *root){//当不平衡时逆时针旋转（左旋）
    if(root==NULL)
        return NULL;
    AVLTree *right=root->RTree;
    root->RTree=right->LTree;
    right->LTree=root;

    root->height=max(root->LTree->height,root->RTree->height)+1;
    right->height=max(right->LTree->height,right->RTree->height)+1;
    return right;
}

AVLTree *LRRotate(AVLTree *root){//先逆时针旋转再顺时针旋转
    root->LTree=LRotate(root->LTree);
    return RRotate(root);
}

AVLTree *RLRotate(AVLTree *root){//先顺时针旋转再逆时针旋转
    root->RTree=RRotate(root->RTree);
    return LRotate(root);
}

AVLTree *Add(AVLTree *tree,Elemtype data){//向树中添加一个节点
    if(tree==NULL){
        tree->data=data;
        tree->height=1;
        tree->LTree=NULL;
        tree->RTree=NULL;
    }
    else if(data>tree->data){//当插入右边时
        tree->RTree=Add(tree->RTree,data);
        if(abs(tree->LTree->height-tree->RTree->height)==2){
            if(tree->LTree==NULL){//因为一定插在树的右边所以一共就两种情况 
                tree=LRotate(tree); 
            }else if(tree->RTree==NULL){
                tree=LRRotate(tree);
            }
    }
    else if(data<tree->data){//当插入左边时
        tree->LTree=Add(tree->LTree,data);
        if(abs(tree->LTree->height-tree->RTree->height)==2){
            if(tree->RTree==NULL){//因为一定插在树的左边所以一共就两种情况 
                tree=RRotate(tree); 
            }else if(tree->LTree==NULL){
                tree=RLRotate(tree);
            }
        }
    }
    else if(data==tree->data)
        return tree;
    tree->height=max(tree->LTree->height,tree->RTree->height)+1;
    return tree;
}

void Create(AVLTree *tree,Elemtype *data,int len){//利用数组创建树
    for(int i=0;i<len;i++)
        tree=Add(tree,data[i]);
}

void PreOrder(AVLTree *tree){//前序遍历
    if(tree==NULL)
        return ;
    cout<<tree->data<<"  ";
    PreOrder(tree->LTree);
    PreOrder(tree->RTree);
}

int main(){
    AVLTree tree;
    Elemtype data[]={3,2,1,4,5,6,8,7,10,9};
    int len=sizeof(data)/sizeof(data[0]);
    init(&tree);
    Create(&tree,data,len);
    PreOrder(&tree);
    return 0;
} 

Answer 1

我没有全看 我就看到你的root 的tree 初始化申请了个空间 ？确定不是初始化直接root=NULL么？你仔细看看 你是不是add第一个就有问题了。我以前写平衡二叉树的算法的，里面用的是数组的如果想要更近似你的的代码。可以看文章里面联动的链接的评论区。和你的是一样指针方式。https://blog.csdn.net/u014646950/article/details/47622789