트리와 잣의 데이터 구조 및 변환
트리의 저장 방식
부모 표현법
각 노드를 배열로 관리하며, 각 요소는 데이터와 부모의 인덱스를 포함한다.
typedef struct {
TElemType data;
int parent; // 부모 노드의 인덱스
} PTNode;
#define MAX_TREE_SIZE 100
typedef struct {
PTNode nodes[MAX_TREE_SIZE];
int root; // 루트 위치
int count; // 총 노드 수
} PTree;
자식 ...
7월 27일 20:21에 게시됨
이진 트리와 힙 구조의 핵심 개념 및 응용
트리 구조 개요
트리는 계층적 관계를 표현하는 비선형 자료구조로, 유한 개의 노드로 구성된다. 루트 노드에서 시작하여 각 노드는 자식 노드들을 가질 수 있으며, 전체 구조는 순환하지 않는다.
기본 용어
노드의 차수(Degree): 자식 노드의 수. 예를 들어 A 노드가 3개의 자식을 가지면 차수는 3.
단말 노드(Leaf Node): 자식이 없는 노드.
부모/자식 노 ...
7월 24일 23:35에 게시됨
이진 트리 탐색 알고리즘 실습 - DAY12
알고리즘 기록 제12일 [이진 트리]
1. LeetCode 226. 이진 트리 뒤집기
주어진 이진 트리의 루트 노드를 기준으로 트리를 완전히 뒤집은 후, 새로운 루트를 반환하세요.
입력: root = [4,2,7,1,3,6,9]
출력: [4,7,2,9,6,3,1]
문제 링크
핵심 접근 방식:
재귀적 뒤집기: 현재 노드와 그 자식들을 순차적으로 처리하며 트리 전체를 재귀적으로 뒤집습니다.
자식 교환: 각 ...
7월 18일 17:37에 게시됨
후위 및 중위 순회로 전위 순회 복원하기
후위 순회와 중위 순회를 통해 전위 순회 구하기
이 문제는 주어진 후위 순회(후순서)와 중위 순회(중간순서) 시퀀스로부터 원래의 이진 트리 구조를 재구성하고, 이를 바탕으로 전위 순회(전순서)를 얻는 것입니다. 핵심은 트리의 재귀적 구성 원리를 이해하는 데 있습니다.
루트 노드 식별: 후위 순회에서 마지막 요소는 항상 현재 서브트리의 루트입니다.
중위 순회에 ...
7월 15일 01:34에 게시됨
이진 트리의 레벨별 출력 구현 방법
다음과 같은 이진 트리가 있다고 가정하자:
// 1
// / \
// 2 3
// / \ / \
// 4 5 6 7
이 트리를 레벨 단위로 출력해야 하며, 출력 형식은 다음과 같아야 한다:
1
2 3
4 5 6 7
이 문제는 너비 우선 탐색(BFS)을 활용하여 해결할 수 있다. 핵심 아이디어는 큐를 사용해 노드를 ...
7월 5일 21:47에 게시됨
이진 검색 트리의 최대 부분 트리 합계
1. 문제 출처
LeetCode 1373번 문제
2. 문제 설명
이진 트리의 루트 노드가 주어졌을 때, 부분 트리 중에서 이진 검색 트리(BST)를 이루는 것들의 최대 노드 합계를 반환하세요. BST 조건은 다음과 같습니다:
왼쪽 서브트리의 모든 노드 값이 현재 노드 값보다 작음
오른쪽 서브트리의 모든 노드 값이 현재 노드 값보다 큼
왼쪽/오른쪽 서브트리 모두 BST를 만족함 ...
6월 1일 01:44에 게시됨
이진 트리 순회 방법 (연결 구조와 순차 구조 활용)
Tree Traversals (25)
==========================
모든 이진 트리 노드의 키는 서로 다른 양의 정수입니다. 후위 순회 및 중위 순회 시퀀스가 주어지면 해당 이진 트리의 수준 순회 시퀀스를 출력해야 합니다.
입력 사양:
각 입력 파일은 하나의 테스트 케이스를 포함합니다. 각 케이스에서 첫 번째 줄은 이진 트리의 노드 수 N (<=30)을 나타냅니다. 두 번째 줄 ...
5월 25일 07:03에 게시됨