二叉查找树，中序遍历，Step 3 逻辑辅助

Question

这不是对编码解决方案或编译器错误的请求。我更想了解一些东西。

我学习 C++ 已经有一段时间了，但在某些方面我仍然是新手。我正在关注 Paul 在 youtube 上的编程教程以及其他教程。

他制作了一个关于二叉搜索树有序遍历概念的 youtube 视频，以及一个展示这种遍历背后的实际编程的 youtube 视频。

谁能帮帮我，我不明白第3步

我的示例程序编译和运行良好，打印与 Paul 的完全一样。我让它工作并且可以复制它/可能出于打印以外的目的对其进行逆向工程，但我想在继续之前真正理解它。

这是 Paul 打印函数的代码

void BinarySearchTree::printInOrderPrivate(node* Ptr)
{
    if(root_ptr != NULL)
    {
        if(Ptr->left_ptr != NULL)
        {
            printInOrderPrivate(Ptr->left_ptr);
        }
        cout << Ptr->key <<" ";//Process Node here

        if(Ptr->right_ptr != NULL)
        {
            printInOrderPrivate(Ptr->right_ptr);
        }   
    }
    else
    {
        cout <<"The tree is empty\n";
    }
}

我只是不明白它在逻辑上是如何工作的。我会link他的概念视频，不过你不需要看，暂停一下，看看他画的图。 https://www.youtube.com/watch?v=pCXgWg5OfhY

在某些节点上，例如 3，左和右指针都将指向 NULL。

请注意代码中的递归调用 PrintInOrderPrivate(Ptr->Left) 和 PrintInOrderPrivate(Ptr->Right) 包含在 if 语句中，这些语句要求 Ptr 的 ->left 和 ->right 的值不是无效的。

我看到并理解该算法在纸上是如何工作的，但是该函数如何在 3 左右都为空的数字处不中断？它怎么知道要回去？

即使假设它确实以某种方式知道返回到包含 2 的节点，它不应该直接返回到 3 吗？

(1)包含2的节点没有左指针 (2)打印值 (3) 向右走（正确的意思是再次回到 3，不是吗？这会循环）。

我的意思是它有效，我看到它就在我面前编译，但我无法理解它是如何编译的。虽然我什至无法正确表达问题，但我们将不胜感激。谢谢你，如果你还在这里，请原谅 tl;dr！

Answer 1

理解递归的最简单方法是想象一个堆栈，其中每个堆栈帧对应一个函数调用。假设您有函数 func1、func2 和 func3。 func1 调用 func2，func2 调用 func3。现在堆栈的目的是跟踪 func3 returns 分别控制 func2 和 func2 控制 func1 的点。当调用 func1 时，会生成第一个堆栈帧（我们称之为 f1）。当在 func1 内部调用 func2 时，第二个框架 f2 被放置在 f1 之上。当在 func2 中调用 func3 时，第三个框架被放置在 f2 之上。当相应的函数完成其任务并且 returns 将控制权从调用函数的位置返回到函数时，堆栈帧将从堆栈中弹出。因此，帧从堆栈中弹出的顺序是：首先是 f3，然后是 f2，最后是 f1。

类比地，递归中的函数调用是用堆栈结构管理的。粗略地说，当递归遍历树时，每个节点都通过其成人节点中的函数调用来访问。因此，对于每个节点，堆栈上都存在一个对应的帧。因此，算法在遇到两个子节点都等于 NULL 的节点后不终止的原因是因为堆栈。当一个函数在离开代码的 else 部分后完成时，它会从堆栈中弹出，控制权会返回到它下面的堆栈帧。

二叉查找树，中序遍历，Step 3 逻辑辅助

Binary Search Tree, In Order Traversal, Step 3 logical assistance

c++

binary-tree

traversal