SEB Section 2 Tree

Tree

트리는 나무를 거꾸로 뒤집어 놓은 듯한 모습을 가지고 있다.

• 특징
  • 그래프의 여러 구조중 하나로 단방향 그래프이다.
  • 데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결된 계층적 자료구조이다.
  • 하나의 데이터 아래에 여러개의 데이터가 존재할 수 있는 비선형 구조이다.

• 루트라는 최상단 노드가 존재한다.
• 각 데이터를 노드라 한다.
• 상하 계층으로 연결되면, 상단의 노드는 부모, 하단의 노드는 자식의 관계가 된다.

• 자식이 없는 노드는 리프 노드라 한다.

• 용어
  • 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
  • 루트(Root) : 트리 구조의 시작점이 되는 노드
  • 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
  • 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
  • 리프(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드

Tree는 깊이와 높이, 레벨 등을 측정할 수 있다.

• 깊이 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현할 수 있다.

• 레벨 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현할 수 있다. 같은 레벨에 나란히 있는 노드를 형제 노드라 부른다.

• 높이 리프 노드를 기준으로 루트까지의 높이를 표현 할 수 있다.

• 서브 트리 루트에서 뻗어 나오는 큰 트리 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리라 부른다.

class Node {
  constructor(content, children = []) {
    this.content = content;
    this.children = children;
  }
}

const tree = new Node("hello", [
  new Node("world"),
  new Node("and"),
  new Node("fun", [new Node("javascript!")]),
]);

function traverse(node) {
  console.log(node.content);
  for (let child of node.children) {
    traverse(child);
  }
}

traverse(tree);