Распечатать все элементы на одном заданном уровне двоичного дерева

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 , указанный в вики, введя уровень массива []; Вы должны сделать это:

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

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

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