-트리 순회 구현
typedef struct TREE {
int value;
struct TREE* left;
struct TREE* right;
} TREE;
먼저 TREE라는 구조체를 만들어 줍니다.
value는 데이터값, left는 왼쪽자식, right는 오른쪽 자식을 의미합니다.
void display(TREE* t) {
if(t) {
display(t->left);
printf("%d", t->value);
display(t->right);
}
}
루트의 주소를 담고 있는 t라는 포인터를 매개변수로 받는다.
display(t->left)로 왼쪽 재귀호출,
display(t->right)로 오른쪽 재귀호출을 함으로써 모든 노드를 방문할 수 있다.
출력하는 printf구문을 위 코드와 같이 두 display함수 가운데에 두면 중위순회,
위에 두면 전위순회,
아래에 두면 후위순회가 된다.
t를 루트, t->left를 왼쪽 자식, t->right를 오른쪽 자식 방문이라고 생각하면 된다.
위의 트리를 예로 들어보면 함수의 진행 원리는 다음과 같다.
void display(TREE* t) {
if(t) {
display(t->left);
printf("%d", t->value);
display(t->right);
}
}
먼저 t는 루트를 의미한다.
if(t) 에서 t가 존재하기 때문에 아래 코드로 진입해준다.
display(t->left) 코드에 의해 루트에서 왼쪽으로 방문하게 된다. 여기서 함수 안에 같은 함수가 있기 때문에 printf로 넘어가지는 못하고 t가 NULL이 될 때 까지 display(t->left)를 반복해준다.
그렇게 되면 t가 1의 주소를 갖고 있을 때까지 계속 내려갈 것이고 그 후에 t는 NULL이 될 것이다.
그렇게 t가 NULL이 되고 나면 if(t) 에서 t가 존재하지 않게 되기 때문에 밀려있던 printf, display(t->right) 함수가 실행된다.
위 예시 트리로 중위 순회 순서를 정리해보면
t (6) > left (4) > left (2) > left (1) > left (NULL) > printf (1) > right (NULL)
> printf (2) > right (3) > left (NULL) > right (NULL)
> printf (4) > right (5) > left (NULL) > right (NULL)
> printf (6) > right (8) > left (7) > left (NULL) > printf (7) > right (NULL)
> printf (8) > right (9) > left (NULL) > printf (9) > right (NULL)
이 된다.
'자료구조 & 알고리즘' 카테고리의 다른 글
힙(Heap), 힙화(Heapify), 최댓값, 최솟값 구하기, 구현 (0) | 2023.02.25 |
---|---|
이진탐색트리 노드 삭제 개념, 구현 (0) | 2023.02.24 |
이진탐색트리 최댓값, 최솟값 노드 찾기, 구현 (0) | 2023.02.23 |
이진 탐색 트리 특징, 노드삽입, 구현 (0) | 2023.02.22 |
트리의 용어, 종류, 트리 순회 (0) | 2023.02.20 |
댓글