자바스크립트 트리의 순차 순회

이 순회 방법에서는 왼쪽 하위 트리를 먼저 방문한 다음 루트를 방문한 다음 오른쪽 하위 트리를 방문합니다. 모든 노드가 하위 트리 자체를 나타낼 수 있음을 항상 기억해야 합니다.

이진 트리가 순서 순회되는 경우 , 출력은 오름차순으로 정렬된 키 값을 생성합니다.

우리는 A,에서 시작합니다. 그리고 in-order traversal에 이어 왼쪽 하위 트리 B로 이동합니다. 나 도 순서대로 순회합니다. 모든 노드를 방문할 때까지 프로세스가 계속됩니다. 이 트리의 중위 순회 출력은 다음과 같습니다. -

D → B → E → A → F → C → G

이것이 우리가 구현할 알고리즘입니다 -

• 왼쪽 하위 트리를 재귀적으로 순회
• 노드 데이터 인쇄
• 오른쪽 하위 트리를 재귀적으로 순회

클래스에서 구현하는 방법을 살펴보겠습니다. 사용자가 스스로 루트를 전달하는 것을 원하지 않기 때문에 클래스 외부에 도우미 함수를 다시 만들 것입니다.

inOrder() {
inOrderHelper(this.root);
}

도우미 기능 -

예시

function inOrderHelper(root) {
   if (root !== null) {
      inOrderHelper(root.left);
      console.log(root.data);
      inOrderHelper(root.right);
   }
}

−

예시

let BST = new BinarySearchTree();
BST.insertRec(10);
BST.insertRec(15);
BST.insertRec(5);
BST.insertRec(50);
BST.insertRec(3);
BST.insertRec(7);
BST.insertRec(12);
BST.inOrder();

출력

이것은 출력을 줄 것입니다 -

3
5
7
10
12
15
50

요소는 정렬된 순서로 인쇄되었습니다. 이는 왼쪽 서브트리를 재귀적으로 먼저 탐색하기 때문에 가장 작은 값을 먼저 얻기 때문입니다. 이것은 끝까지 계속되고 모든 요소를 ​​정렬된 순서로 가져옵니다.