algorithm - 如何证明前序树遍历算法终止？

Question

我认为结构归纳是证明算法终止属性的常用方法，但通过树算法上的归纳来证明并不容易。现在我正在努力证明前序树遍历算法是可终止的：

preorder(node)
  if node == null then return
  visit(node)
  preorder(node.left) 
  preorder(node.right)

我该怎么证明？

Answer 1

通过对树高的强烈感应。

基本情况

该算法在高度为 0 的树上终止，因为在高度为 0 的树中，我们有没有儿子的根。visit(node)在根上是一个步骤，访问node.left并node.right终止，因为它们都是NULL.

感应步骤

假设前序遍历在所有高度为 的树上终止0, 1, 2, .. n，我们证明它在所有高度为 的树上终止n+1。让我们看一下：

visit(node)

终止，因为它是一个步骤。

preorder(node.left) 

终止，因为如果我们的树有高度，n+1则node.left最多是高度为 的树n，并且通过强归纳假设，前序遍历在高度小于或等于 的树上终止n。

preorder(node.right)

一样node.left。

Answer 2

树不包含循环。如果有循环，算法将永远运行。因此，没有循环是证明的关键点。其他点是左或右受内存约束最终指向 null。