[JS] 이진트리와 순회

1. 트리

 연결리스트, 스택, 큐는 자료들이 선의 형태로 쭉 나열되어 있는 구조를 가지고 있다. 이를 선형 자료구조라고 한다. 반대로 자료구조가 선의 형태로 나열되지 않는 구조를 비선형 자료구조라고 한다. 여기서 트리는 비선형 자료구조 중에서 자료들 간에 계층적인 구조를 이루고 있다. 가계도를 떠올리면 쉽다.

 

[그림 1] 가계도

 

 [그림 1] 가계도를 보면 준식는 태성, 형준이라는 두 명의 자식이 있고 태성 또한, 민경, 지영이라는 두 명의 자식이 있다. 이렇듯 가계도에서 가족 구성원을 연결하는 선은 부모-자식 관계를 나타낸다는 것을 알 수 있다. 그리고 쭉 올라가면 준식이라는 조상을 만날 수 있다. 이제 가계도를 트리 구조로 바꾸면 다음과 같다.

 

[그림 2] 트리 구조

 

구조적으로 딱히 가계도와 다르지 않다. 간단하게 용어설명을 하겠다. A, B, C, D, E와 같이 각각의 원소들을 트리구조에서는 노드라고 부른다. 노드는 부모-자식관계가 성립된다. 또한 최종 부모노드, 즉 A라는 조상노드를 우리는 루트노드라고 부른다. C와 같이 자식이 없는 노드를 단말노드라고 하며, 자식의 수를 차수라고 한다. 따라서 B의 차수는 2이다.

 

2. 이진 트리

 [그림 1], [그림 2]처럼 트리의 자식은 꼭 두 개만 있는 것이 아니다. 세 개도 될 수 있고, 네 개도 될 수 있다. 그런데 자식이 엄청나게 많으면 연산이 복잡할 것이다. 따라서 연산을 단순화하려면 자식의 수를 줄일 필요가 있다. 그래서 모든 노드의 차수를 2 이하로 정하여 전체 트리의 차수가 2 이하가 되도록 만든 것이 이진트리다. 

 

 

 이진트리를 구현하는 방법에는 두 가지가 있다. 첫째는 배열을 이용한 방식이고, 둘째는 연결리스트를 이용한 방식이다. 여기서 나는 연결리스트를 이용하여 구현해보려고 한다. 이진트리를 연결리스트를 이용해서 구현하기 위해서는 데이터를 저장하는 필드, 왼쪽 자식노드를 연결하는 링크필드, 오른쪽 자식노드를 연결하는 링크필드를 구성해야한다. 코드를 입력하면 다음과 같다.

 

[그림 3] 이진트리 노드의 구성

/* 노드 초기화 */
const Node = function(data){
  this.data = data;
  this.left = null;
  this.right = null;
}

/* 루트 노드 초기화 */
const bTree = function(data){
  this.root = null;
}

/* 이진트리의 노드 생성 */
bTree.prototype.makebTreeNode = function(left, data, right){
  const newNode = new Node(data); //노드 생성
  newNode.left = left;
  newNode.right = right;
  this.root = newNode;
}

 

 

 [그림 4]와 같은 구성을 만드려면 다음과 같이 코드를 짜주면 된다.

 

[그림 4] 예시 구성도

  const tree = new bTree();
  const n7 = tree.makeTree(null, 'D', null);
  const n6 = tree.makeTree(null, 'C', null);
  const n5 = tree.makeTree(null, 'B', null);
  const n4 = tree.makeTree(null, 'A', null);
  const n3 = tree.makeTree(n6, '/', n7);
  const n2 = tree.makeTree(n4, '*', n5);
  const n1 = tree.makeTree(n2, '-', n3);

 

3. 이진트리의 순회

 트리를 사용하여 자료를 계층적 구조로 저장하고, 이를 사용하기 위해서는 노드를 방문하는 방법이 필요하다. 모든 노드를 한 번씩 모두 방문하여 노드가 가지고 있는 데이터를 처리하는 것을 순회라고 한다. 순회는 세 작업으로 나뉘어진다.

