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])

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);
}

在学习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

我认为这可以使用指针来完成，而不使用任何队列。

基本上我们在任何地方都维护两个指针，一个指向父结点，另一个指向待处理的子结点(链接列表指向所有已处理的子结点)

现在你只需分配子进程的指针&当父进程处理完成时，你只需让子进程成为父进程进行下一层的处理

以下是我的代码:

//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;
    }

以下是我的完全递归实现的双向图的广度优先搜索的代码，而不使用循环和队列。

public class Graph { public int V; public LinkedList<Integer> adj[]; Graph(int v) { V = v; adj = new LinkedList[v]; for (int i=0; i<v; ++i) adj[i] = new LinkedList<>(); } void addEdge(int v,int w) { adj[v].add(w); adj[w].add(v); } public LinkedList<Integer> getAdjVerted(int vertex) { return adj[vertex]; } public String toString() { String s = ""; for (int i=0;i<adj.length;i++) { s = s +"\n"+i +"-->"+ adj[i] ; } return s; } } //BFS IMPLEMENTATION public static void recursiveBFS(Graph graph, int vertex,boolean visited[], boolean isAdjPrinted[]) { if (!visited[vertex]) { System.out.print(vertex +" "); visited[vertex] = true; } if(!isAdjPrinted[vertex]) { isAdjPrinted[vertex] = true; List<Integer> adjList = graph.getAdjVerted(vertex); printAdjecent(graph, adjList, visited, 0,isAdjPrinted); } } public static void recursiveBFS(Graph graph, List<Integer> vertexList, boolean visited[], int i, boolean isAdjPrinted[]) { if (i < vertexList.size()) { recursiveBFS(graph, vertexList.get(i), visited, isAdjPrinted); recursiveBFS(graph, vertexList, visited, i+1, isAdjPrinted); } } public static void printAdjecent(Graph graph, List<Integer> list, boolean visited[], int i, boolean isAdjPrinted[]) { if (i < list.size()) { if (!visited[list.get(i)]) { System.out.print(list.get(i)+" "); visited[list.get(i)] = true; } printAdjecent(graph, list, visited, i+1, isAdjPrinted); } else { recursiveBFS(graph, list, visited, 0, isAdjPrinted); } }