[DS] chapter8 트리 -2

[08-3] 이진 트리의 순회 (Traversal)

 

순회가 필요한 이유는 삭제할 서브트리가 2개라면 한번의 free함수 호출이 전부이므로 메모리 누수로 이어질수있다.

 

순회의 종류:

 

- 전위 순회( Preorder Traversal)

 

- 중위 순회(Inorder Traversal)

 

- 후위 순회( Postorder Traversal)

---

 - 높이가 2이상인 이진트리의 순회법

1단계 : 왼쪽 서브트리 순회

2단계: 루트노드의 방문

3단계: 오른쪽 서브 트리의 순회 

 

void InorderTraverse(BTreeNode * bt)
{
    InorderTraverse(bt->left); // 1단계 왼쪽 서브트리의 순회
    printf("%d \n", bt ->data); // 2단계 루트 노드의 방문 (이게 방문으로~)
    InorderTraverse(bt->right); // 3단계 오른쪽 서브 트리의 순회
    
}

 

재귀 탈출 조건을 넣어야하는데 (*왜냐하면 공집합인 트리가 있을수있으니)

 

고로 노드 L의 오른쪽 서브 트리가 NULL이므로 함수에 NULL이 전달되기 때문이다.

 

void InorderTraverse(BTreeNode * bt)
{
	if (bt == NULL) //bt 가 null이면 재귀탈출!!!!
    	return;

    InorderTraverse(bt->left); // 1단계 왼쪽 서브트리의 순회
    printf("%d \n", bt ->data); // 2단계 루트 노드의 방문 (이게 방문으로~)
    InorderTraverse(bt->right); // 3단계 오른쪽 서브 트리의 순회
    
}

위에는 중위 순환 방법인데 전위 순환 후위 순환도 순서를 바꿔주면 끝.

---

-노드의 방문 이유!

저자는 노드의 방문목적은 단지 데이터의 출력이 아니라고함. 따라서 방문했을때 할 일을 결정 할 수 있도록 포인터를 사용하여 변경.

typedef void (*VisitFuncPtr)(BTData data);
void InorderTraverse(BTreeNode *bt, VisitFuncPtr action)

 

<출처 -윤성우의 열혈 자료구조>