질문

• Q1. 링크드 리스트가 뭔가요? (@김유철)
• Q2. 트리순회 (@김태환)

전위 순회 (Preorder Traversal)

• 전위 순회는 깊이 우선 순회 (DFT, Depth-First Traversal) 이라고도 합니다.

• 트리를 복사하거나, 전위 표기법을 구하는데 주로 사용됩니다.

• 트리를 복사할 때 전위 순회를 사용하는 이유는 트리를 생성할 때 자식 노드 보다 부모 노드가 먼저 생성되어야 하기 때문입니다.

• 전위 순회는 다음과 같은 방법으로 진행합니다.

  1. Root 노드를 방문한다.
  2. 왼쪽 서브 트리를 전위 순회한다.
  3. 오른쪽 서브 트리를 전위 순회한다.

• 위 트리의 전위 순회 결과는 다음과 같습니다.

• A → B → D → E → C → F → G

public void preorder(Node node) {
    if (node == null) {
        return;
    }

    log.info("data: {}", node.getData());
    preorder(node.getLeft());
    preorder(node.getRight());
}

중위순회 (Inorder Traversal)

• 중위 순회는 이진 탐색트리에서 오름차순 또는 내림차순으로 값을 가져올 때 사용됩니다.

• 중위 순회는 다음과 같은 방법으로 진행합니다.

  1. 왼쪽 서브 트리를 중위 순회한다.
  2. Root 노드를 방문한다.
  3. 오른쪽 서브 트리를 중위 순회한다.

• 위 트리의 중위 순회 결과는 다음과 같습니다.

• D → B → E → A → F → C → G

public void inorder(Node node) {
    if (node == null) {
        return;
    }

    inorder(node.getLeft());
    log.info("data: {}", node.getData());
    inorder(node.getRight());
}

후위 순회 (Postorder traversal)

• 후위 순회는 트리를 삭제하는데 주로 사용됩니다.

• 이유는 부모노드를 삭제하기 전에 자식 노드를 삭제하는 순으로 노드를 삭제해야 하기 때문입니다.

• 후위 순회는 다음과 같은 방법으로 진행합니다.

  1. 왼쪽 서브트리를 후위 순회한다.
  2. 오른쪽 서브트리를 후위 순회한다.
  3. Root 노드를 방문한다.

• 위 트리에 중위 순회 결과는 다음과 같습니다.

• D → E → B → F → G → C → A

public void postorder(Node node) {
    if (node == null) {
        return;
    }

    postorder(node.getLeft());
    postorder(node.getRight());
    log.info("data: {}", node.getData());
}

• Q3. 질문 (@발표자이름)