7

二叉树级顺序遍历的时间复杂度是多少？是 O(n) 还是 O(log n)？

void levelorder(Node *n)
{    queue < Node * >q;
     q.enqueue(n);

     while(!q.empty())
      {
         Node * node = q.front();
         DoSmthwith node;
         q.dequeue();          
         if(node->left != NULL)
         q.enqueue(node->left);
         if (node->right != NULL)
         q.enqueue(node->right);
      }

}
4

3 回答 3

7

它是O(n)，或者准确地说Theta(n)。

查看树中的每个节点 - 每个节点最多“访问”3次，并且至少一次） - 发现时（所有节点），从左儿子（非叶子）回来时以及来时从右儿子（非叶子）返回，因此最多总共访问 3*n 次，每个节点至少访问 n 次。每次访问都是O(1)（队列推送/弹出），总计 - Theta(n)。

于 2012-12-29T14:48:04.253 回答
3

解决此问题的另一种方法是确定级别顺序遍历与图的广度优先搜索非常相似。广度优先遍历具有时间复杂度，O(|V| + |E|)其中|V|是顶点数，|E|是边数。

在树中，边的数量大约等于顶点的数量。这使得它在节点数量上总体呈线性关系。

于 2014-09-19T23:01:41.913 回答
0

时间和空间复杂度为 O(n)。n = 没有。的节点。

空间复杂度 - 队列大小与节点数量成正比 O(n)

时间复杂度 - O(n) 每个节点被访问两次。在入队操作期间一次，在出队操作期间一次。

这是 BFS 的一个特例。您可以阅读有关 BFS（广度优先搜索）http://en.wikipedia.org/wiki/Breadth-first_search的信息。

于 2012-12-29T15:24:17.543 回答