185

二分木の幅優先探索を再帰的に実装したいとしましょう。あなたならどうしますか？

コールスタックのみを補助記憶域として使用することは可能ですか?

4

22 に答える 22

150

(これはある種の思考練習、またはトリックの宿題/面接の質問でさえあると想定していますが、何らかの理由でヒープ領域が許可されないという奇妙なシナリオを想像できると思います [いくつかの本当に悪い習慣メモリ マネージャー? いくつかの奇妙なランタイム/OS の問題?] スタックにまだアクセスできます...)

幅優先トラバーサルでは、伝統的にスタックではなくキューを使用します。キューとスタックの性質はほとんど正反対です。そのため、コール スタック (スタックなので名前の由来) を補助ストレージ (キュー) として使用しようとすると、失敗する運命にあります。あなたがすべきではないコールスタックでばかげた何か。

同様に、実装しようとする非末尾再帰の性質は、本質的にアルゴリズムにスタックを追加することです。これにより、二分木で幅優先検索が行われなくなり、従来の BFS の実行時間などは完全には適用されなくなります。もちろん、ループを簡単に再帰呼び出しに変えることはいつでもできますが、それは意味のある再帰ではありません。

ただし、他の人が示しているように、BFS のセマンティクスに従うものを実装する方法はいくつかあります。比較のコストが高いが、ノード トラバーサルが安価な場合、@Simon Buchanが行ったように、反復的な深さ優先検索を単純に実行して、葉のみを処理できます。これは、ヒープに格納されたキューが増加せず、ローカルの深さ変数だけであり、ツリーが何度も何度もトラバースされるにつれてスタックがコール スタック上に何度も構築されることを意味します。@Patrickが指摘したように、配列に裏打ちされたバイナリツリーは通常、とにかく幅優先のトラバーサル順序で格納されるため、補助キューを必要とせずに、幅優先の検索は簡単です。

于 2010-03-31T02:32:53.787 に答える
28

配列を使用してバイナリ ツリーをバックアップすると、代数的に次のノードを決定できます。がノードの場合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)
于 2010-03-31T00:56:24.990 に答える
24

完全に再帰的に行う方法を見つけることができませんでした（補助データ構造なしで）。しかし、キュー Q が参照によって渡される場合、次の愚かな末尾再帰関数を使用できます。

BFS(Q)
{
  if (|Q| > 0)
     v <- Dequeue(Q)
     Traverse(v)
     foreach w in children(v)
        Enqueue(Q, w)    

     BFS(Q)
}
于 2010-03-31T00:52:50.673 に答える
7

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);
}
于 2015-05-04T01:13:30.823 に答える
3

愚かな方法：

template<typename T>
struct Node { Node* left; Node* right; T value; };

template<typename T, typename P>
bool searchNodeDepth(Node<T>* node, Node<T>** result, int depth, P pred) {
    if (!node) return false;
    if (!depth) {
        if (pred(node->value)) {
            *result = node;
        }
        return true;
    }
    --depth;
    searchNodeDepth(node->left, result, depth, pred);
    if (!*result)
        searchNodeDepth(node->right, result, depth, pred);
    return true;
}

template<typename T, typename P>
Node<T>* searchNode(Node<T>* node, P pred) {
    Node<T>* result = NULL;
    int depth = 0;
    while (searchNodeDepth(node, &result, depth, pred) && !result)
        ++depth;
    return result;
}

int main()
{
    // a c   f
    //  b   e
    //    d
    Node<char*>
        a = { NULL, NULL, "A" },
        c = { NULL, NULL, "C" },
        b = { &a, &c, "B" },
        f = { NULL, NULL, "F" },
        e = { NULL, &f, "E" },
        d = { &b, &e, "D" };

    Node<char*>* found = searchNode(&d, [](char* value) -> bool {
        printf("%s\n", value);
        return !strcmp((char*)value, "F");
    });

    printf("found: %s\n", found->value);

    return 0;
}
于 2010-03-31T01:19:56.163 に答える
2

これは、再帰的 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]
}
于 2014-12-15T01:40:50.427 に答える
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;
}
于 2012-01-11T23:09:34.680 に答える
1

v を開始頂点とする

問題のグラフを G とする

以下は、キューを使用しない擬似コードです

Initially label v as visited as you start from v
BFS(G,v)
    for all adjacent vertices w of v in G:
        if vertex w is not visited:
            label w as visited
    for all adjacent vertices w of v in G:
        recursively call BFS(G,w)
于 2014-11-06T06:13:10.783 に答える
0

これは、 QUEUE を使用せずにポインターを使用して実行できると思います。

基本的に、任意の時点で 2 つのポインターを維持しています。1 つは親を指し、もう 1 つは処理される子を指しています (処理されたすべてのリンクリスト)。

これで、子のポインターを割り当てるだけで、親の処理が終了したら、次のレベルを処理するために子を親にするだけです

以下は私のコードです：

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

//アルゴリズム:

    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;
    }
于 2020-12-07T04:46:42.880 に答える
0 
#include <bits/stdc++.h>
using namespace std;
#define Max 1000

vector <int> adj[Max];
bool visited[Max];

void bfs_recursion_utils(queue<int>& Q) {
    while(!Q.empty()) {
        int u = Q.front();
        visited[u] = true;
        cout << u << endl;
        Q.pop();
        for(int i = 0; i < (int)adj[u].size(); ++i) {
            int v = adj[u][i];
            if(!visited[v])
                Q.push(v), visited[v] = true;
        }
        bfs_recursion_utils(Q);
    }
}

void bfs_recursion(int source, queue <int>& Q) {
    memset(visited, false, sizeof visited);
    Q.push(source);
    bfs_recursion_utils(Q);
}

int main(void) {
    queue <int> Q;
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[1].push_back(4);

    adj[2].push_back(5);
    adj[2].push_back(6);

    adj[3].push_back(7);

    bfs_recursion(1, Q);
    return 0;
}
于 2014-06-02T10:54:17.260 に答える
0

これは、深さ優先再帰で幅優先トラバーサルを偽装する JavaScript 実装です。ハッシュ内の配列内の各深さでノード値を格納しています。レベルが既に存在する場合 (衝突がある場合)、そのレベルの配列にプッシュするだけです。レベルは数値であり、配列インデックスとして機能できるため、JavaScript オブジェクトの代わりに配列を使用することもできます。ノード、値を返したり、リンクされたリストに変換したり、必要なものを何でも作成できます。簡単にするために値を返しているだけです。

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
于 2015-02-19T09:05:03.740 に答える