Печать всех элементов на одном заданном уровне двоичного дерева

Question

Я должен распечатать (посетить) узлы на одном уровне двоичного дерева.
Я не вижу, как это можно сделать, но потом я не очень разбираюсь в алгоритмах вообще.
Я знаю, что в обходном перекрестке вы используете очередь и начинаете с помещения корневого узла в очередь, после чего вы удаляете его, посещая его и ставьте в очередь его дочерние элементы, а затем вы удаляете первого зарегистрированного ребенка и посещают его детей и так далее ...
И, по моему мнению, это не позволяет точно знать, когда заканчивается один уровень, а другой начинается, если вы не назначаете каждому узлу уровень, когда создается двоичное дерево, а затем просто проверяйте уровень, когда вы делаете Ширина - первый обход.

Что-то вроде этого (код находится на 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; 
    } 

Так что мои вопросы:

это единственный способ печати узлов на одном уровне двоичного дерева?
Есть ли другой способ?
Есть ли другой способ, не сохраняя уровень при создании дерева?

Answer 1

Будет ли рекурсивное решение для вас? Я написал это в 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); 
} 

Answer 2

@Para,

это делает невозможным, чтобы точно знать, когда один уровень заканчивается и другой начинается, если ....

Вам не нужно пройти все дерево во время BFS обход вы пытаетесь сделать. Вы можете изменить BFS psedocode, указанный в wiki, путем введения уровня массива []; Вы должны сделать это:

1. уровень инициализации как 0 для каждого узла.

2. всякий раз, когда u отметит o в строке: o ← G.opposite(t,e) присвоить уровень [o] = уровень [t] +1;

3. после t ← Q.dequeue() если level[t] > targeted_level break;