열혈 자료구조 - 8-3 이진 트리의 순회

순회의 세 가지 방법

- 루트 노드를 접근하는 시점에 따라 구분

- 중위 순회 : 좌측 -> 중앙(루트) -> 우측

- 후위 순회 : 좌측 -> 우측 -> 중앙(루트)

- 전위 순회 : 중앙(루트) -> 좌측 -> 우측

중위 / 후위 / 전위

- 높이가 2 이상일 경우에는 재귀적 성향이 들어감

 

순회의 재귀적 표현

- 중위 순회의 과정을 단순하게 코드로 작성하면 아래와 같이 쓸 수 있음

void InorderTraverse(BTreeNode * bt)
{
	InorderTraverse(bt->left);		// 왼쪽 서브트리 접근
	printf("%d \n", bt->data);		// 루트 노드 데이터 반환
	InorderTraverse(bt->right);		// 오른쪽 서브트리 접근
}

- 하지만 위 경우는 좌 / 우측이 서브트리가 아닌 단순 노드인 경우에는 문제가 생길 수 있음

    -> 탈출 조건이 없기 때문

- 계속 들어가다 위와 같은 모양의 서브트리가 나왔을 경우 (단순 노드만으로 구성된 트리) bt->left와 같은 주소값 만으로는 좌측에 있는 것이 단순 노드인지 서브 트리인지 알 수 없음

- 계속 호출이 되면 InorderTraverse의 인자에 NULL이 전달이 됨

- 이 부분을 이용해서 NULL을 받으면 return하게 설정하면 간단히 해결할 수 있음

void InorderTraverse(BTreeNode * bt)
{
	if (bt == NULL)		return;

	InorderTraverse(bt->left);		// 왼쪽 서브트리 접근
	printf("%d \n", bt->data);		// 루트 노드 데이터 반환
	InorderTraverse(bt->right);		// 오른쪽 서브트리 접근
}

- 전위, 후위는 위 단계의 배치만 바꾸면 됨

int main(void)
{
	BTreeNode * bt1 = MakeBTreeNode();
	BTreeNode * bt2 = MakeBTreeNode();
	BTreeNode * bt3 = MakeBTreeNode();
	BTreeNode * bt4 = MakeBTreeNode();

	SetData(bt1, 1);
	SetData(bt2, 2);
	SetData(bt3, 3);
	SetData(bt4, 4);

	MakeLeftSubTree(bt1, bt2);
	MakeRightSubTree(bt1, bt3);
	MakeLeftSubTree(bt2, bt4);

	InorderTraverse(bt1);
	return 0;
}

노드 방문 액션 추가하기

- 현재는 간단하게 순회하여 출력해주는 방식으로 구성

void InorderTraverse(BTreeNode * bt)
{
	if (bt == NULL)		return;

	InorderTraverse(bt->left);		// 왼쪽 서브트리 접근
	printf("%d \n", bt->data);		// 루트 노드 데이터 반환
	InorderTraverse(bt->right);		// 오른쪽 서브트리 접근
}

- 노드를 방문했을 때 하고자 하는 액션을 설정할 수 있음

- 원하는 액션의 함수 포인터

typdef void VisitFuncPtr(BTData data);

- 함수를 인자로 전달

void InorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
	if(bt == NULL)
		return;

	InorderTraverse(bt->left, action);
	action(bt->data);
	InorderTraverse(bt->right, action);
}


int main()
{
	...
	InorderTraverse(bt1, ShowIntData);
    ...
}
    
void ShowIntData(int data)
{
	printf("%d ", data);
}