ddoeun_gongdaeimo

이진트리 ADT 구현과 메쏘드 배열에 기초한 이진트리 1D 배열을 이용한 이진트리 표현 순위 i의 노드의 대해 왼쪽 자식의 위치 순위 2i, 오른쪽 자식의 위치 순위 2i+1, 부모의 위치순위 i/2 0에 관한 연산 오류를 피하기 위해 순의 0셀은 사용하지않음, 사용하지 않는 셀도 표시 널마커('#')나 널포인터 만약 MAX를 노드 순위 중 최대값이라 하면 배열크기 N = MAX로 해야함 배열크기 N = n 인 경우가 최선임 이 경우는 크기 N인 배열의 순위 0을 제외한 모든 셀이 이진트리의 노드를 표현하는 데 사용되어 기억장소의 낭비가 전혀 없는 상황 편향이진트리가 최악의 경우가 됨 연결리스트에 기초한 이진트리 연결리스트에 기초하여 이진트리 저장 각 노드는 원소, 부모노드, 왼쪽 자식노드, 오른쪽 자식..

트리 용어 노드 : 데이터 원소 간선 : 노드 사이의 부모-자식 관계를 표시 루트 : 트리 맨 위에 있는 부모가 없는 노드 내부노드(중간노드) : 적어도 한 개의 자식을 가진 노드 외부노드(잎) : 자식이 없는 노드 형제 : 같은 부모를 가진 노드들 노드의 조상 : 루트를 향해 간선을 따라 올라가면 만나게 되는 부모, 조부모, 증조부모 등의 직계 상위 노드들 노드의 자손 : 잎을 향해 간선을 따라 내려가면 만나게 되는 자식, 손주, 증손주 등의 직계 하위 노드들 부트리 : 노드와 그 노드의 자손들로 구성된 트리 경로 : 조상 또는 자손을 따라 이어진 노드 시퀀스 경로길이 : 경로 내 간선의 수 노드의 깊이 : 루트로부터 그 노드에 이르는 유일한 경로의 길이 노드의 높이 : 그 노드로부터 외부노드에 이르는..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 전위순회 중위순회 후위순회를 차례로 출력하는 문제다. 재귀를 이용하는 방법이 먼저 생각이 나서 재귀함수를 만들어서 풀었다. 문제에서 예시로 준 트리이다. 각 순회마다 출력되는 순서는 다음과 같아야 한다. 전위순회 (루트-왼-오) : ABDCEFG 중위순회 (왼-루트-오) : DBAECFG 후위순회 (왼-오-루트) : DBEGFCA 어떤 부트리에서든지 각 순회의 순서가 지켜져야 한다. 그..