递归二叉树遍历代码走向无穷大

Question

我正在尝试遍历使用键盘输入数据构建的二叉树。数据插入二叉树成功。我有一个 switch 语句，其中 'case 2' 应该分别使用递归使用 Inorder、Preorder 和 Postorder 遍历算法遍历（并打印）二叉树。但是，当调用 'case 2' 时，屏幕上只会打印关于中序遍历应该打印的第一个数据；它也打印了很多次（无限次），我需要停止编译操作。如果有人帮助我解决这个问题，我会非常高兴。

（RootPtr 是全局定义的二叉树的顶级 0 级节点；而 GetNode 基本上是类型 TreePtr 指针的初始化函数（使用 malloc）。）

提前谢谢大家。

这是结构定义；

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

}Tree , *TreePtr;

这三个是分别调用的遍历函数；

void inorder (TreePtr TemPtr)
{

    while(TemPtr != NULL)
    {
        inorder((*TemPtr).left);
        printf(" %d ", (*TemPtr).data);
        inorder((*TemPtr).right);
    }
    printf("\n");
}

void preorder (TreePtr TemPtr)
{
    while(TemPtr != NULL)
    {
        printf(" %d ", (*TemPtr).data);
        preorder((*TemPtr).left);
        preorder((*TemPtr).right);
    }
    printf("\n");
}

void postorder (TreePtr TemPtr)
{
    while(TemPtr != NULL)
    {
        postorder((*TemPtr).left);
        postorder((*TemPtr).right);
        printf(" %d", (*TemPtr).data);
    }
    printf("\n");
}

这个是switch语句的相关'case'；

  case 2:
            TreePtr LocPtr;
            GetNode(&LocPtr);
            LocPtr = RootPtr;

            printf("\n");
            printf("Inorder traversal:");
            inorder(LocPtr);
            printf("Preorder traversal:");
            preorder(LocPtr);
            printf("Postorder traversal:");
            postorder(LocPtr);
            printf("\n");

            break;

Answer 1

遍历函数中不应该有 while 循环。递归将进入所有节点。

void inorder (TreePtr TemPtr)
{
    if (TemPtr != NULL) {
        inorder((*TemPtr).left);
        printf(" %d ", (*TemPtr).data);
        inorder((*TemPtr).right);
    }

    printf("\n");
}

如果您考虑一下，当您在循环中迭代时，您的 TemPtr 参数不会更改为 NULL。因此它会陷入无限循环。

树遍历说明：

在您的主程序 case 2 中，您调用 inorder 并将树的根作为参数。然后我们需要遍历树。

inorder(LocPtr);

In-order遍历为：

go to left child ... visit current node ... go to right child

我们在递归 function/method 中需要两件事：基本情况和递归调用。

在这里，我们的基本情况是 if (TemPtr != NULL)。当这个条件为假时，我们知道我们已经到达了一片叶子。如果 TemPtr 确实是一片叶子，我们就不会进一步计算它的 children （这会引发错误）。

但如果TemPtr不是NULL，则表示我们当前处于有效节点。因此，我们必须遵循 in-order 遍历的定义（如前所述）。

我们访问左边child:

inorder((*TemPtr).left); // equivalent to inorder(TemPtr->left);

我们访问当前节点：

printf(" %d ", (*TemPtr).data); // equivalent to printf (" %d ", TemPtr->data);

然后我们访问右边child:

inorder((*TemPtr).right); // equivalent to inorder(TemPtr->right);

当 inorder 完成时，inorder 的调用者从原来的地方继续。这个过程一直持续到 inorder(LocPtr) 完成，此时你将回到主节点，你的整个树将被遍历 in-ordered.

最简单的可视化方法是在 sheet 纸上绘制调用。函数将相互堆叠（main 在底部），并在完成后从堆栈中移除。

递归二叉树遍历代码走向无穷大

Recursive Binary Tree Traversal Code Goes to Infinity

c++

recursion

tree-traversal

binary-search-tree