0

我需要在二叉树的单个级别上打印（访问）节点。
我不明白如何做到这一点，但我又不是很擅长一般的算法。
我知道在广度优先遍历中你使用一个队列，你首先将根节点放入队列然后你出队它访问它并将它的孩子排队然后你将第一个入队的孩子出队访问它并将它的孩子排队等等on...
据我了解，除非您在创建二叉树时为每个节点分配其级别，然后在进行广度优先遍历时检查该级别，否则无法准确知道一个级别何时结束而另一个级别何时开始.

像这样的东西（代码在 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;
    }

所以我的问题是：

这是在二叉树的单个级别上打印节点的唯一方法吗？
还有其他方法吗？
在创建树时是否有另一种不存储关卡的方法？

4

2 回答 2

3

递归解决方案适合您吗？我是用 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-23T08:33:40.087 回答
0

@帕拉，

这使得无法准确知道一个级别何时结束，另一个级别何时开始，除非......

在您尝试执行的BFS 遍历期间，您无需遍历整个树。您可以通过引入数组 level[] 来修改 wiki 中给出的BFS psedocode ；你必须这样做：

  1. 将每个节点的级别初始化为 0。

  2. 每当你在行中标记 o 时：o ← G.opposite(t,e)分配 level[o] = level[t]+1;

  3. t ← Q.dequeue()如果之后level[t] > targeted_level break;

于 2012-09-10T14:53:31.870 回答