트리 Tree

• 부모 자식이 있는 구조
• 계층이 있고, 그룹이 있다.
• 더이상 자식이 없는 마지막 노드를 leaf라고 부른다.

🌳 트리의 종류

⭐️ 이진트리 Binary Tree

• 자식 노드가 최대 2개까지만 붙는 트리
• 3개씩 붙는 트리 (Ternary tree), 4개씩 붙는 트리도 있다.
• 다른 노드 조건없음.

이진 탐색 트리 Binary Search Tree

• 왼쪽 노드와 그 이하 자식 노드들은 오른쪽 노드보다 더 작아야 한다.
  

Balaced / Unbalanced

• 왼쪽 오른쪽 노드의 분포가 너무 한쪽으로 쏠리지 않았다면, Balaced
• red-black tree
• AVL tree

완전 이진 트리 Complete Binary Tree

• 모든 노드들이 레벨별로 왼쪽부터 채워져 있으면 완전 이진 트리
• 마지막 레벨을 제외한 모든 레벨이 다 채워져있고, 마지막 레벨은 왼쪽부터 채우기

Full Binary Tree

• 노드의 자식이 있다면 하나의 자식만 있으면 안된다. 자식이 둘 이거나 0이거나.

Perfect Binary Tree

• 완벽한 피라비드 형태의 이진 트리
• 레벨이 n일 때, 노드가 2^n-1개 있다.

🎄 트리 만들기

노드 Node

• 2진 트리 노드

class Node {
	int data;
    Node left; // 자식노드 왼쪽
    Node right; // 자식노드 오른쪽
}

트리 Tree

class Tree {
	public Node root; // 시작점
    public Node makeNode(Node left, int data, Node right) {
    	Node node = new Node();
        node.data = data;
        node.left = left;
        node.right = right;
        return node;
    }
}

그래프 그리기

• 밑에서부터 그리자

Tree t = new Tree();
Node n4 = t.makeNode(null, 4, null);
Node n5 = t.makeNode(null, 5, null);
Node n2 = t.makeNode(n4, 2, n5);
Node n3 = t.makeNode(null, 3, null);
Node n1 = t.makeNode(n2, 1, n3);
t.setRoot(n1);

---

👿 관련 문제

---

🖇️ 참고

• [자료구조 알고리즘] Tree의 종류