이진트리란?

자식노트가 최대 두 개인 노드들로 구성된 트리
선택지가 2가지이기 때문에 왼쪽 or 오른쪽을 계속 택하는 방식

이진트리의 종류

• 정 이진 트리(Full binary tree) : 각 노드가 0개 혹은 2개의 자식 노드를 갖습니다.(1개는 안된다)
• 포화 이진 트리(Perfect binary tree) : 정 이진 트리이면서 완전 이진 트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다.
• 완전 이진 트리(Complete binary tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리란?

이진 탐색(binary search)과 연결 리스트(linked list)를 결합한 이진트리를 말합니다.
//보통 탐색은 있는지 없는지 확신을 할 수 없어서 더 어렵다?

이진탐색트리 특징

각 노드에 중복되지 않는 키(Key)가 있습니다.
루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있습니다.
루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있습니다.
좌우 서브트리도 모두 이진 탐색 트리여야 합니다.

이진 탐색 트리 특징

이진 탐색 트리는 기존 이진 트리보다 탐색이 빠르다는 장점이 있습니다. 이진 탐색 트리의 연산은 트리의 높이가 h(height)라면 o(h)의 복잡도를 가지게 됩니다. 이와 같은 효율적인 연산이 가능한 이유는 탐색 과정에 있습니다.

이진 탐색 트리의 탐색과정

루트 노드의 키와 찾고자 하는 값을 비교합니다. 만약 찾고자 하는 값이라면 탐색을 종료합니다.
찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행합니다.
찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색을 진행합니다.
이 과정을 찾고자 하는 값을 찾을 때까지 반복해 진행합니다. 만약 값을 찾지 못한다면 그대로 연산을 종료하게 됩니다. 이러한 탐색 과정을 거치면 최대 트리의 높이(h)만큼 탐색을 진행합니다.

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 합니다.
순회방식
1.전위순회
루트가 가장 먼저 방문되므로 시작이 루트부터 시작하여 왼->오로 노드를 탐색

2.중위순회
시작은 제일 왼쪽끝에있는 노트부터 순회하며 왼쪽이 탐색이 다끝나면 루트를 거쳐 오른쪽을 탐색

3.후위 순회
제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문합니다

이진탐색트리 구현

순서
1.class로 노드 만들기
2.자식노드가 루트노드보다 작은지 큰지에 따라 갈리므로 if문으로 조건에 따라 설정을 해준다

• 작으면 왼쪽,크면 오른쪽
  *만약 자식노드에 값이 없으면 new 즉 class를 이용하여 새로운 노드를 만들고 새값과 함께 자식노드에 할당

• 값이 있으면 insert를 재귀로 호출해 값이 없을때까지 실행
  3.위에서 트리구조를 만들었으므로 값이 있는지를 찾는 과정

  class BinarySearchTree {
   constructor(value) {
  		// constructor로 만든 객체는 이진 탐색 트리의 Node가 됩니다.
     this.value = value;
     this.left = null;//없는걸 나타내기 위해?
     this.right = null;
   }
  
  	// 이진 탐색 트리의 삽입하는 메서드를 만듭니다.
   insert(value) {
     if (value < this.value) {
       if (this.left === null) {
         this.left = new BinarySearchTree(value)//없다면 new로 새로운 노드륾 만들어 왼쪽에 넣어준다
       } else {
         this.left.insert(value)//만약 있다면 재귀로 호출
       }
     } else if (value > this.value) {
       if (this.right === null) {
         this.right = new BinarySearchTree(value)//만약 루트보다 크지만 right가 null이면 새로운 노드를 만들어 오른쪽에 넣는다
       } else {
         this.right.insert(value)//위랑 같다
       }
  		//그것도 아니라면, 입력값이 트리에 들어 있는 경우입니다.
     } else {
      
       //이건...위에경우 모두다 아니면 value가 있을때를 의미?
     }
   }
  
   contains(value) {
     if (this.value === value) {
       return true; //맞는 값이 있다면 true
     }
  		
     if (value < this.value) {//찾는 value값이 노드의 this.value보다 작을 때
  		// return !!(this.left && this.left.contains(value))
         //자바스크립트에서 느낌표두개(!!)는 다른 타입의 데이터를 boolean 타입으로 명시적으로 형 변환(Type Conversion)하기 위해 사용->return을 바로 쓸수 있는 이유 이렇게하면 바로 불린타입이 나오는군..
  	//&&헷갈리는 점 
       if(this.left.value ===value) return true
       else {this.left.contains(value)}
     }
  
  		// 입력값을 기준으로 현재 노드의 값보다 큰지 판별하는 조건문이 있어야 합니다.
     if (value > this.value) {
  			//만약 비어있으면 contain재귀 발동?
  			return !!(this.right && this.right.contains(value))
  			// TODO:일치하지 않다면 오른쪽 노드로 이동하여 다시 탐색합니다. 
  
     }
  		
   }
  
  	
  	// 이진 탐색 트리를 전위 순회하는 메서드를 만듭니다.
   preorder(callback) {
  		callback(this.value);//전위는 먼저 루트가 실행이됨
     if (this.left) {
       this.left.preorder(callback)
     };
     if (this.right) {
       this.right.preorder(callback)
     };
   }
  
  	// 이진 탐색 트리를 중위 순회하는 메서드를 만듭니다.
   inorder(callback) {
  		
     	
     if (this.left) {
       this.left.inorder(callback)
     };
     callback(this.value);
     if (this.right) {
       this.right.inorder(callback)
     };
   }
  
  	// 이진 탐색 트리를 후위 순회하는 메서드를 만듭니다.
   postorder(callback) {
  		//TODO: 전위 순회를 바탕으로 후위 순회를 구현하세요.
     if (this.left) {
       this.left.postorder(callback)
     };
     
     if (this.right) {
       this.right.postorder(callback)
     };
     callback(this.value);
   }

}