基于堆栈的树遍历的时间复杂度

Question

以下执行二叉树遍历的时间复杂度是多少？

void Tree::nonRecInOrder() 
{ 
    // nonrecursive inOrder Traversal using Stack 
    Stack< TreeNode* > s ; // declare and initialize stack 
    TreeNode* currentNode = root ; 

    while(true) 
    { 
     while(currentNode) 
     { 
      // move down leftChild fields 
      s.add(currentNode) ; 
      currentNode = currentNode->leftChild ; 
     } 

     if(! s.isEmpty()) // stack is not empty 
     { 
      currentNode = *s.del(currentNode) ; // delete from stack 
      cout << currentNode->data ; 
      currentNode = currentNode->rightChild ; 
     } 
     else 
     { 
      break ; 
     } 
    }  
} 

你能否解释一下如何计算复杂性？

Answer 1

表征困难函数的大O复杂性的一种方法是考虑它访问的某些资源，然后限制该资源被访问的次数。在这种情况下，当您进行树遍历时，您可能会考虑每个节点从堆栈中被压入或弹出的次数。这是一个很好的界限的原因是，这个函数的所有努力工作 - 内部循环通过一系列节点下降，外部循环处理堆栈中的最顶层 - 可能受到节点被推动的次数的限制进入堆栈或从堆栈弹出。这是因为当堆栈为空时，最外层的循环终止，所以它不能运行多次，而堆栈有一些东西压到它上面，而最内层的循环的工作与按压堆栈的次数成正比循环过程。

让我们看看我们如何限制这些数量。第一个问题是每个节点可以将多少次加入到堆栈中。那么，如果一个节点或者它的一个祖先沿着一条只有左路的路径是循环开始执行时的当前节点，那么它只会被添加到栈中。这可能发生多少次？我的说法是这最多只发生一次。这个证明是基于树中节点深度的归纳。我们使用这样的观察：如果一个节点是堆栈中节点的直接右子节点，那么只会再次选择该节点作为当前节点。作为归纳的基本情况，如果节点是根（深度为零），则不能再次选择该节点，因为它没有父节点。对于归纳步​​骤，如果确实没有深度为d的节点可以被选择为当前节点的两倍，那么深度d + 1中的节点不能被选择两次，因为深度d + 1处的节点仅在选择其父母时被选择再次，但通过归纳假设，我们知道这不是真的。因此，我们没有选择任何节点作为当前节点的两倍。我们通过一个简单的观察来跟踪这个问题，即没有一个左子节点可以作为循环开始时的当前节点，因为当前节点是根节点（不是左子节点），或者是某个节点的右子节点。这个说法，再加上没有两次访问节点这一事实，意味着一个节点最多只能添加到队列中一次，这种情况发生在最高的左祖先变为当前节点时发生。

这也给了我们一个可能的出队数量的限制，因为出队数量不能超过入队数量。由于每个节点最多只有一次入队，因此最多也只能出队一次。为了完成这些工作，我们知道整个函数的复杂性受到排队和出队数量的限制，所以复杂度为O（n），其中n是节点数量。

Whe！分析起来并不好玩。我更喜欢递归版本。 :-)