[자료구조] 이진탐색트리 구현 - 중위순회, 전위순회, 후위순회 메소드

중위순회(in-order traversal) : (왼쪽 - 루트 - 오른쪽)

• 오름차순(작은 값에서 큰 값 순)으로 방문된다.
• 트리 정렬 시 사용되는 방법임

 

전위순회(pre-order traversal) : (루트 - 왼쪽 - 오른쪽)

• 자식 노드보다 노드 자신을 먼저 방문한다.
• 구조화된 문서를 출력할 때 많이 이용하는 방법

 

후위순회(post-order traversal) : (왼쪽 - 오른쪽 - 루트)

• 자식 노드를 노드 자신보다 먼저 방문
• 디렉토리와 서브 디렉토리의 파일 용량을 계산할 때 쓰는 방법

 

//in-order traversal 중위순회 (왼쪽 - 루트 - 오른쪽)

    inOrderTraverse(callback){

        this.inOrderTraverseNode(this.root, callback);

    }

    

    inOrderTraverseNode(node, callback){

        if(node !== null){

            this.inOrderTraverseNode(node.left, callback);

            callback(node.key);

            this.inOrderTraverseNode(node.right, callback);

        }

    }



//pre-order traversal 전위순회 (루트 - 왼쪽 - 오른쪽)

    preOrderTraverse(callback){

        this.preOrderTraverseNode(this.root,callback);

    }

    preOrderTraverseNode(node, callback){

        if(node !== null){

            callback(node.key);

            this.preOrderTraverseNode(node.left, callback);

            this.preOrderTraverseNode(node.right, callback);

        }

    }



//post-order traversal 후위순회 (왼쪽-오른쪽-루트)

    postOrderTraverse(callback){

        this.postOrderTraverseNode(this.root, callback);

    }

    postOrderTraverseNode(node, callback){

        if(node !== null){

            this.postOrderTraverseNode(node.left, callback);

            this.postOrderTraverseNode(node.right, callback);

            callback(node.key);

        }

    }

 

사용 방법

예를 들면 callback이 const printValue = (value) =>  console.log(value);

라면 사용할 때 이렇게 함수를 정의해주고 인자로 넣어주면 된다.

 

insert메소드와 순회 메소드까지 구현한 전체 코드와 사용하는 코드는 다음과 같다.

 

class Node{

    constructor(key){

        this.key = key;

        this.left = null;

        this.right = null;

    }

}

class BinarySearchTree{

    constructor(){

        this.root = null;

    }

    insert(key){

        let newNode = new Node(key);

        if(this.root === null){

            this.root = newNode;

        }else{

            this.insertNode(this.root,newNode);

        }

    }

    insertNode(node, newNode){

        if(newNode.key < node.key){

            if(node.left === null){

                node.left = newNode;

            }else{

                this.insertNode(node.left, newNode);

            }

        }else{

            if(node.right === null){

                node.right = newNode;

            }else{

                this.insertNode(node.right, newNode);

            }

        }

    }

    //in-order traversal 중위순회 (왼쪽 - 루트 - 오른쪽)

    inOrderTraverse(callback){

        this.inOrderTraverseNode(this.root, callback);

    }

    

    inOrderTraverseNode(node, callback){

        if(node !== null){

            this.inOrderTraverseNode(node.left, callback);

            callback(node.key);

            this.inOrderTraverseNode(node.right, callback);

        }

    }

    //pre-order traversal 전위순회 (루트 - 왼쪽 - 오른쪽)

    preOrderTraverse(callback){

        this.preOrderTraverseNode(this.root,callback);

    }

    preOrderTraverseNode(node, callback){

        if(node !== null){

            callback(node.key);

            this.preOrderTraverseNode(node.left, callback);

            this.preOrderTraverseNode(node.right, callback);

        }

    }

    //post-order traversal 후위순회 (왼쪽-오른쪽-루트)

    postOrderTraverse(callback){

        this.postOrderTraverseNode(this.root, callback);

    }

    postOrderTraverseNode(node, callback){

        if(node !== null){

            this.postOrderTraverseNode(node.left, callback);

            this.postOrderTraverseNode(node.right, callback);

            callback(node.key);

        }

    }







}

let tree = new BinarySearchTree();

tree.insert(11); // 11은 루트노드가 된다.

tree.insert(7);

tree.insert(15);

tree.insert(5);

tree.insert(3);

tree.insert(9);

tree.insert(8);

tree.insert(10);

tree.insert(13);

tree.insert(12);

tree.insert(14);

tree.insert(20);

tree.insert(18);

tree.insert(25);

console.log(tree);

const printNode = (value) => {

    console.log(value);

}

console.log('------------중위순회------------');

tree.inOrderTraverse(printNode); // 중위순회(in-order traversal, 왼쪽-루트-오른쪽)

console.log('------------전위순회------------');

tree.preOrderTraverse(printNode); // 전위순회(pre-order traversal, 루트-왼쪽-오른쪽)

console.log('------------후위순회------------');

tree.postOrderTraverse(printNode); // 후위순회(post-order traversal, 왼쪽-오른쪽-루트)