Как Вы распечатали бы данные в двоичном дереве, уровне уровнем, начав наверху?
Как много вещей, это - хорошая идея, которую часто несут слишком далеко. Мне нравится div+css управляемое расположение, потому что обычно довольно легко изменить появление, даже решительно, только через таблицу стилей. Также хорошо быть дружественным по отношению к браузерам низшего уровня, программам экранного доступа, и т.д. Но как большинство решений в программировании, цель сайта и стоимость разработки нужно рассмотреть в принятии решения. Никакая сторона не является правильным способом пойти 100% времени.
BTW, я думаю, что все соглашаются, что таблицы должны использоваться для табличных данных.
2 ответа
Обход уровня за уровнем известен как обход в ширину. Использование очереди - правильный способ сделать это. Если вы хотите выполнить обход в глубину, вы должны использовать стек.
Однако способ, которым вы его используете, не совсем стандартный. Вот как должно быть.
public Void BFS()
{
Queue q = new Queue();
q.Enqueue(root);//You don't need to write the root here, it will be written in the loop
while (q.count > 0)
{
Node n = q.DeQueue();
Console.Writeln(n.Value); //Only write the value when you dequeue it
if (n.left !=null)
{
q.EnQueue(n.left);//enqueue the left child
}
if (n.right !=null)
{
q.EnQueue(n.right);//enque the right child
}
}
}
Править
Вот алгоритм в действии. Допустим, у вас есть такое дерево:
1
/ \
2 3
/ / \
4 5 6
Сначала корень (1) будет помещен в очередь. Затем вводится петля. первый элемент в очереди (1) удаляется из очереди и печатается. Потомки 1 ставятся в очередь слева направо, теперь очередь содержит {2, 3} назад к началу цикла первый элемент в очереди (2) удаляется из очереди и печатается Потомки 2 ставятся в очередь слева направо, теперь очередь содержит {3, 4} назад к началу цикла ...
Очередь будет содержать эти значения по каждому циклу
1: {1}
2: {2, 3}
3: {3, 4}
4: {4 , 5, 6}
5: {5, 6}
6: {6}
7: {} // пусто, цикл завершается
Вывод:
1
2
3
4
5
6
Давайте посмотрим на некоторые решения 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))
)
)
)
Мы определим функцию widththFirst, которая будет обходить дерево, применяя желаемая функция для каждого элемента. С этим мы определим функцию печати и будем использовать ее следующим образом:
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, но здесь можно найти хорошее применение.