[자료구조] 이진트리 ADT

이진 트리를 참조하는 함수를 구현할때는 
이진 트리의 성질인 "재귀"를 이용하는게 중요함
 
 

 
트리는 위와같은 서브트리가 반복적으로 나오는 구조이기 때문에 "재귀"를 활용할 수 있다.
 
그럼 단말노드는 어떻게 처리할까
저 2,3은 밑에 아무것도 없지 않은가?
그럼 노드 1개로 봐야하는거 아닌가?
 
재귀에서 가장 중요하고 반드시 필요한 탈출조건은 어떤 조건으로 구성해야할까
 

 
트리의 단말노드는 양쪽에 NULL값의 노드가 있다고 생각하면 된다.
 
따라서 만약 재귀로 쭉 내려가다 양쪽에서 NULL이 나온다? 
이러면 단말노드임을 확신하고 다시 위로 쭉쭉 올라가면 되는거임
 
즉, 단말노드까지 맨 위 구조로 되어있다고 생각하고 코드를 작성해도 되는 것이다
단말노드까지 재귀를 활용할 수 있게 된다

 

---

[이진 트리 기본 ADT 구현]

 

typedef int BTData;

typedef struct _bTreeNode {
	BTData data;
	BTreeNode* left;
	BTreeNode* right;
}BTreeNode;

BTreeNode* MakeBTreeNode(void) {
	BTreeNode* rootnode = (BTreeNode*)malloc(sizeof(BTreeNode));
	rootnode->left = NULL;
	rootnode->right = NULL;
	return rootnode;
}

BTData GetData(BTreeNode* bt) { 
	return bt->data;
}

void SetData(BTreeNode* bt, BTData data) {
	bt->data = data;
}

BTreeNode* GetLeftSubTree(BTreeNode* bt) {
	return bt->left;
}

BTreeNode* GetRightSubTree(BTreeNode* bt) {
	return bt->right;
}

void MakeLeftSubTree(BTreeNode* main, BTreeNode* sub) {
	if (main->left) free(main->left);
	main->left = sub;
}
void MakeRightSubTree(BTreeNode* main, BTreeNode* sub) {
	if (main->right) free(main->right);
	main->right = sub;
}

 

---

[이진 트리 중위순회(RECURSIVE)]

void InorderTraverse(BTreeNode* bt) {
	if (bt == NULL) return;
	InorderTraverse(bt->left);
	printf("%d",bt->data);
	InorderTraverse(bt->right);
}

사실 어떻게 순회하는지는 중요하지 않다.
그냥 상황에 따라 뭐부터 출력하고 어디부터 건드려볼건지 체크하면 된다.
위와 같은 경우는 LEFT -> BT -> RIGHT 순으로 간다.

 

---

[이진 트리 삭제 (RECURSIVE)]

void DeleteTree(BTreeNode* bt) {
	if (bt == NULL) return;
	DeleteTree(bt->left);
	DeleteTree(bt->right);
	free(bt);
}

 

---

 

참고로 시험때나 재귀로 짜지 프로그램으로 돌릴때는 스택/큐 이용하자

이때 DFS BFS 쓰면 된다