algorithm - 递归访问二叉树中的节点

Question

我正在学习遍历二叉树的不同方法。我对此有几个问题。我见过这样的中序遍历伪代码(例如):

 InOrder (a node N)
{
   if N is not empty
   {
     InOrder (N's left child)
     visit N
     InOrder (N's right child)
   }
}

“访问”节点是什么意思？这是否意味着打印出来？另外，alogirthm 如何跟踪它已经访问过的节点？它是否使用在广度优先遍历中使用的队列？

谢谢

Answer 1

“访问”意味着用它做点什么。在一天结束时，您希望对每个节点都做一些事情，而不仅仅是遍历所有节点。

算法“跟踪”调用堆栈中函数参数中访问的内容。 IE。如果你问“信息在哪里？” - 信息就在那里。不需要额外的存储空间——这就是递归的美妙之处。