자료구조 Tree traversal

트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회

트리 구조는 계층적 구조라는 특별한 특징을 가지기 때문에, 모든 노드를 순회하는 방법엔 크게 세 가지

전위 순회, 중위 순회, 후위 순회

트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽

 

 

전위 순회 (preorder traverse)

가장 먼저 방문하는 노드는 루트입니다. 루트에서 시작해 왼쪽의 노드들을 차례대로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색합니다. 즉 부모 노드가 제일 먼저 방문되는 순회 방식입니다. 전위 순회는 주로 트리를 복사할 때 사용

전위 순회

/* 최소한의 기능만 구현되어 있습니다.
   자식 노드가 없는 경우는 node == null이라고 가정합니다.
   이미 이진 트리는 구현되어 있다고 가정합니다. */

class Node {
    String data;
	Node left;
	Node right;

	public Node getLeft() {
      return left;
    }

    public String getData() {
      return data;
    }

    public Node getRight() {
      return right;
    }
}

public ArrayList<String> preOrder(Node node, ArrayList<String> list) {
    if (node != null) {
      list.add(node.getData());
      list = preOrder(node.getLeft(), list);
      list = preOrder(node.getRight(), list);
    }
    return list;
}

탐색 종료 시 list의 값 -> ["A", "B", "D", "H", "I", "E", "J", "K", "C", "F", "L", "M", "G", "N", "O"]

 

 

중위 순회 (inorder traverse)

중위 순회는 루트를 가운데에 두고 순회.

제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색.

부모 노드가 서브 트리의 방문 중간에 방문되는 순회 방식.

중위 순회는 이진 탐색 트리의 오름차순으로 값을 가져올 때 사용.

 

중위 순회

/* 최소한의 기능만 구현되어 있습니다.
   자식 노드가 없는 경우는 node == null이라고 가정합니다.
   이미 이진 트리는 구현되어 있다고 가정합니다. */

class Node {
  String data;
	Node left;
	Node right;

	public Node getLeft() {
      return left;
    }

    public String getData() {
      return data;
    }

    public Node getRight() {
      return right;
    }
}

public ArrayList<String> inOrder(Node node, ArrayList<String> list) {
    if (node != null) {
      list = inOrder(node.getLeft(), list);
      list.add(node.getData());
      list = inOrder(node.getRight(), list);
    }
    return list;
}

탐색 종료 시 list의 값 -> ["H", "D", "I", "B", "E", "J", "K", "A", "L", "F", "M", "C", "N", "G", "O"]

 

 

후위 순회 (postorder traverse)

후위 순회는 루트를 가장 마지막에 순회.

제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문.

트리를 삭제할 때 사용. 자식 노드가 먼저 삭제되어야 상위 노드를 삭제할 수 있기 때문.

후위 순회

/* 최소한의 기능만 구현되어 있습니다.
   자식 노드가 없는 경우는 node == null이라고 가정합니다.
   이미 이진 트리는 구현되어 있다고 가정합니다. */

class Node {
  String data;
	Node left;
	Node right;

	public Node getLeft() {
      return left;
    }

    public String getData() {
      return data;
    }

    public Node getRight() {
      return right;
    }
}

public ArrayList<String> postOrder(Node node, ArrayList<String> list) {
    if (node != null) {
      list = postOrder(node.getLeft(), list);
      list = postOrder(node.getRight(), list);
      list.add(node.getData());
    }
    return list;
}

탐색 종료 시 list의 값 -> ["H", "I", "D", "J", "K", "E", "B", "L", "M", "F", "N", "O", "G", "C", "A"]

 

 

 

 

출처 : 코드스테이츠