Tree(트리) with JavaScript

* node 에서는 기본적으로 class를 사용하지 못하므로 babel을 사용해야 한다. 적용법은 최하단 링크에 있다. 귀찮으면 아래 링크의 git을 clone을 하시면 된다. 

트리구조 (출처 : https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0)

Tree(트리) : 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다.

최상위 노드를 Root Node, 하위 노드를 Child Node, 최하위 노드를 Leaf Node 라고 한다. 

하나의 노드가 두 개 이하의 자식을 가지는 경우 이진트리(Binaray Tree)라고 한다.

이진 트리의 경우 배열을 통해서 값을 정리하는 것이 가능하다.

• 부모노드 : index/2
• 좌측 자식노드 : index * 2
• 우측 자식 : index * 2 + 1

class Node {
    data;
    right;
    left;

    constructor(data, right, left) {
        this.data = data;
        this.right = right;
        this.left = left;
    }
}

class BinaryTree {
    root;

    constructor(arr) {
        if(typeof arr !== Object){
          return;  
        }else{
            this.makeBTbyArr(arr);
        }
    }

    makeBTbyArr(arr) {
        if ((arr[1] === undefined || arr[1] === null || typeof arr[1] === 'string'))
            return;

        arr.map((each, index) => {
            if (each === undefined || each === null || typeof each === 'string') {
                console.log('node missing in this index');
            } else {
                if (index === 1) this.root = each;
                const lcIndex = Math.floor(index * 2);
                const rcIndex = Math.floor(index * 2 + 1);
                each.left = (lcIndex >= arr.length) ? null : arr[lcIndex];
                each.right = (rcIndex >= arr.length) ? null : arr[rcIndex];
            }
        })
    }

    newNode = (data, right, left) => new Node(data, right, left);

    preOrder = (node) => {
        if (node === undefined || node === null) return 'node is not defined';
        console.log(node.data);
        this.preOrder(node.left);
        this.preOrder(node.right);
    }

    inOrder = (node) => {
        if (node === undefined || node === null) return 'node is not defined';
        this.inOrder(node.left);
        console.log(node.data);
        this.inOrder(node.right);
    }

    postOrder = (node) => {
        if (node === undefined || node === null) return 'node is not defined';
        this.postOrder(node.left);
        this.postOrder(node.right);
        console.log(node.data);
    }

}

function normalbinaryTree() {
    const binaryTree = new BinaryTree();

    const root = binaryTree.newNode('ROOT', null, null);
    const nodeA = binaryTree.newNode('A', null, null);
    const nodeB = binaryTree.newNode(
        'B',
        binaryTree.newNode('C', binaryTree.newNode('E'), binaryTree.newNode('F')),
        binaryTree.newNode('D', binaryTree.newNode('G'), binaryTree.newNode('H')));

    binaryTree.root = root;
    root.left = nodeA;
    root.right = nodeB;

    // 전위, 중위, 후위
    // binaryTree.preOrder(binaryTree.root);
    // binaryTree.inOrder(binaryTree.root);
    // binaryTree.postOrder(binaryTree.root);
}

function binarayTreeWithArray() {
    const nodeArray = [];
    for (let i = 0; i < 10; i++) {
        nodeArray.push(new Node(`Node ${i}`, null, null));
    }
    nodeArray[0] = 'emtpy';
    const binaryTree = new BinaryTree(nodeArray);

        // 전위, 중위, 후위
    // binaryTree.preOrder(binaryTree.root);
    // binaryTree.inOrder(binaryTree.root);
    // binaryTree.postOrder(binaryTree.root);
}


binarayTreeWithArray();
// normalbinaryTree();

 

---

아래의 내 깃허브에서 소스를 볼 수 있다.

https://github.com/iamdap91/basic-data-structure

iamdap91/basic-data-structure

http://jeonghwan-kim.github.io/2016/07/19/babel.html

Babel로 ES6 코드 사용하기