트리의 특징
2차원적 구조를 가짐.
이에 반해 자료구조 배열, 연결리스트, 스택, 큐...등은 1차원 선형적 구조를 갖음.
2014/02/28 - [프로그래밍/C언어] - 동적배열 자료구조의 시작
2014/03/20 - [프로그래밍/C언어] - 자료구조 - 연결리스트[linked list] C언어
2014/03/21 - [프로그래밍/C언어] - 자료구조 스택(stack) C언어
2014/03/22 - [프로그래밍/C언어] - 자료구조 큐(Queue) C언어
용어정리
차수 - 자식 노드의 개수
잎 - 자식 노드가 0인 노드
서브트리(sub Tree) - 트리 내부의 작은 트리
포리스트(Forest) - 트리가 여러 개 모인 것.
레벨(level) - 루트에서 그 노드까지의 거리를 말함.(루트레벨 :1)
높이 - 트리의 최대 레벨.
경로 - 특정 노드에서 특정 노드까지 가는 길. 트리의 경로는 1가지만 존재하는 특징이 있음.
(참고 : 그래프의 경로는 여러가지 가능)
트리는 대용량의 자료를 다룰 때 효과적이다.(자료의 삽입, 삭제,검색이 빠르다.)
Linked List와 비슷한 모양이다.
이 구조는 2진트리(Binary Tree)다.
2진트리는 차수의 개수가 2개 이하인 트리를 말한다. 차수는 얼마든지 늘릴 수 있지만, 기본적으로 2진 트리를 많이 사용한다.
아래는 간단히 트리를 사용해본 코드다
Node*형 변수 root는 전역으로 설정하여 초기화한다. inintTree는 root에 동적할당을 한다.
자식이 좌우로 다 있으면 메세지를 출력하고, 하나라도 비워 있으면 왼편부터 채워나간다.(순서있음)
트리의 순회는 재귀 방식을 사용한다. printf의 위치에 따라(3가지위치 가능) 출력순서가 달라진다. 다시 설명하겠다.
2014/02/26 - [프로그래밍/알고리즘] - 하노이탑 재귀호출 알고리즘
여기는 메모리해제 관련 코드가 없다.
메모리 해제관련 코드 또한 재귀호출을 이용한다. 해제를 하려면 2진트리의 순회방식을 알아야 한다.
2진 트리의 순회
왼쪽부터 PreOrder(전위순회), InOrder(중위순회), PostOrder(후위순회) 이라고 부른다.
아래는 코드는 PreOrder방식이다.
출력 위치에 따라서 순회방식이 달라진다.
printf 위치가 두 함수 호출 중간에 위치하면 중위
두함수 호출 후에 위치하면 후위 순회가 된다.
트리의 해제시에는 후위순회를 해야하는데 이유는 부모트리의 해제가 마지막에 이루어져야하기때문이다. 부모트리를 먼저 해제하면 자식트리를 참조할 포인터를 잊어버리게 되기 때문이다.
트리의 해제는 printf 대신 해제 코드를 넣으면 된다.