[자료구조 정리] 1. Tree

📌 자료구조시간에 배웠던 Tree 구조에 대해 정리를 할 것 이다.

트리란?

하나의 부모노드에 여러개의 자식 노드들이 붙어있는 자료구조이다.
트리의 용어에 대해서 아래에서 설명하겠다.

부모노드 : 상하관계에 있는 노드들 중 상의 위치에 존재하는 노드. 부모노드는 여려개의 자식노드들을 가질 수 있다.

자식노드 : 상하관계에 있는 노드들 중 하의 위치에 존재하는 노드. 자식노드는 하나의 부모노드만 가져야 한다.

리프노드 : 트리구조의 마지막부분이며, 더 이상 자식노드들 가지지 않는 노드

깊이(depth) : 트리 구조의 깊이

위 그림를 예를 들어 설명하자.
부모노드 : [1,2,3,4]
자식노드 : [2,3,4,5,6,7]
리프노드 : [3,5,6,7]
깊이 : 3

코드

// 가장 기본적인 트리구조
// 부모노드 하나의 여러개의 자식 노드들이 존재하는 자료구조이다
class Tree {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
  treeInsert(value) {
    const childNode = new Tree(value);
    this.children.push(childNode);
  }
  search(value) {
    if (this.value === value) {
      return true;
    }
    for (let childNode of this.children) {
      if (childNode.search(value)) {
        return true;
      }
    }
    return false;
  }
}

const a = new Tree(1);
a.treeInsert(7);
a.treeInsert(2);
a.treeInsert(3);
a.treeInsert(4);
a.treeInsert(5);
a.treeInsert(6);
console.log(a);

이진트리란?

위에서 설명한 기본적인 트리구조를 가지지만, 하나의 부모노드에는 반드시 두개 이하의 자식들만 존재한다. 또한 왼쪽 자식 노드는 반드시 부모노드와 루트노드보다 작고, 오른쪽 자식 노드는 반드시 부모노드와 루트노드보다 크다.

Push 코드 작성 순서

부모노드는 반드시 오른쪽 자식노드보단 작아야하고, 왼쪽 자식노드보단 커야한다.

1. 센터, 좌측, 우측 노드를 갖는 구조체 생성.
2. 노드를 push할때 조건에 맞게 push
   2-1. value가 부모노드보다 작을 때 -> 좌측 자식 노드에 가야함
   2-2. value가 부모노드보다 클 때 -> 우측 자식 노드에 가야함.

코드

	class BinaryTree{
      constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;      
      }
      pushNode(value){
        // 부모노드보다 넣는 값이 클 때
        if(this.value < value){
        	if(this.right === null){
              // 오른쪽 자식노드가 존재하지 않을때 -> 바로 오른쪽 자식노드에 넣는다.
              this.right = value;
            }else{
              // 오른쪽 자식노드가 존재할때-> 오른쪽 자식노드에 대해 재귀적으로 다시 push한다.
              this.right.pushNode(value);
            }
        }else if(this.value > value){
          // 부모노드보다 넣는 값이 작을 때
          if(this.left === null){
            // 왼쪽 자식노드가 존재하지 않을때 -> 바로 왼쪽 자식노드에 넣는다.
          	this.left = value;
          }else{
              // 왼쪽 자식노드가 존재할때-> 왼쪽 자식노드에 대해 재귀적으로 다시 push한다.
          	this.left.pushNode(value);
          }
        }else{
          return console.log("이미 존재하는 값입니다.")
        }
      }
    }

Search 코드 작성 순서

1. 찾는 값과 부모노드를 비교한다
   1-1 찾는 값과 부모노드가 같으면 true를 리턴한다.
2. 찾는 값과 부모노드가 다르다.
   2.1 찾는 값보다 부모노드가 작다 -> 부모노드의 오른쪽 자식노드에 대해서 재귀적으로 search 수행
   2.2 찾는 값도가 부모노드가 크다 -> 부모노드의 왼쪽 자식노드에 대해서 재귀적으로 search 수행

코드

	...
	searchNode(value){
      if(this.value === value){
        return true;
      }
      //부모노드보다 찾는 값이 작을 경우
      if(this.value > value){
        if(this.left !== null){
          return this.left.searchNode(value);
        }else{
          return false;
        }
      }
      //부모노드보다 찾는 값이 클 경우
      if(this.value < value){
        if(this.right !== null){
          if(this.right !== null){
          	return this.right.searchNode(value);
          }else{
            return false;
        }
      
      }
    }