그래프2 트리_그래프가 트리인지 확인하는 방법 그래프가 트리인지 확인하는 방법 - 트리는 노드 N개, 간선 N-1개를 가지면서 사이클이 없는 특징을 가진다. - 따라서 사이클이 있다면(탐색하는 과정에서 부모 이외의 이전에 방문했던 노드를 또 방문하게 된다면) 이는 트리가 아닌 그래프이다. #include #include #include using namespace std; int N, M; vector graph(15, vector(0)); vector visited(15, false); vector parent(15, 0); void setGraph() { scanf("%d %d", &N, &M); for (int i=0; i 2022. 2. 28. 이진트리순회_레벨순회(level)/전위순회(preorder)/중위순회(inorder)/후위순회(postorder) 트리 자료구조란 - 무방향이면서 사이클이 없는 연결그래프(즉, 트리는 그래프의 일종) - N개의 노드와 N-1개의 간선을 가짐 - 이진트리란, 트리 중 각 노드의 자식들이 2개 이하인 트리 - 이진트리를 순회하는 방식은 크게 레벨순회, 전위순회, 중위순회, 후위순회가 있음 레벨 순회(Level Order Traversal) - 트리의 루트부터 리프까지 계층적으로 순회하는 방식 - 가장 높은 층을 먼저 순회하며 큐로 구현 - 그래프에서의 bfs와 동일하게 구현하나, 사이클이 없기 때문에 이전에 방문한 노드를 별도로 체크해줄 필요가 없음(부모 노드만 기록) #include #include #include using namespace std; int N; vector graph(10, vector(0)); v.. 2022. 2. 27. 이전 1 다음