[Algorithm] Javascript Tree 자료구조 구현하기 (소스코드 포함)

 

Tree 자료구조 구현하기

 

Tree 자료구조는 데이터를 계층적으로 표현하기 위한 자료구조다. 하나 이상의 노드를 가지고 있으며 각 노드들은 간선(Edge)로 연결된다. 방향성이 있는 비순환 그래프의 한 종류로 3가지 트리 종류가 있다.

 

• 이진 트리(Binary Tree) : 자식 노드 수가 최대 2개인 트리
• 포화 이진 트리(정 이진 트리 Full BInary Tree) : 모든 레벨에서 노드가 꽉 채워진 트리다. 단말노드(Leaf Node)를 제외한 모든 노드의 자식 노드가 2개인 트리. 
• 완전 이진트리(Complete Binary Tree) : 단말노드(Leaf Node)를 제외한 모든 노드가 꽉 채워진 형태의 트리

 

 

Tree 자료구조는 2개의 멤버변수와 2개의 메소드를 가진 클래스로 구현이 가능하다.

 

소스코드

 

class Tree {
	// 생성자 함수
  constructor(value) {
    this.value = value;
    this.children = [];
  }

	// 트리에 새로운 노드를 추가하는 메소드
  insertNode(value) {
    const childNode = new Tree(value);
    this.children.push(childNode);
  }

	// 트리 안에서 노드를 검색하는 메소드
  contains(value) {
    if (this.value === value) {
      return true;
    }
    
    for(let i=0; i<this.children.length; i++){
      const childNode = this.children[i];
      if(childNode.contains(value)){
        return true;
      }
    }
    
    return false;
  }
}

 

 

 

 

[Algorithm] Data Structure Tree , 트리 자료구조란? 이진 탐색 트리 (BST, Binary Search Tree)

 

[Algorithm] 재귀 알고리즘 Tree UI 구현하기