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

Question

我需要打印(访问)二叉树的单个级别上的节点。
我不知道如何做到这一点，但话又说回来，我对一般算法不是很熟练。
我知道在广度优先遍历中你使用一个队列并且你首先将根节点放入队列然后你将它出队访问它并将它的 child 入队然后你出队第一个入队的 child 访问它并将它的 child 入队等等在...
根据我的理解，这使得无法准确知道一个级别何时结束和另一个级别何时开始，除非您在创建二叉树时为每个节点分配它的级别，然后在进行广度优先遍历时检查级别。

类似这样的东西(代码在 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);
}