Tree

트리(Tree)란?

• Tree란 선형 데이터 구조인 배열, 연결 목록, 스택 및 큐와 달리 계층적인 데이터 구조이다.
• 트리의 최상위 노드를 루트라고 하며 요소 바로 아래에 있는 요소를 자식이라고 한다.
• 아래 예시에서 d는 b의 자식이며, d는 b의 부모이다. 마지막에 자식이 없는 요소는 잎(leaf)이라고한다.

      tree
      ----
       a    <-- 루트(root)
     /   \
    b      c  
  /   \      \
 d     e      f    <-- 잎(leaf)

---

트리를 사용하는 이유

• 트리를 사용하는 이유는 계층을 자연스럽게 형성하는 정보를 저장하기를 원하기 때문일 수 있다.
• 트리는 적당한 액세스와 검색( linked list보다 빠르고 array보다 느림)을 제공한다.
• 트리는 중간 정도의 삽입/삭제 기능을 제공한다.( array보다 빠르고 linked list보다 느림).
• 연결 목록과 마찬가지로 배열과 달리 트리는 노드가 포인터를 사용하여 연결되기 때문에 노드 수에 상한선이 없다.

---

이진 트리(Binary Tree)

• 요소에 최대 2개(left, right)의 자식이 있는 트리를 이진 트리라고 한다.
• 이진 트리의 각 요소는 2개의 자식만 가질 수 있으므로 일반적으로 왼쪽 및 오른쪽 자식으로 이름을 지정한다.

---

Binary Tree를 Node로 생성

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

// 자바스크립트로 이진 트리 만드는 법

// 트리의 root
let root = null;

/* 루트 노드 생성 */
root = new Node(1);

/*
    현재 트리의 상태

      1
    /   \
    null  null
*/

root.left = new Node(2);
root.right = new Node(3);

/* 
    2는 왼쪽 노드 3은 오른쪽 노드가 되며 1의 children 이 된다.
           1
        /     \
       2        3
     /   \     /  \
    null null null null  
*/
root.left.left = new Node(4);
/* 
    4는 2의 왼쪽 child가 된다.
                1
            /       \
           2          3
         /   \       /  \
        4    null  null  null
      /   \
    null null
*/

---

사용된 전체 코드

https://github.com/rkdden/Data-Structure/blob/main/tree.js

GitHub - rkdden/Data-Structure

출처

https://www.geeksforgeeks.org/binary-tree-set-1-introduction/?ref=lbp 

Binary Tree | Set 1 (Introduction) - GeeksforGeeks