如果没有指定null的返回值，null如何在递归函数的调用堆栈中向上移动

Question

嗨，我目前正在学习使用C#的递归有序二叉树遍历。有一个主要方面我无法理解，尤其是下面的代码。

public void InOrder(BinaryTreeNode node)
{
if (node != null)
{
InOrder(node.Left);
Console.WriteLine(node.Value);
InOrder(node.Right);
}
}

如果我有一个看起来像这样的二叉树。。。

9
/   
4    20
/   /  
1  6 15  170

我知道，通过递归调用Inorder(node.left(，我最终会到达二叉树的左叶，即树的最末端，因为没有更多的节点，node.left将等于null。这棵树会是这样的。。。

9
/   
4    20
/   /  
1  6 15  170
/
null

因为node.left=null，所以第一个递归函数

InOrder(node.left)

将终止，并且

Console.Writeline(node.left) 

将执行

打印1的值

最终，在分析每个节点并打印所有节点后，这些null值会向上移动到调用堆栈中，当null值向上移动时，树开始看起来像这样。。

9
/     
4       20
/      /    
null  6 15    170
/    / 
null  null null

最终，树中的所有节点都等于null，并且所有节点都被打印以输出。。。

1、4、6、9、15、20、170

我不明白的是，这个null值是如何在树上向上移动的，并在没有返回值的情况下将所有已分析的节点更改为null。通常会有一个基本情况，比如。。。

if (node == null)
{
return null;
}

为此，我知道null将被返回，因此将在调用堆栈中持久存在/返回。但对于上面的第一个代码块，并没有返回语句。

我还发现，当只有一个返回语句而没有返回值时，这同样令人困惑，比如。。。

if (node == null)
{
return;
}

同样，没有指定返回null，那么在评估每个节点时，这个null值是如何在树中向上移动的呢？

这些代码都没有问题，它按预期工作，并打印二进制树InOrder的所有节点。这更多的是关于理解递归，以及为什么即使没有指定返回null值，第一块代码仍然可以工作。

提前感谢您的帮助。

Answer 1

没有指定返回null，那么在评估每个节点时，这个null值如何在树中向上移动？

即使没有要返回的值，函数仍将返回。它已经完成了执行，所以控制权被传递回调用者。

if (node != null) <- skipped entirely when the node is null
{
InOrder(node.Left);
Console.WriteLine(node.Value);
InOrder(node.Right);
}

对于您给出的树，这是在值为1:的节点上发生的情况

1. 它不是null，所以我们进入if块
2. 我们评估InOrder(node.Left)，它只是InOrder(null)：
   1. 它为null，因此跳过if块
   2. 我们返回呼叫方InOrder(node with value=1)
3. Console.WriteLine(node.Value)打印1

等等。。。

尽管您无法在代码中"看到"基本情况，但它仍然存在：(只是隐式的。