들어가기 전에, 개념 정리

1. Tree 개념 정리

• 데이터의 linked list
• node: 데이터 저장 공간
• branch(link): 노드에 저장되어있는 포인터 (간선)
• depth(height, level): 루트 노드로부터 거리
• degree(fanout): 각 노드의 간선 개수
  • 트리의 크기가 N일 때, 전체 간선의 개수는 N-1
• 트리의 종류:
  "사진 첨부"

---

2. 노드 접근 방식

1. Deth-First(Traversal/Search)(DFS: 깊이 우선 탐색)

1. Inorder Traversal

2. Postorder Traversal

3. Preorder Traversal

2. Breadth-First(Traversal/Search)(BFS: 너비 우선 탐색)

Level Order Traversal

그래서 오늘은,,,, DFS 중 Inorder Traversal를 탐구해보겠습니다!!

---

DFS - Inorder Traversal

• 왼쪽 -> 중간 -> 오른쪽

• Binary Tree일 때만 성립 가능

  1. root가 null이면, 다음을 반환..
  2. Inorder Traversal (루트 -> 왼쪽으로 이동)
  3. Process Root (루트 출력)
  4. Inorder Traversal (루트 -> 오른쪽으로 이동)

• 예시:
  

// JavaScript
// 이진 트리 구조
class Node {
    constructor(v) {
        this.data = v;
        this.left = null;
        this.right = null;
    }
}

function printInorder(node) {
  	// 트리가 비어있거나 리프 노드의 자식인 경우,빈 값 반환
    if (node === null) {
        return;
    }
    
    // 노드의 왼쪽으로 이동
    printInorder(node.left);
    
    // 해당 노드값 출력
    console.log(node.data);
    
    // 노드의 오른쪽으로 이동
    printInorder(node.right);
}

// 노드 입력
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.right = new Node(6);

// Function call
printInorder(root); // 4 2 5 1 3 6

TIL:

• constructor(생성자): 자바 생각하셈
  • 클래스의 인스턴스 객체를 생성함
  • key,value 개념
  • this.XXX: 키 값을 할당
  • new 생성자명을 통해 객체(인스턴스) 생성 (속성값을 물려준다.)

+) 참고 자료:
https://www.geeksforgeeks.org/inorder-traversal-of-binary-tree/?ref=header_outind