[알고리즘 1068] 트리

들어가기전

• 트리구조는 실제로 트리모양으로 구현되진 않는다
• 물론 Node[] 를 여러개 가지고 Node 안에 left right 등의 주소를 가진 구조로 코드를 짤순있지만, 조금 복잡해지는 경향이 있다
• 물론 라이브러리의 경우에는 이런식으로 짜야 유지보수하기 편하긴 할 것 같다
• 나는 일단 배열 구조로 트리를 완성했다

요구사항

• 트리의 특정 노드를 지우면 하위 노드까지 삭제되었다고 전파되어야 한다
• 리프노드의 개수를 셀 수 있어야 한다.

특징

• 리프노드는 각각의 배열 원소에서 부모를 가리키는 형태로 개발이 된다.
• 트리에서 어떤 인덱스를 트리에서 부모로 가지지 않는 경우
  • 이는 리프 노드이다.

개략적 흐름도

• gpt 의 힘을 빌려 흐름도 작성 (벨로그에서는 머메이드 지원이 안되는거 같다..)

로직

int deletedNodeNumber = Integer.parseInt(br.readLine());

dfs(deletedNodeNumber);

---

private static void dfs(int deletedNodeNumber) {
    tree.set(deletedNodeNumber, DELETED_NODE);
    
    for (int i = 0; i < N; i++) {
        if (tree.get(i) == deletedNodeNumber) {
            dfs(i);
        }
    }
}

• dfs 에서 deletedNodeNumber 같은 경우,

  • 삭제될 노드 인덱스인데, 삭제될 부분은 별도

        public static final int DELETED_NODE = -10000;

  • 에 따라 음수 처리한다

  • 그리고 삭제될 노드의 인덱스를 부모로 가지는 노드를 탐색

    for (int i = 0; i < N; i++) {
        if (tree.get(i) == deletedNodeNumber) {
            dfs(i);
        }
    }

  • 요 부분임.

  • 암튼 탐색하여서, 해당 노드로 삭제처리를 위해 dfs 를 호출한다. 물론 매개변수는 삭제될 인덱스를 가져가야 할 것이다.