이진 트리 (binary tree) 와 이진트리의 순회(traversal)

컴퓨터 과학에서, 이진 트리(二進-, 영어: binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.

연결 리스트를 이용해 이진 트리를 구현해보자.

이진트리 구현

node 구현

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

node를 이용한 Tree구현

class Tree {
    constructor() {
        this.root = null;
    }

    insert(value) {
        const newNode = new Node(value);

        if (!this.root) this.root = newNode;
        else {
            let currentNode = this.root;
            while (true) {
                if (value < currentNode.value) {
                    //Left
                    if (!currentNode.left) {
                        currentNode.left = newNode;
                        return this;
                    }
                    currentNode = currentNode.left;
                } else {
                    //Right
                    if (!currentNode.right) {
                        currentNode.right = newNode;
                        return this;
                    }
                    currentNode = currentNode.right;
                }
            }
        }
    }
}

1. 전위 순회

전위 순회(preorder)는 다음과 같은 방법으로 진행한다.

1. 노드를 방문한다.
2. 왼쪽 서브 트리를 전위 순회한다.
3. 오른쪽 서브 트리를 전위 순회한다.

전위 순회는 깊이 우선 순회(depth-first traversal)라고도 한다.

const preOrderList = [];
const preOrder = (node) => {
    preOrderList.push(node.value);
    if (node.left) preOrder(node.left);
    if (node.right) preOrder(node.right);
};

2. 중위 순회

중위 순회(Inorder)은 다음의 순서로 진행된다.

1. 왼쪽 서브 트리를 중위 순회한다.
2. 노드를 방문한다.
3. 오른쪽 서브 트리를 중위 순회한다.

중위 순회는 대칭 순회(symmetric)라고도 한다.

const inOrderList = [];
const inOrder = (node) => {
    if (node.left) inOrder(node.left);
    inOrderList.push(node.value);
    if (node.right) inOrder(node.right);
};

3. 후위 순회

후위 순회(postorder)는 다음과 같은 방법으로 진행한다.

1. 왼쪽 서브 트리를 후위 순회한다.
2. 오른쪽 서브 트리를 후위 순회한다.
3. 노드를 방문한다.

const postOrderList = [];
const postOrder = (node) => {
    if (node.left) postOrder(node.left);
    if (node.right) postOrder(node.right);
    postOrderList.push(node.value);
};

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EC%88%9C%ED%9A%8C