TIL

• 자료구조(트리, 우선순위 큐, 힙, 트라이)

과제가 있었던 트리를 알아보겠습니다.

트리

• 방향 그래프의 일종으로 정점을 가르키는 간선이 하나 밖에 없는 구조를 가지고 있다
• 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다
• 정점이 n개인 트리는 반드시 n-1개의 간선을 가진다
• 루트에서 특정 정점으로 가는 경로는 유일하다

이진트리

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

완전이진트리

마지막 레벨을 제외하고 모든 트리가 채워져있다.

포화 이진트리

이진 트리의 구현방법
배열 혹은 요소에 링크가 2개 존재하는 연결 리스트로 구현할 수 있다.
js 코드

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.right) queue.enqueue(currentNode.right);
            
        }
    }

}

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

결과 시각화: