c++ - 逐层遍历和打印二叉树

Question

我正在尝试遍历使用键盘输入数据构建的二叉树。数据插入二叉树成功。我有一个 switch 语句，其中“案例 4”应该逐级遍历(并打印)二叉树。但是我得到了 EXC_BAD_ACCESS 错误。如果有人能帮助我解决这个问题，我会非常高兴。

(RootPtr 是全局定义的二叉树的顶级 0 级节点；TreeDepth() 是计算树的“深度”的函数，其中 Depth 是全局定义的，根节点的深度为 0；GetNode 基本上是一个类型 TreePtr 指针的初始化函数(使用 malloc)。)

提前谢谢大家。

相关代码如下:

这是结构定义；

    typedef struct treeItem
{
    int data;
    struct treeItem *left;
    struct treeItem *right;

}Tree , *TreePtr;

这是我调用 Level by Level 遍历函数的 switch case；

case 4:
                TreePtr temp;
                GetNode(&temp);

                temp = RootPtr;

                printLevelOrder(temp);
                printf("\n\n");

                break;

这些是用于逐层遍历树的函数；

void printGivenLevel(TreePtr TemPtr, int level)
{
    if (items == 0)
        return;
    else
    {    if(level == 0 )
        {
            printf(" %d", (*TemPtr).data); //the line I got ERROR
        }
        else
        {
            printGivenLevel((*TemPtr).left, (level-1));
            printGivenLevel((*TemPtr).right, (level-1));
        }
    }
}

void printLevelOrder(TreePtr TemPtr)
{
    TreeDepth();
    if (items == 0)
        printf("\nTree is empty.\n");
    else
    {
        printf("Traverse level by level:");

        for (int i=0; i<=Depth; i++)
        {
            printGivenLevel(TemPtr, i);
        }
    }
}

Answer 1

差一个错误。在你的 for 循环中:

for (int i=0; i<=Depth; i++)

您正在遍历此循环 Depth + 1 次。这意味着您正在尝试访问比实际多一个级别。特别是，在 printGivenLevel 的最终调用中，在 level == 1 的递归点中，您已经位于树的底部。您现在又递归了一次，但是您传递到下一个递归级别的指针是垃圾指针(它们不能保证指向您被允许访问的内存，甚至不存在)。因此，当您尝试取消引用它们时，会出现错误。

还有一件事:这个实现非常低效，因为您要遍历树很多次。最好进行广度优先搜索，例如提到的 kiss-o-matic。这样，您将只遍历树一次，速度更快(尽管它确实使用更多内存)。