如何打印二叉树中的数据，从顶层开始逐层打印？
如何打印二叉树中的数据，从顶层开始逐层打印？
提问于 2009-07-09 15:29:24
这是一个面试问题
我想出了一个解决方案。它使用队列。
public Void BFS()
{
Queue q = new Queue();
q.Enqueue(root);
Console.WriteLine(root.Value);
while (q.count > 0)
{
Node n = q.DeQueue();
if (n.left !=null)
{
Console.Writeln(n.left);
q.EnQueue(n.left);
}
if (n.right !=null)
{
Console.Writeln(n.right);
q.EnQueue(n.right);
}
}
} 还有比这更好的解决方案吗?它不使用队列。
回答 10
Stack Overflow用户
发布于 2012-05-05 11:53:14
由于问题需要逐层打印树，因此应该有一种方法来确定何时在控制台上打印换行符。下面是我的代码，它试图通过将NewLine节点附加到队列来执行相同的操作，
void PrintByLevel(Node *root)
{
Queue q;
Node *newline = new Node("\n");
Node *v;
q->enque(root);
q->enque(newline);
while(!q->empty()) {
v = q->deque();
if(v == newline) {
printf("\n");
if(!q->empty())
q->enque(newline);
}
else {
printf("%s", v->val);
if(v->Left)
q-enque(v->left);
if(v->right)
q->enque(v->right);
}
}
delete newline;
}Stack Overflow用户
发布于 2009-07-09 23:03:11
让我们来看看一些Scala解决方案。首先，我将定义一个非常基本的二叉树：
case class Tree[+T](value: T, left: Option[Tree[T]], right: Option[Tree[T]])我们将使用以下树：
1
/ \
2 3
/ / \
4 5 6您可以这样定义树：
val myTree = Tree(1,
Some(Tree(2,
Some(Tree(4, None, None)),
None
)
),
Some(Tree(3,
Some(Tree(5, None, None)),
Some(Tree(6, None, None))
)
)
)我们将定义一个breadthFirst函数，该函数将遍历树，将所需的函数应用于每个元素。在这里，我们将定义一个print函数，并像这样使用它：
def printTree(tree: Tree[Any]) =
breadthFirst(tree, (t: Tree[Any]) => println(t.value))
printTree(myTree)现在，Scala解决方案，递归，列表，但没有队列：
def breadthFirst[T](t: Tree[T], f: Tree[T] => Unit): Unit = {
def traverse(trees: List[Tree[T]]): Unit = trees match {
case Nil => // do nothing
case _ =>
val children = for{tree <- trees
Some(child) <- List(tree.left, tree.right)}
yield child
trees map f
traverse(children)
}
traverse(List(t))
}接下来，Scala解决方案，队列，无递归：
def breadthFirst[T](t: Tree[T], f: Tree[T] => Unit): Unit = {
import scala.collection.mutable.Queue
val queue = new Queue[Option[Tree[T]]]
import queue._
enqueue(Some(t))
while(!isEmpty)
dequeue match {
case Some(tree) =>
f(tree)
enqueue(tree.left)
enqueue(tree.right)
case None =>
}
}这种递归解决方案功能齐全，但我有一种不安的感觉，那就是它还可以进一步简化。
队列版本不起作用，但它非常有效。关于导入对象的部分在Scala中并不常见，但在这里可以很好地使用。
Stack Overflow用户
发布于 2014-11-12 15:53:37
public class LevelOrderTraversalQueue {
Queue<Nodes> qe = new LinkedList<Nodes>();
public void printLevelOrder(Nodes root)
{
if(root == null) return;
qe.add(root);
int count = qe.size();
while(count!=0)
{
System.out.print(qe.peek().getValue());
System.out.print(" ");
if(qe.peek().getLeft()!=null) qe.add(qe.peek().getLeft());
if(qe.peek().getRight()!=null) qe.add(qe.peek().getRight());
qe.remove(); count = count -1;
if(count == 0 )
{
System.out.println(" ");
count = qe.size();
}
}
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/1104644
复制相关文章
相似问题