수학과의 개발자 도전기

공부한 날짜: 2021.09.16

-트리는 나무를 닮은 자료구조이다.

-계층 데이터, 수식표현, 집합, 데이터 탐색에도 사용되는 활용도가 높은 자료구조 

-운영체제의 파일 시스템, xml의 dom(document object model),검색 엔진, 디비도 트리 자료구조에 기반해서 구현됨

-트리 용어

뿌리: 가장 위에 있는 노드 

가지: 루트와 잎 사이에 있는 모든 노드

잎: 가지 끝에 매달려 있는 노드 

관계: 부모,자식 관계가 있다 

경로(path) : 한 노드에서부터 다른 한 노드까지 이르는 길 사이에 놓여있는 노드들의 순서 

길이(length) : 출발 노드에서 목적지 노드까지 거쳐야 하는 노드의 개수를 의미 

깊이(depth): 루트 노드에서 해당 노드까지의 경로 길이를 의미함 

레벨(level): 깊이가 같은 노드의 집합 

높이(height) : 가장 깊은 곳에 있는 잎 노드까지의 깊이 

차수(degree) : 자식 노드의 개수, 트리의 차수 = 가장 많은 자식노드를 가진 노드의 차수 

-트리 표현하기 

1. 중첩된 괄호

: 같은 레벨의 노드들을 괄호로 같이 묶어 표현하는 방법 

2. 중첩된 집합

: 트리가 하위트리의 집합이라는 관계를 잘 보여주는 표현

3. 들여쓰기

:자료의 계층적인 특징을 잘 나타냄 

-노드 표현하기

(부모와 자식,형제 노드를 서로 연결짓는 방법)

1. N-link

: 노드의 차수가 n일 때, 노드가 n개의 링크를 가지고 있어서 이 링크들이 각각 자식 노드를 가리키도록 노드를 구성하는 방법(정확히는 잘 이해가 가지 않음,,)

차수가 노드마다 달라지는 트리에는 적용하기 어려움

2.왼쪽자식-오른쪽 형제 표현법

:한 노드의 모든 자식 노드를 얻으려면 일단 왼쪽 자식 노드에 대한 포인터만 있으면 됨

왼쪽 자식 노드의 주소를 얻은 후, 이 자식 노드의 오른쪽 형제 노드의 주소를 계속해서 얻어 나가면  결국에는 모든 자식노드를 얻을 수 있음

-트리 구현하기 (leftchild,rightsibling 방법으로 구현했음)

1. 노드 선언 

2. 함수 선언 

3. 트리 노드 생성 

생성 함수 구현시 malloc으로 자유저장소에 newnode 공간 확보하는 것 잊으면 안됨! 그리고 newnode 주소 반환하는 것도. 

4. 트리 노드 제거 

5. 트리 제거 

destroytree 구현부에 destroytree를 쓰는 것으로 보아 재귀함수인가? 하는 생각이 듦.

tree를 제거할 때는 root를 파라미터로 넣고 rightsibling,leftchild를 제거하는 방식으로 감 

6. 자식노드 추가하기 

자식 노드는 parent의 leftchild의 rightsibling으로  연결해야하므로 그거 Null 여부 확인한 다음에 연결. 

7. 트리 출력