层序遍历的时间复杂度

Question

二叉树级序遍历的时间复杂度是多少?是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);
      }
}

Answer 1

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

查看树中的每个节点-每个节点最多被"访问"3次，至少一次)-当它被发现时(所有节点)，当从左子节点(非叶节点)返回时，当从右子节点(非叶节点)返回时，所以总共最多3*n次访问，每个节点至少n次访问。每次访问O(1)(队列push/pop)，共计- Theta(n)。

Answer 2

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

在树中，边的数量等于顶点的数量。这使得总体在节点数量上是线性的。

特别是，由于树中的每个节点(根节点除外)都有一个传入边(来自它的一个父节点)，我们得到，|E| = |V| - 1 .

因此，O(|V| + |E|) = O(|V| + |V| - 1) = O(|V|) .

Answer 3

时间和空间复杂度为O(n)。N =否。节点。

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

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

这是BFS的一个特例。你可以阅读有关BFS(广度优先搜索)http://en.wikipedia.org/wiki/Breadth-firstrongearch .