假设您想递归地实现一个二叉树的宽度优先搜索。你会怎么做?
是否可以只使用调用堆栈作为辅助存储?
假设您想递归地实现一个二叉树的宽度优先搜索。你会怎么做?
是否可以只使用调用堆栈作为辅助存储?
当前回答
在学习AlgoExpert时,对这个问题进行了改编。提示符中已经提供了以下Class。这里是python中的迭代和递归解决方案。这个问题的目标是返回一个输出数组,其中列出了按访问顺序排列的节点名称。如果遍历顺序为A -> B -> D -> F,则输出为['A','B','D','F']
class Node:
def __init__(self, name):
self.children = []
self.name = name
def addChild(self, name):
self.children.append(Node(name))
return self
递归
def breadthFirstSearch(self, array):
return self._bfs(array, [self])
def _bfs(self, array, visited):
# Base case - no more nodes to visit
if len(visited) == 0:
return array
node = visited.pop(0)
array.append(node.name)
visited.extend(node.children)
return self._bfs(array, visited)
迭代
def breadthFirstSearch(self, array):
array.append(self.name)
queue = [self]
while len(queue) > 0:
node = queue.pop(0)
for child in node.children:
array.append(child.name)
queue.append(child)
return array
其他回答
在学习AlgoExpert时,对这个问题进行了改编。提示符中已经提供了以下Class。这里是python中的迭代和递归解决方案。这个问题的目标是返回一个输出数组,其中列出了按访问顺序排列的节点名称。如果遍历顺序为A -> B -> D -> F,则输出为['A','B','D','F']
class Node:
def __init__(self, name):
self.children = []
self.name = name
def addChild(self, name):
self.children.append(Node(name))
return self
递归
def breadthFirstSearch(self, array):
return self._bfs(array, [self])
def _bfs(self, array, visited):
# Base case - no more nodes to visit
if len(visited) == 0:
return array
node = visited.pop(0)
array.append(node.name)
visited.extend(node.children)
return self._bfs(array, visited)
迭代
def breadthFirstSearch(self, array):
array.append(self.name)
queue = [self]
while len(queue) > 0:
node = queue.pop(0)
for child in node.children:
array.append(child.name)
queue.append(child)
return array
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);
}
我找不到一种完全递归的方法(没有任何辅助数据结构)。但是如果队列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)
下面使用Haskell对我来说似乎很自然。在树的各个层次上递归迭代(这里我将名字收集到一个大的有序字符串中,以显示树的路径):
data Node = Node {name :: String, children :: [Node]}
aTree = Node "r" [Node "c1" [Node "gc1" [Node "ggc1" []], Node "gc2" []] , Node "c2" [Node "gc3" []], Node "c3" [] ]
breadthFirstOrder x = levelRecurser [x]
where levelRecurser level = if length level == 0
then ""
else concat [name node ++ " " | node <- level] ++ levelRecurser (concat [children node | node <- level])