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

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

抱歉,没有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;
} 
c++

1个回答

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

u014646950
Datrilla 回复qq_41235711: 头必须为空啊,你这里没有数据的时候头数据和地址有问题吧
10 个月之前 回复
u014646950
Datrilla 回复qq_41235711: 你给头指针没有给值,后面怎么比较?除非是哨兵节点
大约一年之前 回复
qq_41235711
qq_41235711 我是这样想的:不在main中初始化空间,直接调用函数让这个树在整个程序内有效。一开始给个头指针,然后左右子树为空。第一个好像没问题,应该是后面的问题
大约一年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

1
在查找方面二叉排序树效率与顺序查找的效率谁高(这里一般二叉排序树 不是指平衡二叉树)
2
为什么根据前序输入可以构造二叉树, 但是知道前序遍历不能确定二叉树? 二者有什么区别?
4
C语言求二叉树结点个数?
3
C++二叉树应用问题求助
1
这个平衡二叉树的平衡因子是怎么算的呢
1
数据结构java实验四验证教材中树结构的基本操作,设计实现指定操作的算法,并做算法分析。 以下各题二叉树的存储结构是二叉链表表示,方法声明如下: 二叉树的二叉链表结点类:
1
以二叉链表建立二叉树链式存储结构,实现前序遍历、求叶子结点的个数计算、中序遍历、后序遍历、求深度。
1
关于C++二叉树遍历的问题
1
为什么建立空二叉树后T=NULL后指针还有结构?
0
c++二叉树应用实例判断两个二叉树是否相似
4
二叉树非递归前序遍历
1
编程二叉树求根结点到所有结点的路径长度
1
二叉树中先序递归输入数据?
1
二叉树深度算法查错求助
0
二叉树的创建问题:为什么我写的程序删掉一句printf语句就执行不了了??求大佬解答
0
先序建立二叉树中的查找双亲操作
3
求助二叉树一道难题,怎么进行后序遍历输入,要求C语言
0
关于二叉树动物问答数据,如何使用文件来构造出二叉树?
1
创建及遍历线索二叉树,出了一些小问题
2
求二叉树宽度 大佬帮忙看看我的代码哪里是错在哪里