[2023-09-26] TIL - 자료구조 & 알고리즘 - 트리

비선형 자료구조인 트리에 대해서 알아보자

 

트리

- 방향 그래프의 일종으로 정점을 가리키는 간선이 하나밖에 없는 구조를 가지고 있다.

 

트리의 특징

- 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다.

- 정점이 N개인 트리는 반드시 N-1개의 간선을 가진다.

- 루트에서 특정 정점으로 가는 경로는 유일하다. -> 하나의 부모 정점을 가지기 때문에 생긴 특징

 

이진 트리

- 이진트리는 각 정점이 최대 2개의 자식을 가지는 트리를 의미한다.

 

• 이진트리
• 완전 이진트리 : 마지막 레벨을 제외하고 모두 채워져 있는 이진 트리
• 포화 이진 트리 : 완전히 채워져 있는 이진 트리
• 편향 트리 : 한 방향으로만 정점이 이어진 이진 트리

 

이진트리의 특징

- 정점이 N개인  이진트리는 최악의 경우 높이가 N이 될 수 있다.

- 정점이 N개인 포화 또는 완전 이진트리의 높이는 Log N 이다.

- 높이가 h인 포화 이진트리는 2^h - 1개의 정점을 가진다.

- 일반적인 이진트리를 사용하는 경우는 많지 않다. 다음 자료구조에 응용된다.

 - 이진 탐색트리

 - 힙

 - AVL 트리

 - 레드 블랙 트리

 

트리의 구현방법

- 그래프와 마찬가지로 인접 행렬, 인접 리스트 두 가지 방식으로 트리를 표현할 수 있다.

 

이진 트리의 구현방법

- 배열 혹은 요소에 링크가 2개 존재하는 연결리스트로 구현할 수 있다.

 

 

자바스크립트에서 사용법

이진트리 - 배열

// 0번 인덱스는 편의를 위해 비워둔다.
// Left = Index * 2;
// Right = Index * 2 + 1
// Parent = floor(Index / 2)
const tree = [
	undefined,
    //1
    8,
    // 1*2, 1*2+1
    4, 6
    // 2*2, 2*2+1, 3*2, 3*2+1
    3, undefined, 2, 5
    // 4*2. 4*2+1, 5*2, 5*2+1
    undefined, undefined, 1
];

이진트리 - 연결리스트

class Queue {
	constructor() {
    	this.queue =[];
        this.front = 0;
        this.rear = 0;
    }
    
    enqueue(value){
    	this.queue[this.rear++] = value;
    }
    
    dequeue() {
    	const value = this.queue[this.front];
        delete this.queue[this.front];
        this.front +=1;
        return value;
    }
    
    peek() {
    	return this.queue[this.front];
    }
    
    size() {
    	return this.rear - this.front;
    }
}

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

class Tree{
	constructor(node){
    	this.root = node;
    }
    
    display() {
    	const queue = new Queue();
        queue.enqueue(this.root);
        while(queue.size) {
        	const currentNode = queue.dequeue();
            console.log(currentNode.value);
            if(currentNode.left) queue.enqueue(currentNode.left);
            if(currentNode.left) queue.enqueue(currentNode.right);
        }
	}
}

const tree = new Tree(new Node(8));
tree.root.left = new Node(4);
tree.root.right= new Node(6);
tree.root.left.left = new Node(3);
tree.root.right.left = new Node(2);
tree.root.right.right = new Node(5);
tree.root.right.left.left = new Node(1);

 

 

 

전위순회 (재귀+스택)

// 재귀,스택 전위순회
function PreOrder() {
  let answer = [];
  let string = [undefined, "-", "+", "*", 2, 5, 3, 9];
  function DFS(L) {
    if (L > 7) return;
    else {
      answer.push(string[L]);
      DFS(L * 2);
      DFS(L * 2 + 1);
    }
  }
  DFS(1);
  return answer.join(" ");
}

console.log(PreOrder());

중위 순회 (재귀 + 스택)

// 재귀,스택 중위순회
function InOrder() {
  let answer = [];
  let string = [undefined, "-", "+", "*", 2, 5, 3, 9];
  function DFS(L) {
    if (L > 7) return;
    else {
      DFS(L * 2);
      answer.push(string[L]);

      DFS(L * 2 + 1);
    }
  }
  DFS(1);
  return answer.join(" ");
}

console.log(InOrder());

후위 순회 (재귀 + 스택)

// 재귀,스택 후위순회
function PostOrder() {
  let answer = [];
  let string = [undefined, "-", "+", "*", 2, 5, 3, 9];
  function DFS(L) {
    if (L > 7) return;
    else {
      DFS(L * 2);
      DFS(L * 2 + 1);
      answer.push(string[L]);
    }
  }
  DFS(1);
  return answer.join(" ");
}

console.log(PostOrder());