AHRIBORI.COMv0.9
HomeAbout (2)Javascript (7)CSS (12)React (3)Webpack (1)Java (0)Node.js (4)ElasticSearch (1)자료구조 (8)알고리즘 (6)Selenium (1)Linux (2)Docker (1)Git (1)Tip (4)Issue (1)Memo (3)

[자료구조] 이진 트리(Binary Tree)

아리보리 | 2017.05.29 11:40 | 조회 236 | 추천 0 | 댓글 0

 

 

(1) 이진트리?

이진트리(Binary Tree)란 하나의 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리를 말한다.

어떤 하나의 노드를 부모 노드(parent node)라고 할 때, 왼쪽 자식 노드(left child node)와 오른쪽 자식 노드(right child node)가 존재할 수 있다.

 

(2) 구현

class Node {
    constructor(_data) {
        this.data = _data;
        this.leftChild = null;
        this.rightChild = null;
        this.parent = null;
        this.sibling = null;
    }
}

class BinaryTree {

    //_data를 루트노드로 가지는 BinaryTree 초기화
    constructor(_data) {
        this.root = new Node(_data);
        this.level = 1;
        this.height = 1;
    }
    
    // targetNode의 왼쪽에 _data를 자식 노드로 추가
    insertLeftChildNode(targetNode, _data) {
        if (this.root) {
            const newNode = new Node(_data);
            newNode.parent = this.root;
            if (this.root.rightChild) {
                newNode.sibling = this.root.rightChild;
                this.root.rightChild.sibling = newNode;
            }
            targetNode.leftChild = newNode;
        }
    }
    
    // targetNode의 오른쪽에 _data를 자식 노드로 추가  
    insertRightChildNode(targetNode, _data) {
        if (this.root) {
            const newNode = new Node(_data);
            newNode.parent = this.root;
            if (this.root.leftChild) {
                newNode.sibling = this.root.leftChild;
                this.root.leftChild.sibling = newNode;
            }
            targetNode.rightChild = newNode;
        }
    }

    // 전위 순회(TLR)
    preOrder(node) {
        if (node) {
            console.log(node.data);
            this.preOrder(node.leftChild);
            this.preOrder(node.rightChild);
        }
    }

    // 중위 순회(LTR)
    inOrder(node) {
        if (node) {
            this.inOrder(node.leftChild);
            console.log(node.data);
            this.inOrder(node.rightChild);
        }
    }

    // 후위 순회(LRT)
    postOrder(node) {
        if (node) {
            this.postOrder(node.leftChild);
            this.postOrder(node.rightChild);
            console.log(node.data);
        }
    }
    
    // targetNode의 왼쪽 자식 노드를 반환
    getLeftChildNode(targetNode) {
        return targetNode.leftChild;
    }
    
    // targetNode의 오른쪽 자식 노드를 반환
    getRightChildNode(targetNode) {
        return targetNode.rightChild;
    }

    getRootNode() {
        return this.root;
    }
}

const tree = new BinaryTree(1);

tree.insertLeftChildNode(tree.root, 2);
tree.insertLeftChildNode(tree.root.leftChild, 3);
tree.insertRightChildNode(tree.root, 4);

tree.postOrder(tree.root);