Tree traversal

ある特定の目的のために、ウィハトリのすべてのノードに1回アクセスすることをツリーツアーと呼ぶ.
階層構造の特殊性のため,すべてのノードを遍歴する方法には多くの種類がある.
木の巡り方は大きく分けて前列巡り、中列巡り、後列巡りの3種類があります.
前、中、後の基準はルートで、ルートがどこに置かれているかによって、ツアーの仕方が異なります.
このような巡り方とは異なり、巡りの順番はいつも左から右へ.

前衛巡査(Preorder)

最初にアクセスするノードはルートノードです.ルートを基準に左側のノードを見学した後,左側のノード探索が終了した後に右側の探索を行う.

中尉巡り

中央を巡回する.左端のノードから巡回を開始し、ルートを基準として左端のノード巡回が終了した後、ルートを介して右端のノードに移動し、ナビゲーションを続行します.

後列巡回(Postorder)

最後の巡回ルート.左端のノードから巡視を開始し,経路を経ずに右に移動し,巡視後,最後に経路を訪問する.

バイナリ検索ツリー実装

class BinarySearchTree {
  constructor(value) {
    // constructor로 만든 객체는 이진 탐색 트리의 Node가 된다.
    this.value = value;
    this.left = null;
    this.right = null;
  }
  insert(value) { // 이진 탐색 트리의 삽입하는 메서드
    // 입력값을 기준으로, 현재 노드의 값보다 크거나 작은 것에 대한 조건문이 필요
    // 보다 작다면, Node의 왼쪽이 비어 있는지 확인 후 값을 넣는다.
    if(value < this.value) {
      if(this.left === null) {
        this.left = new BinarySearchTree(value);
      } else {
        // 비어 있지 않다면 해당 노드로 이동하여 처음부터 다시 크거나 작은 것에 대한 조건문을 확인
        this.left.insert(value);
      }
      // 보다 크다면, Node의 오른쪽이 비어 있는지 확인 후 값을 넣는다.
    } else if(value > this.value) {
      if(this.right === null) {
        this.right = new BinarySearchTree(value);
      } else {
        this.right.insert(value);
      }
    } else {
      // 아무것도 하지 않는다
    }
  }
  constains(value) {
    // 값이 포함되어 있다면 true 반환
    if(value === this.value) {
      return true;
    }
    if(value < this.value) {
      // 현재 노드의 왼쪽이 비어 있지 않고, 노드의 값이 입력값과 일치하면 true
      // 일치하지 않다면 왼쪽 노드로 이동하여 다시 탐색
      if(this.value === null) {
        return false;
      } else {
        return this.left.contains(value)
      }
    }
    if(value > this.value) {
      // 현재 노드의 오른쪽이 비어 있지 않고, 노드의 값이 입력괎과 일치하면 true
      // 일치하지 않다면 오른쪽 노드로 이동하여 다시 탐색
      if(this.right === null) {
        return false;
      } else {
        return this.right.contains(value)
      }
    }
    // 없다면 false 반환
    else {
      return false;
    }
  }
  // 트리의 순회 구현
  // 이진 탐색 트리를 전위 순회하는 메서드
  preorder(callback) {
    callback(this.value);
    if(this.left) {
      this.left.preorder(callback);
    };
    if(this.right) {
      this.right.preorder(callback);
    };
  }
  // 이진 탐색 트리를 중위 순회하는 메서드
  inoder(callback) {
    if(this.left) {
      this.left.inoder(callback);
    };
    callback(this.value);
    if(this.right) {
      this.right.inoder(callback);
    };
  }
  // 이진 탐색 트리를 후위 순회하는 메서드
  postoder(callback) {
    if(this.left) {
      this.left.postoder(callback);
    }
    if(this.right) {
      this.right.posroder(callback);
    }
    callback(this.value);
  }
}

BFS / DFS

グラフィックのブラウズは、1つの頂点から、グラフィック内のすべての頂点を1回(ブラウズ)することを目的としています.
グラフィックのデータは配列のように整然と並んでいないので、必要な資料を見つける前に、一つ一つアクセスして検索します.
グラフィックのすべての頂点ブラウズ方法には、1つではなく多くの方法があります.その中で最も代表的なのは2つです.(DFSとBFS)
この2人ともどのような順序で探索しているのか、すべての資料を確認しただけなのは同じです.

例

韓国からアメリカへのフライトを予定している場合、様々な旅の中で最も短いルートを知りたいのですが、どうすればいいですか?

Breathed First Search

韓国を基準に、最近の頂点から米国のやり方を確認する.
探索可能な頂点がなくなると、次の間隔を置いた頂点が巡回されます.
このように幅を優先的に探索する方法をBreadth−First Searchといい,幅優先探索と呼ぶ.
主に2つの頂点間の最短パスを探すために使用されます.
すべてのパスに1つずつアクセスする場合、最悪の場合、すべてのパスが表示される可能性があります.

Depth First Search

どの道がアメリカに行くのか分からないので、一つの道を探索した後、アメリカに到着しなければ、次の道に回って探索します.
このように深さを優先的に探索する方法をDepth−First Searchといい,深さ優先探索である.
頂点から開始し、次のパスに移行する前に、パスを完全にナビゲートする場合に使用します.
ブラウズ時間がBFSより遅くても、すべてのノードを完全にブラウズできます.
BFSを使ってナビゲートすると、最初のパスがアメリカに行ったとしても、すべてのパスを確認しなければならないという不祥事が発生します.

BFSとDFSはすべての頂点に一度だけアクセスする共通点があるが,それらの使用時の長所と短所は明らかであるため,状況に合った技術を使用しなければならない.