[자료구조] 트리 순회 (Tree traversal)

트리 순회 (Tree traversal)

• 특정 목적을 위해 트리의 모든 노드를 방문하는 것을 트리 순회라고 한다.
• 트리 순회에는 전위 순회, 중위 순회, 후위 순회가 있다.

 

전위 순회

• root를 먼저 순회
• root(부모노드) -> 왼쪽 하위 트리 (왼쪽 자식 노드) -> 오른쪽 하위 트리 (오른쪽 자식 노드)

    public ArrayList<Integer> preorderTree(Node root, int depth, ArrayList<Integer> list) {    //전위 순회
      
      if (root != null) {
        list.add(root.getData()); // 부모 노드
        preorderTree(root.getLeft(), depth + 1, list); // 왼쪽 자식노드 
        preorderTree(root.getRight(), depth + 1, list); // 오른쪽 자식노드
      }
      
      return list;
    }

중위 순회

• 왼쪽 하위 트리를 모두 순회후 root를 순회 
• 왼쪽 하위 트리 (왼쪽 자식 노드) -> root(부모노드) -> 오른쪽 하위 트리 (오른쪽 자식 노드)

public ArrayList<Integer> inorderTree(Node root, int depth, ArrayList<Integer> list) {

  if (root != null) {
    inorderTree(root.getLeft(), depth + 1, list); // 왼쪽 자식 노드
    list.add(root.getData());  // root
    inorderTree(root.getRight(), depth + 1, list); // 오른쪽 자식 노드
  }
  
  return list;
}

후위 순회

• 하위 트리 모두 순회후 root 순회
• 왼쪽 하위 트리 (왼쪽 자식 노드) ->  오른쪽 하위 트리 (오른쪽 자식 노드) ->  root(부모노드) 

    public ArrayList<Integer> postorderTree(Node root, int depth, ArrayList<Integer> list) {   //후위 순회
 
      if (root != null) {
        postorderTree(root.getLeft(), depth + 1, list); // 왼쪽 자식 노드
        postorderTree(root.getRight(), depth + 1, list); // 오른쪽 자식 노드
        list.add(root.getData());
      }
      
      return list;
    }