Javascript 비선형 자료 구조 - 이진 트리 ( Binary Tree )

트리 : 두 노드 사이에 하나의 간선만 연결되어 있는, 최소 연결과 계층 형태의 비선형 자료구조

노드 ( node ) : 하나 이상의 값을 갖는 객체 단위

간선 ( edge ) : 두 노드를 연결하는 선

루트 노드 ( Root node ) : 부모가 없는 최상위 노드 ▶ A

단말 노드 ( Leaf node ) : 자식이 없는 최하위 노드 ▶ C, D, E

부모 노드 ( Parent node ) : 특정 Sub-Tree 내에서의 상위 노드 ▶ A ( B, C의 부모노드 ), B ( D, E의 부모 노드 )

자식 노드 ( Child node ) : 특정 Sub-Tree 내에서의 하위 노드 ▶ B와 C ( A의 자식 노드 ), D와 E (  B의 자식 노드 )

형제 ( Sibling ) : 같은 부모를 가지는 자식 노드들 간의 관계 ( 같은 계층에 있음 )

---

노드 크기(size) : 자신을 포함한 모든 자손 노드의 개수

노드 깊이(depth) : 루트에서 특정 노드에 도달하기 위한 간선의 개수

노드 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합

노드 차수(degree) : 노드가 지닌 가지의 수

트리 차수(tree degree) : 트리의 최대 차수

트리 높이(height) : 루트 노드에서 가장 깊숙이 있는 노드의 깊이

---

트리 순회 : 트리 구조에서 각각의 노드를 한 번씩 방문하는 과정

 

N : 해당 노드를 방문 ( Node )

L : 왼쪽 서브트리로 이동 ( Left )

R : 오른쪽 서브트리로 이동 ( Right )

 

순회방식

전위 순회 ( Pre-order ) : N - L - R ( A → B → D → E → C )

중위 순회 ( In-order ) : L - N - R ( D → B → C → A → C )

후위 순회 ( Post-order ) : L - R - N ( D → E → B → C → A )

층별 순회 ( Level-order ) : 낮은 Level부터 순차적으로 순회 ( A → B → C → D → E )

 

이진 트리 : 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조

 

---

 

이진 트리 순회 구현

 

🔴 노드 & 이진 트리

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

function BinaryTree(){
    this.root = null;
}

 

 

🟠 노드 삽입 함수 ( 부모 노드보다 작은 값은 왼쪽 서브트리에, 큰 값은 오른쪽 서브트리에 삽입 ▶ '이진 탐색 트리' )

비교대상이 되는 부모 노드(node)와 새롭게 삽입 될 값(value)를 매개변수로 받는다.

만약 부모 노드가 null이 아니면, value가 node의 value보다 작으면 node의 left를 부모 노드로 하여 함수를 실행시킨다. 

반대로 value가 node의 value보다 크거나 같으면 node의 right를 부모 노드로 하여 함수를 실행시킨다. 

위의 과정을 반복하여 최하위 레벨로 이동하면 ( = node가 null이면 ) 그 자리에 새로운 노드를 삽입하고 반환한다.

//_insertNode함수는 내부함수로서, insert함수의 내부에서만 사용된다.
BinaryTree.prototype._insertNode = function(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);
    }
    return node;
}

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

let tree = new BinaryTree();

tree.insert("C");
tree.insert("B");
tree.insert("A");
tree.insert("F");
tree.insert("G");
tree.insert("E");

console.log(tree);

이진 트리에 알파벳을 추가하여 아래와 같은 구조의 이진트리를 구현하였다. 

 

 

🟡 전위 순회

부모 노드 출력한 후 왼쪽 서브트리, 오른쪽 서브트리 순으로 순회하면서 callback함수를 실행한다.

BinaryTree.prototype._preOrdereTraverseNode = function(node, callback){
    if(node === null) return;
    callback(node);
    this._preOrdereTraverseNode(node.left, callback);
    this._preOrdereTraverseNode(node.right, callback);
}
BinaryTree.prototype.preOrderTraverse = function(callback){
    this._preOrdereTraverseNode(this.root, callback);
}

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

tree.preOrderTraverse(printNode);
console.log("end");
//output: C -> B -> A -> F -> E -> G -> end

노드를 출력하는 printNode함수를 콜백함수로 실행시킨 결과 올바르게 출력된 것을 확인할 수 있다. 

 

🟢 중위 순회

왼쪽 서브트리를 출력한 후 부모 노드, 오른쪽 서브트리 순으로 순회하면서 callback함수를 실행한다.

BinaryTree.prototype._inOrdereTraverseNode = function(node, callback){
    if(node === null) return;
    this._inOrdereTraverseNode(node.left, callback);
    callback(node);
    this._inOrdereTraverseNode(node.right, callback);
}
BinaryTree.prototype.inOrderTraverse = function(callback){
    this._inOrdereTraverseNode(this.root, callback);
}

tree.inOrderTraverse(printNode);
console.log("end");
//output: A -> B -> C -> E -> F -> G -> end

 

🔵 후위 순회

왼쪽 서브트리를 출력한 후 오른쪽 서브트리, 부모 노드 순으로 순회하면서 callback함수를 실행한다.

BinaryTree.prototype._postOrdereTraverseNode = function(node, callback){
    if(node === null) return;
    this._postOrdereTraverseNode(node.left, callback);
    this._postOrdereTraverseNode(node.right, callback);
    callback(node);
}
BinaryTree.prototype.postOrderTraverse = function(callback){
    this._postOrdereTraverseNode(this.root, callback);
}

tree.postOrderTraverse(printNode);
console.log("end");
//output: A -> B -> E -> G -> F -> C -> end

 

🟣 층별 순회

낮은 레벨의 노드부터 순차적으로 순회하면서 callback 함수를 실행하며, 큐를 활용하여 구현할 수 있다.

function Queue(array){
    this.array = array ? array : [];
    this.tail = array ? array.length : 0;
    this.head = 0;
}

Queue.prototype.enqueue = function(data){
    return (this.array[this.tail++] = data);
}

Queue.prototype.dequeue = function(){
    if(this.tail == this.head) return undefined;
    let element = this.array[this.head];
    delete this.array[this.head++];
    return element;
}

BinaryTree.prototype.levelOrderTraverse = function(callback){
    let q = new Queue();
    let node;
    q.enqueue(this.root);
    while(q.tail !== q.head){
        node = q.dequeue();
        callback(node);
        if(node.left !== null) q.enqueue(node.left);
        if(node.right !== null) q.enqueue(node.right);
    }
};

예를 들어보자. 위의 예시와 같은 이진 트리라면 가장 먼저 C가 큐에 삽입되었을 것이고 while문이 실행될 것이다. while문을 통해 큐에서 C가 출력될 것이고, 왼쪽 노드인 B와 오른쪽 노드인 F가 큐에 삽입된다. 그 후 B가 출력되면서 B의 왼쪽 노드인 A가 큐에 삽입되고, F가 출력되면서 F의 자식 노드인 E와 G가 큐에 삽입된다. 이렇게 큐에 쌓인 노드들이 순차적으로 출력되는 것을 확인할 수 있다. ( 층별 순회 ) 

tree.levelOrderTraverse(printNode);
console.log("end");
//output: C -> B -> F -> A -> E -> G -> end