트리 순회 구현

 

 

 

-트리 순회 구현

 

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)

이 된다.