트리는 그래프의 일종으로 노드들이 계층 구조를 갖는 자료 구조입니다.
노드는 최대 1개의 부모 노드와 여러개의 자식 노드를 가질 수 있습니다.

• A는 트리의 최상층에 있는 노드로 루트 노드라고 합니다.
• D와 H처럼 자식 노드가 없는 노드들을 리프 노드라고 합니다.
• 하나의 노드에서 자식 노드로 내려갈수록 트리 깊이는 점점 깊어집니다.

트리의 구현

임의의 노드를 선택했을 때 해당 노드를 루트 노드로 시작하는 서브 트리를 갖습니다. 이 서브 트리 또한 트리 성질을 모두 지니므로 트리는 재귀적 특성을 갖는다고 봅니다.

따라서 다음 클래스로 표현할 수 있습니다.

class Node {
	int data;
    Node parent;
    List<Node> children;
}

이진 트리

위의 그림처럼 모든 노드가 최대 2개의 자식 노드만을 가질때 이 트리를 이진 트리(binary tree)라고 합니다.

각 자식을 왼쪽 자식과 오른쪽 자식이라고 합니다. 이진 트리를 클래스로 표현하면 다음과 같습니다.

class Node {
	int data;
    Node parent;
    Node left;
    Node right;
}

이진 트리의 순회

노드를 방문하는 순서에 따라 순회 방식을 세가지로 구분할 수 있습니다.
다음 그림을 예시로 살펴보겠습니다.

1. 전위 순회

• 루트 노드에서 시작합니다.
• 노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 순으로 순회를 진행합니다.
• A -> B -> D -> C -> E -> H -> F
• 재귀 메서드로 구현할 수 있습니다.

void preorder(Node node){
	if(node == null) return;
    
    //노드 방문
    System.out.println(node.data);
    
    preorder(node.left);
    preorder(node.right);
    
}

2. 중위 순회

• 왼쪽 서브 트리 -> 노드 -> 오른쪽 서브 트리 순으로 순회를 진행합니다.
• D -> B -> A -> E -> H -> C -> F
• 재귀 메서드로 구현할 수 있습니다.

void inorder(Node node){
	if(node == null) return;
    
    inorder(node.left);
    
     //노드 방문
    System.out.println(node.data);
    
    inorder(node.right);
    
}

3. 후위 순회

• 양쪽 서브 트리 -> 노드 순으로 순회를 진행합니다.
• D -> B -> H -> E -> F -> C -> A
• 재귀 메서드로 구현할 수 있습니다.

void postorder(Node node){
	if(node == null) return;
    
    postorder(node.left);
    postorder(node.right);
    
      //노드 방문
    System.out.println(node.data);
}