Tree 알고리즘

트리(Tree) 개념 정리

1. 트리(Tree)란?

• 부모/자식 관계를 가지는 계층적 구조이다.
• 노드는 하나 이상의 자식(Child)을 가질 수 있다.
• 트리에서 자식이 없는 노드를 리프(Leaf) 노드라고 한다.

---

2. 이진 트리(Binary Tree)

• 각 노드는 최대 2개의 자식 노드를 가질 수 있는 트리이다.

이진 탐색 트리(Binary Search Tree, BST)

• 왼쪽 서브트리의 모든 노드는 부모보다 작은 값을 가진다.
• 오른쪽 서브트리의 모든 노드는 부모보다 큰 값을 가진다.

완전 이진 트리(Complete Binary Tree)

• 모든 노드가 왼쪽부터 차례로 채워져 있는 트리이다.
• 마지막 레벨의 노드들은 가능한 왼쪽부터 채워져 있어야 한다.

포화 이진 트리(Full Binary Tree)

• 모든 노드가 자식 노드를 0개 또는 2개 갖는 트리이다.

---

3. 이진 트리 순회(Binary Tree Traversal)

중위 순회(Inorder Traversal) - Left, Root, Right

1. 루트 노드에서 시작한다.
2. 왼쪽 서브트리로 이동한다.
3. 왼쪽 서브트리의 가장 끝 노드까지 도달하면 해당 노드를 출력한다.
4. 부모 노드를 출력한다.
5. 오른쪽 서브트리를 출력한다.

예시 트리

      (1)  
   (2)   (3)
 (4) (5)

순회 결과: 4 -> 2 -> 5 -> 1 -> 3

---

전위 순회(Preorder Traversal) - Root, Left, Right

1. 루트 노드를 출력한다.
2. 왼쪽 서브트리로 이동하며 노드를 출력한다.
3. 왼쪽 서브트리의 리프 노드까지 도달하면 오른쪽 서브트리로 이동하여 출력한다.

예시 트리

      (1)  
   (2)   (3)
 (4) (5)

순회 결과: 1 -> 2 -> 4 -> 5 -> 3

---

후위 순회(Postorder Traversal) - Left, Right, Root

1. 왼쪽 서브트리의 리프 노드까지 이동하여 출력한다.
2. 오른쪽 서브트리로 이동하여 리프 노드를 출력한다.
3. 부모 노드를 출력한다.

예시 트리

      (1)  
   (2)   (3)
 (4) (5)

순회 결과: 4 -> 5 -> 2 -> 3 -> 1

class Node {  
  
    int data;  
    Node left;  
    Node right;  
}  
  
class Tree {  
  
    public Node root;  
  
    Tree() {  
        root = new Node();  
    }  
  
    public void setRoot(Node node) {  
        this.root = node;  
    }  
  
    public Node getRoot() {  
        return this.root;  
    }  
  
    public Node makeNode(Node left, int data, Node right) {  
        Node node = new Node();  
        node.left = left;  
        node.data = data;  
        node.right = right;  
        return node;  
    }  
  
    public void inorder(Node node) {  
        if (node == null) {  
            return;  
        }  
  
        inorder(node.left);  
        System.out.println(node.data);  
        inorder(node.right);  
    }  
  
    public void preorder(Node node) {  
        if (node == null) {  
            return;  
        }  
  
        System.out.println(node.data);  
        preorder(node.left);  
        preorder(node.right);  
    }  
  
    public void postorder(Node node) {  
        if (node == null) {  
            return;  
        }  
        postorder(node.left);  
        postorder(node.right);  
        System.out.println(node.data);  
    }  
}  
  
/*  
  
        (1)    (2)     (3)  (4) (5)  
* */  
  
public class test2 {  
    public static void main(String[] args) {  
  
        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.inorder(n1);  
        System.out.println("------");  
        t.preorder(n1);  
        System.out.println("------");  
        t.postorder(n1);  
    }  
}