[DataStructure] 자바스크립트로 구현하는 '트리' 자료구조 (1) 이진트리

트리 자료구조의 필요성 

 

- 트리 자료구조는 결리스트의 검색 시, 노드의 처음부터 찾아가야하는 단점을 보완했음. 이진탐색의 장점을 활용함. 

 

트리 자료구조 실생활 예시 

 

- 회사나 정부의 조직도

- 나라, 지방, 시•군별, 계층적인 데이터의 저장 

- 인덱스

- DOM Tree 

 

이진트리의 조건 

 

- 모든 노드는 왼쪽 가지에 포함되는 어떤 숫자보다도 큰 숫자가 된다.

- 모든 노드는 그 노드의 오른쪽 가지에 포함되는 어떤 숫자보다 작은 숫자가 된다. 

 

용어 

- 노드

 

- 루트노드 : 가장 꼭대기 노드. 

- 노드 : 트리 구조에서의 기본 데이터 저장 단위. 

- 리프 노드 : 차수가 0인 노드, 즉 맨 끝에 달린 노드를 말함. 

 

- 관련 용어 

 

- 차수 : 선택한 노드의 부속 트리의 개수를 말함. 

- 트리의 차수 : 전체 트리의 최대 차수를 말함. 

- 부모 : 부속 트리를 가진 노드. 

- 자식 : 자신의 바로 상위 노드에 속하는 부속노드. 

- 형제 : 부모가 같은 자식 노드. 

- 조상 : 노드의 부모 노드들의 총 집합. 

- 자손 : 노드의 부속 트리에 있는 모든 노드들. 

- 레벨 : 루트 노드들로부터의 깊이. 

- 트리의 깊이 : 트리에 속한 노드의 최대 레벨. 

 

필요한 메소드 

- 필수

- add ( )

- remove ( ) -> 추가할 예정

- get ( ) -> 추가할 예정

 

- 기타

 

코드

 

console.log("세번째 구현하기");

function Tree(){
    this.root = null;
}

function Node(data){
    this.data = data;
    this.left = null;
    this.right = null;
}

function _add(root, node){
    
    if(!root){
        return node;
    }

    if(root.data > node.data){
        root.left = _add(root.left, node);
        return root;
    } else if(root.data < node.data) {
        root.right = _add(root.right, node);
        return root;
    } else {
        throw("같은 값을 추가할 수 없습니다.");
    }
}

Tree.prototype.add = function (data){
    let newNode = new Node(data);

    if(!this.root){
        this.root = newNode;
    } else {
        _add(this.root, newNode);
    }

    return newNode;
}

Tree.prototype.preOrderTraversal = function (root){

    if(!root){
        return ;
    }

    console.log(root.data);
    this.preOrderTraversal(root.left);
    this.preOrderTraversal(root.right);
}

Tree.prototype.inOrderTraversal = function (root){
    
    if(!root){
        return ;
    }

    this.inOrderTraversal(root.left);
    console.log(root.data);
    this.inOrderTraversal(root.right);
}

Tree.prototype.postOrderTraversal = function (root){

    if(!root){
        return ;
    }

    this.postOrderTraversal(root.left);
    this.postOrderTraversal(root.right);
    console.log(root.data);
}

Tree.prototype.getRoot = function (){
    return this.root;
}

const main = function () {
    const testTree = new Tree();
    testTree.add(5);
    testTree.add(3);
    testTree.add(7);
    testTree.add(2);
    testTree.add(4);
    testTree.add(6);
    testTree.add(8);

    console.log("전위순회 시작합니다!");
    testTree.preOrderTraversal(testTree.getRoot());
    
    console.log("중위순회 시작합니다!");
    testTree.inOrderTraversal(testTree.getRoot());

    console.log("후위순회 시작합니다!");
    testTree.postOrderTraversal(testTree.getRoot());
}

main();