자료구조 - 트리, 이진 트리, 이진 탐색 트리, 트리 순회, JS 트리 구현

1. 트리(tree) 란?

트리는 계층적인 자료를 표현하는 데 사용되는 자료구조입니다.

tree

1. Node

tree의 각 요소 ( A, B, C, D.... 와 같은) 를 노드 (Node) 라고 부릅니다.

B를 A의 자식 노드, A를 B의 부모 노드 라고 합니다.

각 Node는 자신의 데이터를 가지고 있으며, 자식 노드의 주소를 가지고 있을 수도 있습니다.

 

2. Root Node

A와 같이 부모 노드가 없고 최상단에 위치한 Node를 루트 노드( Root Node ) 라고 합니다.

 

3. Leaf Node

H, I, E, J, G 처럼 자식 노드가 없는 Node를 단말 노드( Leaf Node ) 라고 합니다.

 

4. size

모든 Node의 갯수를 크기(size) 라고 합니다. (ex. size: 10)

 

5. depth

Root Node로부터의 거리를 깊이(depth) 라고 합니다. (ex. B, C: 1  /  D, E, F, G: 2) 

 

 

---

2. 이진 트리(binary tree) 란?

자식 노드의 갯수가 최대 2개로 한정된 tree를 말합니다.

binary tree

최대 자식 노드 갯수가 2개인것 뿐이므로 
위 그림에서 G 노드가 없어도 이진 트리입니다.

 

---

3. 이진 탐색 트리(binary search tree) 란?

이진 탐색이 동작할 수 있도록 고안된 자료구조의 일종입니다.

왼쪽 자식 노드가 부모 노드보다 작고

오른쪽 자식 노드가 부모 노드보다 큰 이진 트리를 말합니다.  

왼쪽 자식 < 부모 < 오른쪽 자식

binary search tree

위와 같은 조건이 성립하면

원하는 값을 찾고 싶을 때 해당 값을 Root node의 값과 비교하여

왼쪽 혹은 오른쪽으로 탐색 해 나갈 수 있습니다.

(ex. Root node의 값인 10을 기준으로  11은 오른쪽에 있다는 것을 확신하고 검색할 수 있습니다.)

 

---

4. 트리 순회(Tree Travercal) 란?

트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법을 의미합니다.

보통 자신을 출력하는 방법과 같이 방문한 노드를 시각적으로 확인 가능합니다.

---

대표적인 트리 순회 방법은 3가지가 있습니다.

예제 tree

1. In order / 중위 순회  ( Left - Root - Right )

왼쪽 노드부터 출력합니다.

이후 Root 노드를 출력합니다.

이후 오른쪽 노드를 출력합니다.  

 

예제를 중위 순회 하면 D-B-E-A-F-C-G 입니다.

 

 

2. pre order / 전위 순회 ( Root - Left - Right )

Root 노드를 먼저 출력합니다.

이후 왼쪽 오른쪽 순으로 출력합니다.

 

예제를 전위 순회 하면 A-B-D-E-C-F-G 입니다.

 

 

3. post order / 후위 순회 ( Left - Right - Root ) 

왼쪽 노드부터 출력합니다.

이후 오른쪽 노드를 출력합니다.

이후 Root 노드를 출력합니다.

 

예제를 후위 순회 하면 D-E-B-F-G-C-A 입니다.

 

---

4-1. 트리 순회 직접 구현

 

1. node 클래스

class Node {
  constructor() {
    this.left = null;
    this.value = null;
    this.right = null;
  }
}

 

2. tree 클래스

class Tree {
  contructor() {
    this.root = null;
  }

  setRoot(node) {
    this.root = node;
  }
  getRoot() {
    return this.root;
  }
  makeNode(left, value, right) {
    const node = new Node();
    node.left = left;
    node.value = value;
    node.right = right;
    return node;
  }

  inorder(node) {
    if (node !== null) {
      this.inorder(node.left);
      console.log(node.value);
      this.inorder(node.right);
    }
  }

  preorder(node) {
    if (node != null) {
      console.log(node.value);
      this.preorder(node.left);
      this.preorder(node.right);
    }
  }

  postorder(node) {
    if (node != null) {
      this.preorder(node.left);
      this.preorder(node.right);
      console.log(node.value);
    }
  }
}

 

3. 각 순회 함수 실행 결과

 

in oreder

 

---

pre order

---

post order