时间层次序遍历的复杂性 [英] Time complexity of level order traversal

问题描述

什么是二叉树层次序遍历的时间复杂度？它是为O（n）或O（log n）的？

 无效levelorder（节点* N）
{队列＆LT;节点*＆GT;问;
     q.enqueue（N）;

     而（！q.empty（））
      {
         节点*节点= q.front（）;
         DoSmthwith节点;
         q.dequeue（）;
         如果（与于节点GT;！左= NULL）
         q.enqueue（与于节点GT;左）;
         如果（与于节点GT;！右= NULL）
         q.enqueue（与于节点GT;右一）;
      }

}
 

解决方案

是 O（N），或者准确的说的Theta（N ）。

有树中的每个节点上的外表 - 至多3倍每个节点拜访，和至少一次） - 当它被发现（所有节点），从左侧儿子回来时（非叶）并从右侧的儿子（非叶），所以总共有3 * N访问最多和n visites每个节点到来时，追溯到至少。每次访问是 O（1）（队列推/流行），共计在 - 的Theta（N）

What is the time complexity of binary tree level order traversal ? Is it O(n) or 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);
      }

}

解决方案

It is O(n), or to be exact Theta(n).

Have a look on each node in the tree - each node is "visited" at most 3 times, and at least once) - when it is discovered (all nodes), when coming back from the left son (non leaf) and when coming back from the right son (non leaf), so total of 3*n visits at most and n visites at least per node. Each visit is O(1) (queue push/pop), totaling in - Theta(n).

这篇关于时间层次序遍历的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！