1. 현재 노드를 방문하여 데이터를 읽는 작업 D

2. 현재 노드의 왼쪽 서브 트리로 이동하는 작업 L

3. 현재 노드의 오른쪽 서브트리로 이동하는 작업 R

 (1) 전위 순회

 

  전위 순회는 현재 노드를 방문하는 D 작업을 가장 먼저 수행하여 DLR의 순서로 순회하는 방법이다. L과 R은 재귀함수를 이용한다.

 

 

bTree.prototype.preOrder = function(treeRoot){
  //트리의 전위순회 구현
  if(treeRoot != null){
    preOrderResult.push(treeRoot.data);
    this.preOrder(treeRoot.left);
    this.preOrder(treeRoot.right);
  }
}

 

 (2) 중위순회

 

  중위순회는 현재노드를 방문하는 D 작업을 L 작업과 R 작업 중간에 수행하여 LDR 순서로 순회하는 방법이다. 

 

 

bTree.prototype.inOrder = function(treeRoot){
  //트리의 중위순회 구현
  if(treeRoot != null){
    this.inOrder(treeRoot.left);
    inOrderResult.push(treeRoot.data);
    this.inOrder(treeRoot.right);
  }
}

 

 (3) 후위 순회

후위 순회는 현재 노드를 방문하는 D 작업을 가장 나중에 수행하여 LRD로 순회하는 방법이다.

 

 

bTree.prototype.postOrder = function(treeRoot){
  //트리의 후위순회 구현
  if(treeRoot != null){
    this.postOrder(treeRoot.left);
    this.postOrder(treeRoot.right);
    postOrderResult.push(treeRoot.data);
  }
}

 

4. 프로그램 코드

 프로그램 코드는 다음과 같다.

const preOrderResult = [];
const inOrderResult = [];
const postOrderResult = [];

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

const bTree = function(){
  this.root = null;
}

bTree.prototype.makeTree = function(left, data, right){
  const newNode = new Node(data);
  newNode.left = left;
  newNode.right = right;
  return newNode;
}

bTree.prototype.preOrder = function(treeRoot){
  //트리의 전위순회 구현
  if(treeRoot != null){
    preOrderResult.push(treeRoot.data);
    this.preOrder(treeRoot.left);
    this.preOrder(treeRoot.right);
  }
}

bTree.prototype.inOrder = function(treeRoot){
  //트리의 중위순회 구현
  if(treeRoot != null){
    this.inOrder(treeRoot.left);
    inOrderResult.push(treeRoot.data);
    this.inOrder(treeRoot.right);
  }
}

bTree.prototype.postOrder = function(treeRoot){
  //트리의 후위순회 구현
  if(treeRoot != null){
    this.postOrder(treeRoot.left);
    this.postOrder(treeRoot.right);
    postOrderResult.push(treeRoot.data);
  }
}

const main = function(){
  const tree = new bTree();
  const n7 = tree.makeTree(null, 'D', null);
  const n6 = tree.makeTree(null, 'C', null);
  const n5 = tree.makeTree(null, 'B', null);
  const n4 = tree.makeTree(null, 'A', null);
  const n3 = tree.makeTree(n6, '/', n7);
  const n2 = tree.makeTree(n4, '*', n5);
  const n1 = tree.makeTree(n2, '-', n3);

  console.log("전위 순회");
  tree.preOrder(n1);
  console.log(preOrderResult.join(" "));

  console.log("\n중위 순회");
  tree.inOrder(n1);
  console.log(inOrderResult.join(" "));

  console.log("\n후위 순회");
  tree.postOrder(n1);
  console.log(postOrderResult.join(" "));
}

main();

 

5. 참고자료

1. 자바로 배우는 쉬운 자료구조, 한빛아카데미