트리와 이진트리

<트리의 기본적인 용어>

노드 : 데이터를 담는 가장 작은 단위
edge : 각 노드를 연결하는 선
루트노드 : 트리에서 최상위 노드
자식노드가 없는 노드 : 터미널 노드
인터널 노드 : 루트노드, 터미널 노드를 제외한 나머지 노드

<트리의 레벨과 높이>

트리의 레벨 : 루트노드부터 레벨 1, 아래로 내려갈 수록 1씩 증가함
트리의 높이 : 트리에서 가장 높은 레벨

<트리의 종류>

이진트리(Binary Tree)

• 각각의 노드가 최대 2개의 자식 노드를 가질 수 있는 트리

포화 이진트리

• 트리의 자식노드가 모두 2개인 트리, 더이상의 노드를 추가할 수 없음

완전 이진트리

• 최대 레벨을 제외한 나머지 레벨에는 모두 채워져 있어야 하고, 최대 레벨의 노드들은 왼쪽부터 채워진 트리

<이진트리의 추상자료형>

getData() - 해당트리(노드)의 데이터 리턴
setData(data) - 해당 트리(노드)의 데이터 설정
getLeftSubTree() - 해당 트리(노드)의 왼쪽 서브 트리 리턴
getRightSubTree() - 해당 트리(노드)의 오른쪽 서브 트리 리턴
setLeftSubTree(tree) - 해당 트리(노드)의 왼쪽 서브 트리를 tree로 설정
setRightSubTree(tree) - 해당 트리(노드)의 오른쪽 서브 트리를 tree로 설정

<트리를 순회하며 출력하기 위한 함수>

preOrderTraversal() - 전위순회 (1->2->3)
inOrderTraversal() - 중위순회 (2->1->3)
postOrderTraversal() - 후위순회 (2->3->1)

<이진트리 구현코드>

class BinaryTree{
    constructor(data, leftTree = null, rightTree = null){
        this.data=data;
        this.leftSubTree = leftTree;
        this.rightSubTree = rightTree;
    }
    getData(){
        return this.data;
    }
    setData(data){
        this.data=data;
    }
    getLeftSubTree(){
        return this.leftSubTree;
    }
    getRightSubTree(){
        return this.rightSubTree;
    }
    setLeftSubTree(tree){
        this.leftSubTree = tree;
    }
    setRightSubTree(tree){
        this.rightSubTree = tree;
    }
    preOrderTraversal(tree){
        if (tree == null) return;
        console.log(tree.data);
        this.preOrderTraversal(tree.getLeftSubTree());
        this.preOrderTraversal(tree.getRightSubTree());
    }
    inOrderTraversal(tree){
        if(tree == null) return ;
        this.inOrderTraversal(tree.getLeftSubTree());
        console.log(tree.data);
        this.inOrderTraversal(tree.getRightSubTree());
    }
    postOrderTraversal(tree){
        if(tree == null) return ;
        this.postOrderTraversal(tree.getLeftSubTree());
        this.postOrderTraversal(tree.getRightSubTree());
        console.log(tree.data);
    }

}