如何证明预序树遍历算法终止？

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。