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

참고문헌.

https://geniee.tistory.com/20
https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html
https://taesung1993.tistory.com/18?category=868017
https://taesung1993.tistory.com/21?category=868017