[트리] 전위(Preorder), 중위(Inorder), 후위(Postorder)

전위, 중위, 후위는 tree traversal의 방식이다.

 

Preoder는 root -> left -> right의 순서를 가진다.

F -> B -> A -> D -> C -> E -> G -> I -> H

 

Inorder는 left -> root -> right의 순서를 가진다.

A -> B -> C -> D -> E -> F -> G -> H -> I

 

Postorder는 left -> right -> root의 순서를 가진다.

A -> C -> E -> D -> B -> H -> I -> G -> F

 

트리 순회 (preorder, inorder, postorder) JAVA 코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

// root -> left -> right
public void preorder(TreeNode root){
    if (root == null) return;
    System.out.println(root.value);
    preorder(root.left);
    preorder(root.right);
}

// left -> root -> right
public void inorder(TreeNode root){
    if (root == null) return;
    inorder(root.left);
    System.out.println(root.value);
    inorder(root.right);
}

// left -> right -> root
public void postorder(TreeNode root){
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.println(root.value);
}