[Data Structure] Tree

트리

노드로 이루어진 자료 구조

• 트리는 하나의 루트노드를 갖는다.
• 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
• 그자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이를 반복적으로 정의된다.
• 사이클이 없는 그래프의 한종류 이다.
• 계층모델이다.

루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
내부(internal) 노드: 단말 노드가 아닌 노드
간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
형제(sibling): 같은 부모를 가지는 노드
노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
트리의 차수(degree of tree): 트리의 최대 차수
트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

이진트리

각노드가 최대 두개의 자식을 갖는 트리
이진트리 순회

• 중위순회 : 왼쪽 -> 루트 -> 오른쪽
• 전위순회 : 루트 -> 왼쪽 -> 오른쪽
• 후위순회 : 왼쪽 -> 오른쪽 -> 트리

소스로 포현해 봅시다.

1. 트리

   insertNode(value) - 트리에 노드를 추가합니다.
   contains(value) - 트리에 해당 노드가 존재하는지 여부를 반환합니다.

class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }

insertNode(value){
  this.children.push(new TreeNode(value));
  //{"children": [{"children": [], "value": 5},"value": null}  children에 노드를 추가 
}

cotails(value){
	if(this.value === value){// 첫번째 객체 안에 value확인
    	return true;
    }else{
      for(let el of this.children){
        if(el.contains(value)){// 재귀로 children안쪽 값 계속 확인
          return true;
        }
      }
    }
  return false;
}

2. 이진탐색트리 (중위순회)

   insert(value) - 이진 탐색 트리에 노드를 추가합니다.
   contains(value) - 이진 탐색 트리에 해당 노드가 존재하는지 여부를 반환합니다.
   inorder(callback) - 이진 탐색 트리를 중위순회 합니다.

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

 insert(value) {//이진 탐색 트리에 노드를 추가합니다.
  if(value < this.value){//들어오는 값이 기존트리보다 작을때
   if(this.left === null){// 왼쪽에 널이 나올때까
     this.left = new BinarySearchTreeNode(value);
   }else{
     return this.left.insert(value);
   }
 }else if(value > this.value){//들어오는값이 기존트리보다 클때
   if(this.right === null){//오른쪽에 널이 나올때까지 
     this.right = new BinarySerchTreeNode(value);
   }else{
     return this.right.insert(value);
   }
 }
}

cotains(value){
  if(this.value === value){//첫번째객체안 value값 확인
    return true;
  }else if(value < this.value){//찾는 값이 현재값 보다 작은지
    if(this.left === null)//값이 없는경우
      return false;
  }else if(this.left.contains(value)){//왼쪽 끝까지 true나올때까지 재귀
    return ture;
  }
}else if(value > this.value){//찾는 값이 현재값 보다 큰지
  if(this.right === null){//값이 없는경우
    return false;
  }else if(this.right.contains(value)){//오른쪽 끝까지 true나올때까지 재귀
    return true;
  }
}
return false;
}

inorder(callback){
  if(this.left !== null){
    this.left.inorder(callback);
  }
  callback(this.value);
  if(this.right !== null){
    this.right.inorder(callback);
  }