打印二叉树的单个给定级别上的所有元素
打印二叉树的单个给定级别上的所有元素
提问于 2010-01-23 16:07:05
我需要打印出(访问)二叉树单层上的节点。
我不知道如何做到这一点，但话又说回来，我对算法总体上不是很熟练。
我知道在广度优先遍历中，你使用一个队列，你首先将根节点放入队列中，然后将其出队，访问它并将其子节点排队，然后将第一个排队的子节点出队，访问它并将其子节点排队，等等。
根据我的理解，这使得我们不可能确切地知道一个级别何时结束，另一个级别何时开始，除非你在创建二叉树时为每个节点分配它的级别，然后在进行广度优先遍历时检查级别。
如下所示(代码是用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;
}所以我的问题是：
这是在二叉树的单个级别上打印节点的唯一方法吗？
还有别的办法吗？
在创建树时，有没有不存储级别的其他方法？
回答 2
Stack Overflow用户
回答已采纳
发布于 2010-01-23 16:33:40
递归解决方案适合您吗？这是我用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);
}Stack Overflow用户
发布于 2012-09-10 22:53:32
@Para，
这使得不可能确切地知道一个级别何时结束，另一个级别何时开始，除非....
在您尝试执行的BFS遍历期间，您不需要遍历整个树。您可以通过引入数组level[]来修改wiki中给出的BFS psedocode；您必须执行以下操作：
- 将每个节点的级别初始化为0。如果为
level[t] > targeted_level break;
，则无论何时在行中标记o，都会分配级别：
-
o ← G.opposite(t,e)= levelt+1;
- after
t ← Q.dequeue()
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2122568
复制相关文章
相似问题
腾讯云开发者
