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

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 是节点的数量。

哇！分析起来并不有趣。我更喜欢递归版本。 :-)