假设您想递归地实现一个二叉树的宽度优先搜索。你会怎么做?
是否可以只使用调用堆栈作为辅助存储?
假设您想递归地实现一个二叉树的宽度优先搜索。你会怎么做?
是否可以只使用调用堆栈作为辅助存储?
当前回答
下面是递归BFS的Scala 2.11.4实现。为了简洁起见,我牺牲了尾部调用优化,但是TCOd版本非常相似。参见@snv的帖子。
import scala.collection.immutable.Queue
object RecursiveBfs {
def bfs[A](tree: Tree[A], target: A): Boolean = {
bfs(Queue(tree), target)
}
private def bfs[A](forest: Queue[Tree[A]], target: A): Boolean = {
forest.dequeueOption exists {
case (E, tail) => bfs(tail, target)
case (Node(value, _, _), _) if value == target => true
case (Node(_, l, r), tail) => bfs(tail.enqueue(List(l, r)), target)
}
}
sealed trait Tree[+A]
case class Node[+A](data: A, left: Tree[A], right: Tree[A]) extends Tree[A]
case object E extends Tree[Nothing]
}
其他回答
我找不到一种完全递归的方法(没有任何辅助数据结构)。但是如果队列Q是通过引用传递的,那么你可以得到下面这个愚蠢的尾部递归函数:
BFS(Q)
{
if (|Q| > 0)
v <- Dequeue(Q)
Traverse(v)
foreach w in children(v)
Enqueue(Q, w)
BFS(Q)
}
如果使用数组来支持二叉树,则可以用代数方法确定下一个节点。如果I是一个节点,那么它的子节点可以在2i + 1(左节点)和2i + 2(右节点)处找到。节点的下一个邻居由i + 1给出,除非i是2的幂
下面是在数组支持的二叉搜索树上实现宽度优先搜索的伪代码。这假设一个固定大小的数组,因此一个固定深度的树。它将查看无父节点,并可能创建难以管理的大堆栈。
bintree-bfs(bintree, elt, i)
if (i == LENGTH)
return false
else if (bintree[i] == elt)
return true
else
return bintree-bfs(bintree, elt, i+1)
我发现了一个非常漂亮的递归(甚至函数)宽度优先遍历相关算法。不是我的想法,但我认为在这个话题中应该提到它。
Chris Okasaki在http://okasaki.blogspot.de/2008/07/breadth-first-numbering-algorithm-in.html上用3张图片非常清楚地解释了他的ICFP 2000的宽度优先编号算法。
Debasish Ghosh的Scala实现,我在http://debasishg.blogspot.de/2008/09/breadth-first-numbering-okasakis.html找到的,是:
trait Tree[+T]
case class Node[+T](data: T, left: Tree[T], right: Tree[T]) extends Tree[T]
case object E extends Tree[Nothing]
def bfsNumForest[T](i: Int, trees: Queue[Tree[T]]): Queue[Tree[Int]] = {
if (trees.isEmpty) Queue.Empty
else {
trees.dequeue match {
case (E, ts) =>
bfsNumForest(i, ts).enqueue[Tree[Int]](E)
case (Node(d, l, r), ts) =>
val q = ts.enqueue(l, r)
val qq = bfsNumForest(i+1, q)
val (bb, qqq) = qq.dequeue
val (aa, tss) = qqq.dequeue
tss.enqueue[org.dg.collection.BFSNumber.Tree[Int]](Node(i, aa, bb))
}
}
}
def bfsNumTree[T](t: Tree[T]): Tree[Int] = {
val q = Queue.Empty.enqueue[Tree[T]](t)
val qq = bfsNumForest(1, q)
qq.dequeue._1
}
我必须实现以BFS顺序输出的堆遍历。它实际上不是BFS,但完成了相同的任务。
private void getNodeValue(Node node, int index, int[] array) {
array[index] = node.value;
index = (index*2)+1;
Node left = node.leftNode;
if (left!=null) getNodeValue(left,index,array);
Node right = node.rightNode;
if (right!=null) getNodeValue(right,index+1,array);
}
public int[] getHeap() {
int[] nodes = new int[size];
getNodeValue(root,0,nodes);
return nodes;
}
Java中简单的BFS和DFS递归: 只需要在堆栈/队列中推送/提供树的根节点并调用这些函数。
public static void breadthFirstSearch(Queue queue) {
if (queue.isEmpty())
return;
Node node = (Node) queue.poll();
System.out.println(node + " ");
if (node.right != null)
queue.offer(node.right);
if (node.left != null)
queue.offer(node.left);
breadthFirstSearch(queue);
}
public static void depthFirstSearch(Stack stack) {
if (stack.isEmpty())
return;
Node node = (Node) stack.pop();
System.out.println(node + " ");
if (node.right != null)
stack.push(node.right);
if (node.left != null)
stack.push(node.left);
depthFirstSearch(stack);
}