[algorithm] 너비 우선 검색을 재귀 적으로 수행

이진 트리에 대한 폭 넓은 검색을 재귀 적 으로 구현하려고한다고 가정 해 봅시다 . 어떻게 하시겠습니까?

보조 스택으로 콜 스택 만 사용할 수 있습니까?

답변

(이것은 일종의 사고 운동이거나 심지어 까다로운 숙제 / 인터뷰 질문이라고 가정하지만 어떤 이유로 힙 공간을 허용하지 않는 기괴한 시나리오를 상상할 수 있다고 가정합니다. 메모리 관리자? 일부 이상한 런타임 / OS 문제?]] 스택에 액세스 할 수있는 동안 …)

폭 우선 순회는 전통적으로 스택이 아닌 대기열을 사용합니다. 대기열과 스택의 특성은 거의 반대이므로 보조 스택 (큐) 인 호출 스택 (스택이므로 이름)을 사용하려고하면 실패하지 않을 것입니다. 호출 스택에 멍청하게도 말도 안되는 일이 있습니다.

같은 토큰에서, 당신이 구현하려고하는 비 꼬리 재귀의 본질은 본질적으로 알고리즘에 스택을 추가하는 것입니다. 이로 인해 더 이상 이진 트리에서 처음으로 검색하지 않으므로 기존 BFS의 런타임 및 기타 사항이 더 이상 완전히 적용되지 않습니다. 물론 루프를 재귀 호출로 쉽게 바꿀 수 있지만 이는 의미있는 재귀가 아닙니다.

그러나 다른 사람들이 보여 주듯이 BFS의 의미를 따르는 무언가를 어떤 비용으로 구현하는 방법이 있습니다. 비교 비용이 비싸지 만 노드 순회가 저렴한 경우 @Simon Buchan과 마찬가지로 반복 깊이 우선 검색을 실행하여 잎만 처리 할 수 있습니다. 이는 힙에 저장된 증가하는 큐가없고 로컬 깊이 변수 만 있고 트리가 계속해서 반복됨에 따라 호출 스택에서 스택이 계속 누적되는 것을 의미합니다. 있듯이 @Patrick이 언급에 그 너비 우선 탐색은 또한 보조 큐 없이도 사소한 것이되도록 배열에 근거 이진 트리가 통상적 어쨌든 너비 우선 탐색 순서로 저장된다.

답변

배열을 사용하여 이진 트리를 백업하면 다음 노드를 대수적으로 결정할 수 있습니다. i노드 인 경우 하위 노드는 2i + 1(왼쪽 노드) 및 2i + 2(오른쪽 노드) 에서 찾을 수 있습니다 . 노드의 다음 이웃 은의 거듭 제곱이 i + 1아닌 한i2

다음은 배열 지원 이진 검색 트리에서 광범위한 첫 번째 검색을 순진하게 구현하기위한 의사 코드입니다. 이것은 고정 크기 배열과 고정 깊이 트리를 가정합니다. 부모없는 노드를보고 관리 할 수 없을 정도로 큰 스택을 만들 수 있습니다.

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)

답변

보조 데이터 구조없이 완전히 재귀 적으로 수행 할 수있는 방법을 찾지 못했습니다. 그러나 큐 Q가 참조로 전달되면 다음과 같은 어리석은 꼬리 재귀 함수를 가질 수 있습니다.

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

     BFS(Q)
}

답변

다음 방법은 DFS 알고리즘을 사용하여 특정 수준의 모든 노드를 가져 왔습니다. 이는 해당 수준에서 BFS를 수행하는 것과 같습니다. 트리의 깊이를 찾아 모든 레벨에 대해이 작업을 수행하면 결과는 BFS와 동일합니다.

public void PrintLevelNodes(Tree root, int level) {
    if (root != null) {
        if (level == 0) {
            Console.Write(root.Data);
            return;
        }
        PrintLevelNodes(root.Left, level - 1);
        PrintLevelNodes(root.Right, level - 1);
    }
}

for (int i = 0; i < depth; i++) {
    PrintLevelNodes(root, i);
}

나무의 깊이를 찾는 것은 케이크 한 조각입니다.

public int MaxDepth(Tree root) {
    if (root == null) {
        return 0;
    } else {
        return Math.Max(MaxDepth(root.Left), MaxDepth(root.Right)) + 1;
    }
}

답변

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

답변

나는 매우 아름다운 재귀 (기능조차도) 너비 우선 탐색 관련 알고리즘을 발견했습니다. 내 생각은 아니지만이 주제에서 언급해야한다고 생각합니다.

크리스 오카 사키 (Chris Okasaki)는 ICFP 2000의 http://okasaki.blogspot.de/2008/07/breadth-first-numbering-algorithm-in.html 에서 ICFP 2000의 너비 우선 번호 매기기 알고리즘을 3 장의 그림으로 매우 명확하게 설명합니다 .

http://debasishg.blogspot.de/2008/09/breadth-first-numbering-okasakis.html 에서 찾은 Debasish Ghosh의 Scala 구현 은 다음과 같습니다.

trait Tree[+T]
case class Node[+T](data: T, left: Tree[T], right: Tree[T]) extends Tree[T]
case object E extends Tree[Nothing]

def bfsNumForest[T](i: Int, trees: Queue[Tree[T]]): Queue[Tree[Int]] = {
  if (trees.isEmpty) Queue.Empty
  else {
    trees.dequeue match {
      case (E, ts) =>
        bfsNumForest(i, ts).enqueue[Tree[Int]](E)
      case (Node(d, l, r), ts) =>
        val q = ts.enqueue(l, r)
        val qq = bfsNumForest(i+1, q)
        val (bb, qqq) = qq.dequeue
        val (aa, tss) = qqq.dequeue
        tss.enqueue[org.dg.collection.BFSNumber.Tree[Int]](Node(i, aa, bb))
    }
  }
}

def bfsNumTree[T](t: Tree[T]): Tree[Int] = {
  val q = Queue.Empty.enqueue[Tree[T]](t)
  val qq = bfsNumForest(1, q)
  qq.dequeue._1
}

답변

바보 같은 방법 :

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