在二叉树的单个给定级别上打印所有元素

我需要打印（访问）二叉树的单个级别上的节点。
我不明白这是如何做到的，但我再次对算法不熟练。
我知道，在广度优先遍历中，您使用一个队列，并且首先将根节点放入队列中，然后您将它列入队列并将其排入子队列，然后您将第一个被取消的子队列出队列，然后将其排入子队列等等......
据我所知，这使得不可能确切地知道何时一个层次结束，另一个层次开始，除非您在创建二叉树时将其分配给每个节点，然后在您执行该操作时检查层次广度优先遍历。在二叉树的单个给定级别上打印所有元素

像这样的东西（代码是在PHP中，但这不是一个PHP相关的问题，这是一个通用算法相关的问题 - 这是一个函数的一部分，添加一个节点到一个二进制树，每个节点添加）：

if($this->root == null) 
    { 
     $this->root = $node; 
        $this->root->level = 1; 
     return; 
    } 

    $nextnode = $this->root; 

      $level = 1; 

    while (true) 
    { 
     if($node->value > $nextnode->value) 
     { 
         if($nextnode->right != null) 
         { 
          $nextnode = $nextnode->right; 
          $level++; 
         } 
         else 
         { 
          $nextnode->right = $node; 
          $nextnode->right->level = ++$level; 
          return; 
         } 
     } 
     else if($node->value < $nextnode->value) 
     { 
         if($nextnode->left != null) 
         { 
          $nextnode = $nextnode->left; 
          $level++; 
         } 
         else 
         { 
          $nextnode->left = $node; 
          $nextnode->left->level = ++$level; 
          return; 
         } 
     } 
     else if($node->value == $nextnode->value) 
      return; 
    }

所以我的问题是：

这是印上一个二叉树的单级节点的唯一途径？
还有别的办法吗？
创建树时没有存储关卡还有其他方法吗？

来源

2010-01-23 Para

会递归解决方案套件吗？我在C中写过这个，我希望这对你来说不是问题。

void traverse_tree_rec(TreeNode *ptn, int current_level, int targeted_level, (void*)(pVisit)(TreeElement*)){  
    if (ptn==NULL) 
     return; 
    else if(current_level == targeted_level) 
     pVisit(ptn->entry); 
    else{ 
     traverse_tree_rec(ptn->left, current_level+1, targeted_level, pVisit); 
     traverse_tree_rec(ptn->right, current_level+1, targeted_level, pVisit); 
    } 
} 

void traverse_level(Tree *pTree, int level, (void*)(pFunction)(TreeElement)){ 
    traverse_level_rec(pTree->root, 0, level, pFunction); 
}

来源

2010-01-23 08:33:40

需求第一和第二条款切换或有一个空指针引用可能。首先访问左侧分支也更自然！ – 2010-01-23 10:41:34

完成并完成。谢谢你，先生。 – 2010-01-23 21:10:54

@Para，

这使得它无法确切地知道一个关卡结束和另一个开始，除非....

你不必在遍历整个树BFS遍历您正在尝试。您可以通过引入数组级别[]来修改wiki中给出的BFS psedocode; 你必须做这些：

初始化级别0的每个节点。
只要你在行中标记○：o ← G.opposite(t,e)赋值级别[o] =级别[t] +1;
后t ← Q.dequeue()如果level[t] > targeted_level break;

来源

2012-09-10 14:53:31

在二叉树的单个给定级别上打印所有元素

回答

相关问题