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

Question

我看到结构归纳是证明算法终止属性的常用方法，但是通过树上的归纳来证明并不那么容易强>算法。现在我正在努力证明预序树遍历算法是可终止的:

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

我应该如何证明？

Answer 1

通过 strong induction在树的高度上。

基本案例

算法在高度为 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 的树，并且由 strong归纳假设前序遍历终止于高度小于或等于 n 的树。

preorder(node.right)

与 node.left 相同。