이진 트리 순회 구현해보기

각각의 노드가 최대 두개의 자식 노드를 가지는 트리 자료 구조를 순회하는 방법

구현 메서드

• 노드 추가: BinaryTree._insertNode(), BinaryTree.insert()
• 전위 순회: BinaryTree._preOrederTraverseNode(), BinaryTree.preOrderTraverse()
• 중위 순회: BinaryTree._inOrderTraverseNode(), BinaryTree.inOrderTraverse()
• 후위 순회: BinaryTree._postOrderTraverseNode(), BinaryTree.postOrderTraverse()
• 층별 순회: BinaryTree.levelOrderTraverse()

1. _insertNode() ⇒ 내부 함수, insert()

** insertNode()의 경우 사용자가 어떤 방식으로 이루어지는지 알지 못해도 되는 내부 함수이므로 를 이용해 private로 나타낸다.

1) node가 null이면 새로운 node 객체를 만든다.

2) node가 존재하고, 새로 넣을 value가 기존의 node의 value보다 작다면 재귀를 통해 가장 왼쪽에 위치하도록 한다.

3) node가 존재하고, 새로 넣을 value가 기존의 node의 value보다 크다면 재귀를 통해 가장 오른쪽에 위치하도록 한다.

_insertNode (node, value) {
        if (node === null) {
            node = new Node(value);
        } else if (value < node.value) {
            node.left = this._insertNode(node.left, value);
        } else if (value > node.value) {
            node.right = this._insertNode(node.right, value);
        }
    }

    insert (value) {
        this.root = this._insertNode(this.root, value);
    }

2. 전위 순회 (_preOrderTraverseNode())

전위 순회의 경우 노드(N) → 노드의 왼쪽(L) → 노드의 오른쪽(R)으로 방문한다.

그렇기 때문에 함수를 프린트하는 callback메서드를 1. 노드, 2. 노드의 왼쪽, 3. 노드의 오른쪽 순서대로 호출한다.

_preOrderTraverseNode (node, callback) {
        if (node === null) return;
        callback(node);
        this._preOrderTraverseNode(node.left, callback);
        this._preOrderTraverseNode(node.right, callback);
    }

    preOrderTraverse (callback) {
        this._preOrderTraverseNode(this.root, callback);
    }

3. 중위 순회 (_inOrderTraverseNode())

중위 순회의 경우 노드의 왼쪽(L) → 노드(N) → 노드의 오른쪽(R)으로 방문한다.

_inOrderTraverseNode (node, callback) {
        if (node === null) return;
        this._inOrderTraverseNode(node.left, callback);
        callback(node);
        this._inOrderTraverseNode(node.right, callback);
    }

    inOrderTraverse (callback) {
        this._inOrderTraverseNode(this.root, callback);
    }

4. 후위 순회 (_postOrderTraverseNode())

후위 순회의 경우 노드의 왼쪽(L) → 노드의 오른쪽(R) → 노드(N) 순으로 방문한다.

_postOrderTraverseNode (node, callback) {
        if (node === null) return;
        this._postOrderTraverseNode(node.left, callback);
        this._postOrderTraverseNode(node.right, callback);
        callback(node);
    }

    postOrderTraverse (callback) {
        this._postOrderTraverseNode(this.root, callback);
    }

5. 층별 순회 (levelOrderTraverse())

층별 순회는 Queue를 이용한다.

1) 가장 처음에 root를 큐에 넣는다.

2) queue가 비어있지 않을 때까지 처음에는 가장 먼저 들어있는 queue의 node를 print한다.

3) 해당 node의 left와 right를 순서대로 queue에 넣고, 비어있지 않을 때까지 반복한다.

levelOrderTraverse (callback) {
        let q = new Queue();
        let node;
        q.enequeue(this.root);
        while (!q.isEmpty()) {
            node = q.dequeue();
            callback(node);
            if (node.left !== null) q.enqueue(node.left);
            if (node.right !== null) q.enquque(node.right);
        }
    }

6. callback - printNode

function printNode(node) {
	process.stdout.write(`${node.value} -> `);
}

관련 전체 코드는 Git에 업로드 해두었습니다.
Github_tree