假设您想递归地实现一个二叉树的宽度优先搜索。你会怎么做?

是否可以只使用调用堆栈作为辅助存储?


当前回答

我必须实现以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;
}

其他回答

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

下面使用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])

下面是递归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]
}

我想在上面的答案中加上我的观点,如果语言支持生成器之类的东西,bfs可以协递归地完成。

首先,@Tanzelax的回答是:

宽度优先遍历传统上使用队列,而不是堆栈。队列和堆栈的性质几乎是相反的,因此试图使用调用堆栈(因此得名为堆栈)作为辅助存储(队列)几乎是注定要失败的

实际上,普通函数调用的堆栈不会像普通堆栈那样运行。但是生成器函数将暂停函数的执行,因此它给了我们产生下一层节点的子节点的机会,而无需深入研究节点的更深层次的后代。

下面的代码是Python中的递归bfs。

def bfs(root):
  yield root
  for n in bfs(root):
    for c in n.children:
      yield c

这里的直觉是:

BFS首先将根作为第一个结果返回 假设我们已经有了BFS序列,BFS中的下一层元素是序列中前一个节点的直接子节点 重复以上两个步骤