假设您想递归地实现一个二叉树的宽度优先搜索。你会怎么做?
是否可以只使用调用堆栈作为辅助存储?
假设您想递归地实现一个二叉树的宽度优先搜索。你会怎么做?
是否可以只使用调用堆栈作为辅助存储?
当前回答
我认为这可以使用指针来完成,而不使用任何队列。
基本上我们在任何地方都维护两个指针,一个指向父结点,另一个指向待处理的子结点(链接列表指向所有已处理的子结点)
现在你只需分配子进程的指针&当父进程处理完成时,你只需让子进程成为父进程进行下一层的处理
以下是我的代码:
//Tree Node
struct Node {
int val;
Node* left;
Node* right;
Node* next;
Node() : val(0), left(NULL), right(NULL), next(NULL) {}
Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
/ / Algorightm:
void LevelTraverse(Node* parent,Node* chidstart,Node* childend ){
if(!parent && !chidstart) return; // we processed everything
if(!parent && chidstart){ //finished processing last level
parent=chidstart;chidstart=childend=NULL; // assgin child to parent for processing next level
LevelTraverse(parent,chidstart,childend);
}else if(parent && !chidstart){ // This is new level first node tobe processed
Node* temp=parent; parent=parent->next;
if(temp->left) { childend=chidstart=temp->left; }
if(chidstart){
if(temp->right) { childend->next=temp->right; childend=temp->right; }
}else{
if(temp->right) { childend=chidstart=temp->right; }
}
LevelTraverse(parent,chidstart,childend);
}else if(parent && chidstart){ //we are in mid of some level processing
Node* temp=parent; parent=parent->next;
if(temp->left) { childend->next=temp->left; childend=temp->left; }
if(temp->right) { childend->next=temp->right; childend=temp->right; }
LevelTraverse(parent,chidstart,childend);
}
}
//驱动代码:
Node* connect(Node* root) {
if(!root) return NULL;
Node* parent; Node* childs, *childe; parent=childs=childe=NULL;
parent=root;
LevelTraverse(parent, childs, childe);
return root;
}
其他回答
c#实现的递归宽度优先搜索二叉树算法。
二叉树数据可视化
IDictionary<string, string[]> graph = new Dictionary<string, string[]> {
{"A", new [] {"B", "C"}},
{"B", new [] {"D", "E"}},
{"C", new [] {"F", "G"}},
{"E", new [] {"H"}}
};
void Main()
{
var pathFound = BreadthFirstSearch("A", "H", new string[0]);
Console.WriteLine(pathFound); // [A, B, E, H]
var pathNotFound = BreadthFirstSearch("A", "Z", new string[0]);
Console.WriteLine(pathNotFound); // []
}
IEnumerable<string> BreadthFirstSearch(string start, string end, IEnumerable<string> path)
{
if (start == end)
{
return path.Concat(new[] { end });
}
if (!graph.ContainsKey(start)) { return new string[0]; }
return graph[start].SelectMany(letter => BreadthFirstSearch(letter, end, path.Concat(new[] { start })));
}
如果你想让算法不仅适用于二叉树,而且适用于有两个或两个以上节点指向同一个节点的图,你必须通过持有已经访问过的节点列表来避免自循环。实现可能是这样的。
图形数据可视化
IDictionary<string, string[]> graph = new Dictionary<string, string[]> {
{"A", new [] {"B", "C"}},
{"B", new [] {"D", "E"}},
{"C", new [] {"F", "G", "E"}},
{"E", new [] {"H"}}
};
void Main()
{
var pathFound = BreadthFirstSearch("A", "H", new string[0], new List<string>());
Console.WriteLine(pathFound); // [A, B, E, H]
var pathNotFound = BreadthFirstSearch("A", "Z", new string[0], new List<string>());
Console.WriteLine(pathNotFound); // []
}
IEnumerable<string> BreadthFirstSearch(string start, string end, IEnumerable<string> path, IList<string> visited)
{
if (start == end)
{
return path.Concat(new[] { end });
}
if (!graph.ContainsKey(start)) { return new string[0]; }
return graph[start].Aggregate(new string[0], (acc, letter) =>
{
if (visited.Contains(letter))
{
return acc;
}
visited.Add(letter);
var result = BreadthFirstSearch(letter, end, path.Concat(new[] { start }), visited);
return acc.Concat(result).ToArray();
});
}
下面使用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])
在学习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
Here is a JavaScript Implementation that fakes Breadth First Traversal with Depth First recursion. I'm storing the node values at each depth inside an array, inside of a hash. If a level already exists(we have a collision), so we just push to the array at that level. You could use an array instead of a JavaScript object as well since our levels are numeric and can serve as array indices. You can return nodes, values, convert to a Linked List, or whatever you want. I'm just returning values for the sake of simplicity.
BinarySearchTree.prototype.breadthFirstRec = function() {
var levels = {};
var traverse = function(current, depth) {
if (!current) return null;
if (!levels[depth]) levels[depth] = [current.value];
else levels[depth].push(current.value);
traverse(current.left, depth + 1);
traverse(current.right, depth + 1);
};
traverse(this.root, 0);
return levels;
};
var bst = new BinarySearchTree();
bst.add(20, 22, 8, 4, 12, 10, 14, 24);
console.log('Recursive Breadth First: ', bst.breadthFirstRec());
/*Recursive Breadth First:
{ '0': [ 20 ],
'1': [ 8, 22 ],
'2': [ 4, 12, 24 ],
'3': [ 10, 14 ] } */
下面是一个使用迭代方法的实际广度优先遍历的示例。
BinarySearchTree.prototype.breadthFirst = function() {
var result = '',
queue = [],
current = this.root;
if (!current) return null;
queue.push(current);
while (current = queue.shift()) {
result += current.value + ' ';
current.left && queue.push(current.left);
current.right && queue.push(current.right);
}
return result;
};
console.log('Breadth First: ', bst.breadthFirst());
//Breadth First: 20 8 22 4 12 24 10 14
我找不到一种完全递归的方法(没有任何辅助数据结构)。但是如果队列Q是通过引用传递的,那么你可以得到下面这个愚蠢的尾部递归函数:
BFS(Q)
{
if (|Q| > 0)
v <- Dequeue(Q)
Traverse(v)
foreach w in children(v)
Enqueue(Q, w)
BFS(Q)
}