본문 바로가기
728x90
반응형

Datastructure

[8] 트리 ⑦ 응용 (2) : 폴더 용량 출력 프로그램 2024. 6. 8. 트리 2주 차: 트리의 순회[ 문제 1 ] 위 트리에 대해 순회 방법과 폴더 id가 주어지면, 아래의 트리의 루트노드에서 출발하 여 해당 노드를 탐색하여 찾고, 이 노드를 시작점으로 순회하며 각 폴더의 용량을 출력하는 프로그램을 작성하시오. - 노드 id를 저장하기 위해 노드는 다음과 같은 구조체를 만들어 사용함. - 지난주 문제의 F1, F2와 같은 노드별 포인터는 사용할 수 없으며, 주어진 노드를 탐색하여 찾아 야 함.입출력 상세: ◦ 순회 방법 종류 (입력)- 1: 전위순회, 2: 중위순회, 3: 후위순회 ◦ 존재하지 않는 폴더 이름이 입력되는 경우 –1을 출력이진 트리와 순회 알고리즘 해석이번 포스팅에서는 이진트리의 노드 생성과 전위, 중위, 후위 순회 알고리즘을 설명합니다. 각 함수와 알고리즘의..
[8] 트리 ⑦ 응용 (2) : 폴더 용량 출력 프로그램 2024. 6. 6. 트리 2주 차: 트리의 순회[ 문제 1 ] 위 트리에 대해 순회 방법과 폴더 id가 주어지면, 아래의 트리의 루트노드에서 출발하 여 해당 노드를 탐색하여 찾고, 이 노드를 시작점으로 순회하며 각 폴더의 용량을 출력하는 프로그램을 작성하시오. - 노드 id를 저장하기 위해 노드는 다음과 같은 구조체를 만들어 사용함. - 지난주 문제의 F1, F2와 같은 노드별 포인터는 사용할 수 없으며, 주어진 노드를 탐색하여 찾아 야 함.입출력 상세: ◦ 순회 방법 종류 (입력)- 1: 전위순회, 2: 중위순회, 3: 후위순회 ◦ 존재하지 않는 폴더 이름이 입력되는 경우 –1을 출력이진 트리와 순회 알고리즘 해석이번 포스팅에서는 이진트리의 노드 생성과 전위, 중위, 후위 순회 알고리즘을 설명합니다. 각 함수와 알고리즘의..
[8] 트리 ⑥ 응용 (1) : 연결리스트를 이용한 트리 구현 2024. 6. 5. 트리 1주차: 이진 트리 삽입과 탐색 [연결리스트를 이용한 이진 트리] 이진트리의 노드에 저장되는 정보- data: 노드에 저장되는 값 (아래 문제에서 폴더의 용량) - left: 좌측 child 노드를 가리키는 링크- right: 우측 child 노드를 가리키는 링크 이진 트리를 이용한 폴더 구조 표현- 이진트리는 최대 2개의 자식 노드를 갖음.- 컴퓨터의 폴더 구조가 이진 트리 형태로 구성되어 있다고 가정함. - 각각의 노드는 폴더 이름과 용량을 나타내며, 아래 트리에서 폴던 F1에는 20M 가 저장되 어 있음을 의미함.[ 문제 1 ] 위 트리를 연결리스트를 이용해서 구현하고, 주어진 노드에 대해 자신과 왼쪽 자식, 우측 자식의 용량을 순서대로 출력하시오. ※ 참고사항: 실습 및 테스트 용이성을 위해..
[8] 트리 ⑤ 스택을 이용한 이진 트리 2024. 6. 4. 스택과 이진트리 정의스택 (Stack)스택은 선형 자료구조로, 가장 나중에 삽입된 데이터가 가장 먼저 삭제되는 LIFO(Last In First Out) 특성을 가집니다. 주요 연산으로는 데이터 삽입(Push), 삭제(Pop), 피크(Peek), 공백 상태 검출(IsEmpty), 포화 상태 검출(IsFull) 등이 있습니다.이진 트리 (Binary Tree)이진 트리는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조입니다. 각 노드는 데이터를 포함하며, 왼쪽 자식 노드와 오른쪽 자식 노드를 가리키는 포인터를 가집니다. 주요 순회 방식으로는 전위 순회(Pre-order), 중위 순회(In-order), 후위 순회(Post-order) 등이 있습니다.스택 구조체 설명스택(Stack)은 후입선출(L..
[8] 트리 ④ 레벨 순회 : 원형 큐 이용 2024. 6. 3. 이진트리의 레벨 순회 (Level Order Traversal)이진트리는 각 노드가 최대 두 개의 자식을 가지는 트리 자료구조입니다.이진트리의 순회 방식 중 하나인 레벨 순회는 노드를 깊이(depth) 순서대로 방문합니다. 즉, 루트 노드에서 시작하여 같은 깊이의 노드를 왼쪽에서 오른쪽으로 방문한 후, 그다음 깊이의 노드를 같은 방식으로 방문하는 방법입니다. 레벨 순회는 큐(Queue)를 사용하여 구현할 수 있습니다.같은 깊이의 노드를 왼쪽에서 오른쪽으로 방문한 후, 그 다음 깊이의 노드를 같은 방식으로 방문하는 방법레벨 순회의 필요성 및 활용레벨 순회는 다음과 같은 상황에서 유용하게 사용됩니다: 1. 최단 경로 문제: 트리의 특정 노드에서 가장 가까운 노드를 찾을 때 유용합니다.2. 그래프의 너비 우선..
[8] 트리 ③ 원형 큐 2024. 6. 3. 원형 큐를 이용한 이진트리 구현원형 큐를 이용하여 이진 트리를이진트리를 구현하는 과정과 그 코드에 대해 설명드리겠습니다. 이번 포스팅에서는 C 언어로 작성된 코드를 사용하여 원형 큐를 구현하고, 이를 이용하여 이진트리를 구성하는 방법을 살펴보겠습니다.원형 큐원형 큐(Circular Queue)는 선형 큐에서 마지막 위치와 첫 번째 위치를 연결하여 하나의 원처럼 만든 자료 구조입니다. 이러한 구조를 통해 원형 큐는 선형 큐의 단점을 보완하여 효율적인 메모리 사용이 가능하게 합니다.원형 큐와 일반큐의 차이점큐는 FIFO(First In, FirstOut) 구조를 가지고 있어, 먼저 들어온 데이터가 먼저 나가는 특징을 갖습니다. 원형 큐와 일반 큐는 이러한 기본적인 큐의 특성을 공유하지만, 메모리 사용과 구현..
728x90
반응형

티스토리툴바