在二叉树中的 Level Order Traversal 中获取运行时错误

Question

出现运行时错误，找不到我哪里错了

我认为存在一些与内存相关的问题但无法追踪它

#include<stdio.h>
#include<stdlib.h>
struct node{
    int data;
    struct node* leftchild;
    struct node* rightchild;
};

用于新节点创建

struct node* newnode(int data)
{
    struct node* node=malloc(sizeof(struct node));
    node->data=data;
    node->leftchild=NULL;
    node->rightchild=NULL;
    return node;
 }

树高

int height(struct node* root)
{
    int lheight,rheight;
    if(root==NULL)
        return 0;
    else
    {
        lheight=height(root->leftchild);
        rheight=height(root->rightchild);
    }
    if(lheight>rheight)
        return lheight+1;
    else 
        return rheight+1;
}

打印节点的递归函数

void printlevelorder(struct node* root,int current,int level)
{
    if(current==level)
    {
        printf("%d ",root->data);
        return;
    }
    else
    {
        printlevelorder(root->leftchild,current+1,level);
        printlevelorder(root->rightchild,current+1,level);
    }

 }

遍历每一层的函数

void levelorder(struct node* root)
{
    int h,i;
    h= height(root);
    if(h!=0){
        for(i=1;i<=h;i++)
        {
            printlevelorder(root,1,i);
        }
    }
    else 
        printf("Tree not exist\n");
}

用于测试功能的驱动程序

int main()
{
    struct node* root=newnode(1);
    root->leftchild=newnode(2);
    root->rightchild=newnode(7);
    root->leftchild->leftchild=newnode(3);
    root->leftchild->rightchild=newnode(6);
    root->leftchild->leftchild->leftchild=newnode(4);
    root->leftchild->leftchild->leftchild->rightchild=newnode(5);
    root->rightchild->leftchild=newnode(9);
    root->rightchild->rightchild=newnode(8);
    levelorder(root);
    return 0;
}

Answer 1

当 current 是树的最大高度（在您的情况下为 5）时，您停止递归调用 printlevelorder 函数。由于 root 的右子树的高度小于 5，当 current 足够大时，遍历该子树时会出现分段错误。更好的解决方案是在遇到 NULL 节点时停止递归调用，而不是检查 current 何时达到 5.

Answer 2

函数printlevelorder 不检查指针root 是否为空。

将 NULL 检查添加为函数中的第一条语句：

if( !root )
{
    return;
}

当树的部分没有参数 level 假设的那么深时停止递归。

Answer 3

void printLevelOrder(struct node* root)
{
    int h, i;
    h = height(root);

    for (i=1; i<=h; i++)
        levelorder(root, i);
}

/* Print nodes at a given level */
void levelorder(struct node* root, int level)
{
    if (root == NULL)
        return;
    if (level == 1)
        printf("%d ", root->data);
    else if (level > 1)
    {
        printGivenLevel(root->left, level-1);
        printGivenLevel(root->right, level-1);
    }
}