[C언어] 자료구조 - Tree 트리 순회,기본연산 -3

 

 

 

트리에 대해 적당히 알아보았고 이제

기본함수를 알기 전에 연결리스트로 트리를 구성했기 때문에 우선 순회라는 것을 알아야하는데

순회라는 것은 트리에 속하는 모든 노드를 한 번 씩 방문한다는 것으로 방문해서

데이터를 목적에 맞게 처리하기 위함이다. 

 

 

 

선형 자료구조에서는 순회방법이 단순하지만,, 얘는 알다시피 선형자료구조가 아니기 때문에 다른 방식이다.

아무튼 이진트리의 순위에는 4가지정도가 있다. 여기서는 3가지만 하겠다.

 

 

 

---

 

 

 

 

 

 

1. 전위 순회  VLR

2. 중위 순회  LVR

3. 후위 순회  LRV

4. 레벨순회

 

V는 value라고 보면된다. 자료를 의미한다.

 

---

 

우선 전위순회부터 알아보자.

스크립트를 먼저 보자면

 

void preorder(TNode *n){
	if(n != NULL){  // 루트를 가르키는 것이겠다.
		printf("[%c]", n->data);  //Value값 출력
		preorder(n->left);  // 왼쪽자식
		preorder(n->right);  // 오른쪽 자식
	}
}

 

순환함수를 써서 모든 노드를 탐색하는 것이다. 그런데 저 순서에 따라서 탐색하는 것일뿐

재귀를 이용해서 왼쪽 것 부터 다 불러오고 그다음 오른쪽을 뒤지고 있다.

 

---

 

중위순회는??

 

void inorder(TNode *n)
{
	printf("가");
	printf("%d", n);
	if(n != NULL){
		inorder(n->left);
		printf("b");
		printf("[%c]", n->data);
		printf("c");
		inorder(n->right);
	}
}

 

---

 

후위순회는?

 

void postorder(TNode *n)
{
	if( n != NULL){
		postorder(n->left);
		postorder(n->right);
		printf("[%c]", n->data);
	}
}

 

---

 

아무튼 순회하는 방법도 여러가지가 있다. 뭐 상황에 맞춰 순회하는 방법을 결정하면 되겠다.

순회방법에 따라 뭐 장단점이 있겠다

자식노드부터 처리하고 그 다음 부모노드를 불러온다면 후위순회를 하면 알맞겠고

부모노드부터 처리하고 그 다음 자식노드를 불러온다면 전위순회를 하면 좋다.

 

어차피 모든 노드를 순회하는것은 마찬가지다.

 

이제 순회방법도 알았으니까

 

---

 

 

이진트리의 연산을 알아볼까 한다..

이진트리에서는 여러가지랑 삽입까지만 배우고

다음 binary search tree에서 삭제를 배우도록하자 ㅎㅎ

 

거의 재귀를 이용한 것으로써

N번째 일때 이렇게 일어난다면..

1번째의 값이 정해진다면.. N도 구할 수 있는 거겠지?라는 생각에서 나오는 것이다.

수학적 귀납법을 거꾸로 생각하면 이해하기 조금 쉽다.

 

 

노드 개수 구하는 count 함수 

int count_node(TNode* n)
{
	if(n == NULL) return 0;  // 루트가 가리키는게 NULL이면 뭐 노드도 루트노드도  없으니 0이지
	return 1 + count_node(n->left) + count_node(n->right); // 그렇지 않으면 루트노드는 있는 것이고 자식들을 봐야지
}

 

 

 

단말노드의 개수 구하는 카운트 함수

(단말 노드란 자식노드가 없는 노드를 말한다)

int count_leaf(TNode* n)
{
	if( n == NULL) return 0;  //역시나 루트가 가리키는 게 없으면 걍 노드 자체가 없는거지
	if( n->left == NULL && n->right == NULL) return 1; // 왼쪽 자식, 오른쪽 자식이 없으면 그것이 바로 단말노드
	else return count_leaf(n->left) + count_leaf(n->right);  // 자식이 있으면 그 자식의 자식이 있는지 봐야겠지?
}

 

 

트리의 높이 구하는 함수

여기서는 참고로 ?라는 3항 연산자가 쓰였다.

** (bool 결과값)? v1 : v2   -- >  bool이 True면 v1값, False이면 v2값

 

int calc_height(TNode *n)
{
	int hleft, hright;
	if( n == NULL) return 0; // 역시나 노드자체가 없으니 높이 0
		hleft = calc_height(n->left);  // 왼쪽 자식들로 만든 높이를 반환
		hright = calc_height(n->right);  // 오른쪽 자식들로 만든 높이를 반환
		return ( hleft>hright)? hleft+1 : hright + 1 ;  // 그 후 둘 중 큰거 고름 참이면 왼쪽 거짓이면 오른쪽 값을 반환하는 것

}

 

노드를 만드는 함수

 

TNode *create_tree(TElement val, TNode* l, TNode* r)
{
	TNode* n = (TNode*) malloc(sizeof(TNode)); // 구조체랑 비슷하게 만듭니다 ㅎㅎ
	n->data = val;
	n->left = l;
	n->right = r;
	return n;  // 포인터를 반환해야하고 그 노드를 가리키는?? 그래야 추가를 하니까
}

 

 

뭐 메인함수를 이렇게 돌리는데.. 가장 중요한 것은 순서대로 돌려야한다!!!

자식부터 돌려야한다!! 그니까 자식이 있는 다음에 그 부모를 만드는 것이다.

사람하고 반대의 개념이긴하네

 

int main(){
TNode *b, *c, *d, *e, *f, *g, *h;

init_tree();
g = create_tree ('G',NULL,NULL);
h = create_tree ('H',NULL,NULL);
e = create_tree ('E',g,h);
f = create_tree ('F',NULL,NULL);
d = create_tree ('D',NULL,NULL);
b = create_tree ('B',d, NULL);
c = create_tree ('C',e,f);
root = create_tree('A',b,c);



}

 

 

이제 다음 번에는 BST에서 알아보고 트리에 대한 연산을 더욱 자세히 알아보도록 하자.