JS로 공부하는 Binary Tree

gem·2021년 10월 22일

자료구조

JS로 공부하는 자료구조

목록 보기

2/8

Tree

트리는 비선형자료구조 중에서 노드 간에 계층적인 구조를 이루고 있다.

특징

트리는 하나의 루트 노드를 갖는다.
모든 노드는 0개이상의 자식노드를 갖고 있다.
노드와 노드를 연결하는 간선으로 구성되어 있다.
트리는 사이클이 없는 방향 그래프(DAG)이다.
트리에는 사이클이 존재할 수 없다.
이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 있다.

Binary Tree

모든 노드가 최대 2개의 자식노드를 갖고 있는 트리.

구현방법

배열

/*       5
 *     /   \
 *    3      8
 *   / \   /  \
 *  1   4  7   9
 */
 
const tree = [null, 5, 3, 8, 1, 4, 7, 9];

index0은 null로 비우고 index1부터 root를 시작한다.
왼쪽 자식노드는 index*2
오른쪽 자식노드는 index*2+1

연결리스트

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

// 트리 객체
const bTree = function(){
	this.root = null;
}
// 트리 프로토타입 1. 노드 만들기
bTree.prototype.makeTree = function(left,data,right){
	const newNode = new Node(data);
    newNode.left = left;
    newNode.right = right;
    return newNode;
}

const tree = new bTree();
const n1 = tree.makeTree("b","a","c");
console.log(n1); // {data:'a',left:'b',right:'c'}

left, right를 이용해 자식노드를 참조한다.

순회

순회는 Pre-order/ In-order/ Post-order
DFS/BFS에서도 위 3가지 순회가 적용된다.

/*       a
 *     /   \
 *    b     c
 *   / \   /  \
 *  d   e f   g
 */

전위 순회 (pre-order)

root > left > right 순으로 순회

// a b d e c f g

function preOrder(root)
	if(root != null){
    	console.log(root.data);
        preOrder(root.left);
        preOrder(root.right);
   }
}

중위 순회 (in-order)

left > root > right 순으로 순회

// d b e a f c g

function inOrder(root)
	if(root != null){
        inOrder(root.left);
        console.log(root.data);
        inOrder(root.right);
   }
}

후위 순회 (post-order)

left > right > root 순으로 순회

// d e b f g c a

function postOrder(root)
	if(root != null){
        postOrder(root.left);
        console.log(root.data);
        postOrder(root.right);
   }
}

전체코드

// 순회결과를 담을 배열
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;
}

// 트리 프로토타입 1. 노드 만들기
bTree.prototype.makeTree = function(left,data,right){
	const newNode = new Node(data);
    newNode.left = left;
    newNode.right = right;
    return newNode;
}

// 트리 프로토타입 2. 전위순회
bTree.prototype.preOrder = function(root){
	if(root != null){
    	preOrderResult.push(root.data);
        this.preOrder(root.left);
        this.preOrder(root.right);
    }
}

// 트리 프로토타입 3. 중위순회
bTree.prototype.inOrder = function(root){
	if(root != null){
        this.inOrder(root.left);
		inOrderResult.push(root.data);
        this.inOrder(root.right);
    }
}

// 트리 프로토타입 4. 후위순회
bTree.prototype.postOrder = function(root){
	if(root != null){
        this.postOrder(root.left);
        this.postOrder(root.right);
        postOrderResult.push(root.data);
    }
}

const tree = new bTree();
const n3 = tree.makeTree(null,"c",null);
const n2 = tree.makeTree(null,"b",null);
const n1 = tree.makeTree(n2,"a",n3);


/*       a
 *     /   \
 *    b    c
 */

tree.preOrder(n1);
console.log(preOrderResult.join(" ")); // a b c

tree.inOrder(n1);
console.log(inOrderResult.join(" ")); // b a c

tree.postOrder(n1);
console.log(postOrderResult.join(" ")); // b c a