[Java] Tree와 BFS, DFS (child가 여러개)

Tree

https://medium.com/quantum-ant/트리-tree-cec69cfddb14

class Node<E> {
    E value;
    Node<E>[] childerns = null;

    public Node(E value, Node[] childerns) {
        this.value = value;
        this.childerns = childerns;
    }
}

일반적으로 이진Tree등 자식의 개수가 정해진 Tree를 많이 사용하는데 자식의 개수가 가변인(배열인) Tree를 만들어 봤습니다.

DFS, 깊이 우선 탐색

https://velog.io/@cptkuk91/treeDFS-깊이-우선-탐색-이해-Javascript

void DFS(Node node) {
    if (node == null) {
        return;
    }
    System.out.println(node.value);
    if (node.childerns != null) {
        for (Node n : node.childerns) {
            DFS(n);
        }
    }
}

void DFSwithStack(Node root) {
    Stack<Node> treeStack = new Stack<>();
    treeStack.push(root);
    while (!treeStack.isEmpty()) {
        Node node = treeStack.pop();
        System.out.println(node.value);
        if (node.childerns != null) {
            for (Node n : node.childerns) {
                treeStack.push(n);
            }
        }
    }
}

일반적으로 재귀함수를 많이 사용합니다. Stack으로도 구현할 수 있을 것 같아 구현 해보았습니다만, 일반적인 DFS와 달리 오른쪽(끝) 에서 부터 탐색합니다.
일반적인 왼쪽(시작) 부터 탐색하는 DFS는 재귀함수를 사용해야할 것 같습니다. Stack을 활용한 DFS는 Tree 보다는 Graph에서 사용하는 것 같습니다

BFS, 너비 우선 탐색

void BFS(Node root) {
    Queue<Node> treeQueue = new LinkedList<>();
    treeQueue.offer(root);
    while (!treeQueue.isEmpty()) {
        Node node = treeQueue.poll();
        System.out.println(node.value);
        if (node.childerns != null) {
            for (Node n : node.childerns) {
                treeQueue.offer(n);
            }
        }
    }
}

Stack을 활용한 DFS와 같지만 자료구조만 Queue 입니다.

테스트 코드

@Test
@DisplayName("treeAndDFSBFS")
void test() {
    Node<Integer>[] childern1 = new Node[3];
    Node<Integer>[] childern2 = new Node[2];
    childern2[0] = new Node<>(5, null);
    childern2[1] = new Node<>(6, null);
    childern1[0] = new Node<>(2, childern2);
    childern1[1] = new Node<>(3, null);
    childern1[2] = new Node<>(4, null);
    Node<Integer> root = new Node<>(1, childern1);
    DFS(root);
    System.out.println();
    DFSwithStack(root);
    System.out.println();
    BFS(root);
}

Node의 생성자에 바로 Node 배열을 넣는 것은 안되는 것 같습니다.

Tree의 모양은 이렇습니다.

1
2      3      4
5 6

DFS로 탐색하면 1, 2, 5, 6, 3, 4
Stack을 활용한 DFS로 탐색하면 1, 4, 3, 2, 6, 5
BFS로 탐색하면 1, 2, 3, 4, 5, 6 입니다.