📌 트리(Tree)

이미지 출처 : https://python.plainenglish.io/data-structures-tree-29c825760095

- Node와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조

- 이진트리 : 노드의 최대 Branch가 2인 트리

- 이진탐색트리(Binary Search Tree, BST) : 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가진다.

 

- 전위 순회 : Root -> Left -> Right

- 중위 순회 : Left -> Root -> Right

- 후위 순회 : Left -> Right -> Root

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
 
    TreeNode(int x) {
        val = x;
    }
}
 
public class Tree {
    public void preOrder(TreeNode root) {
        // 기저조건
        if (root == null) {
            return;
        }
 
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
 
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
 
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
 
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
 
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
 
    public static void main(String[] args) {
 
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
 
        Tree tree = new Tree();
 
        System.out.println("Preorder traversal");
        tree.preOrder(root);
        System.out.println();
 
        System.out.println("Inorder traversal");
        tree.inOrder(root);
        System.out.println();
 
        System.out.println("Postorder traversal");
        tree.postOrder(root);
        System.out.println();
 
    }
}

 

🎯 과제

1) 트리의 부모 찾기
https://www.acmicpc.net/problem/11725

2) 트리 순회

https://www.acmicpc.net/problem/1991