이진 트리 -<자료구조 11>

hans·2022년 5월 3일

자료구조 공부 정리

목록 보기

11/14

글에 앞서

요번에는 이진트리의 구현에 대해 공부한 내용을 정리하려고 한다
비선형 자료구조에 대해 계속 공부하면서 확실히 선형 자료구조 보다
어렵다고 생각하지만 차근차근 배운것들을 정리해 나가보니 개념에 대해 조금씩 이해가 가고있다

이진 트리의 구현

이진트리의 종류

이진트리는 크게 2가지 종류로 구현이 가능하다

- 1.연결 리스트 이진 트리
- 2.배열 기반 이진 트리

각각이 어떻식으로 구현 되는지에 대해 알아보자

1.연결 리스트 이진 트리

그림을 보면 연결 리스트 기반 이진트리는 구현은 그림으로 볼때 직관적으로 이해하기가 쉽다
루트 노드 A가 B,C를 그리고 노드B가 D,E를 가키키게 만들어서 이진 트리를 구현한다

2.배열 기반 이진 트리

연결 리스트 기반 이진 트리와의 차이점을 살펴보자
먼저 이진 트리 노드 위의 숫자가 적혀있는것을 볼수있고 그 숫자를 기반으로 배열에 데이터를 저장한것을 확인할수있다
여기서 우리가 한 가지 집고 갈것은 배열의 첫번째 배열에는 값을 비워 두었다는 것이다
이것은 배열 이진 트리의 구현에서 첫번째를 비워두는 것이 여러모로 편하기 때문이다

이진 트리의 구조체 정의

typedef int BTData;

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

위 코드는 이진 트리 관련 헤더파일에서 이진 트리 구조체와 관련된 코드를 가지고 온거다
여기서 우리가 재밌게 생각해 볼것은 노드의 정의 자체가 자료구조의 정의를 의미한다 는점이다
우리가 자료구조를 공부 하면서 구현에 있어 노드와 자료구조를 각각 구분하여 구조체를 정의해 왔다
(예시 스택 에서 노드와 스택을 각각 구분함)
하지만 연결 리스트 기반 이진 트리에서는 노드 자체가 이진트리를 표현하고 있다
우리가 A라는 노드를 한개 생성했다고 가정하고 각각의 left와 right에 null 값을 넣었다고 가정한다면
위 그림처럼 이진트리가 형성되었다는 사실을 알수있다

이진 트리의 ADT 정의

1.BTreeNode * MakeBTreeNode(void);
-이진 트리 노드를 생성하고 주소값을 반환 한다.

2.BTData GetData(BTreeNode * bt);
-노드에 저장된 데이터를 반환한다.

3.void SetData(BTreeNode * bt, BTData data);
-노드에 데이터를 저장한다.data로 전달된 값을 저장한다.

4.BTreeNode GetLeftSubTree(BTreeNode bt);
-왼쪽 서브 트리의 주소 값을 반환한다.

5.BTreeNode GetRightSubTree(BTreeNode bt);
-오른쪽 서브 트리의 주소 값을 반환한다.

6.void MakeLeftSubTree(BTreeNode main, BTreeNode sub);
-왼쪽 서브 트리를 연결한다.

7.void MakeRightSubTree(BTreeNode main, BTreeNode sub);
-오른쪽 서브 트리를 연결한다.

이진 트리의 ADT 구현

1.BTreeNode * MakeBTreeNode(void);

BTreeNode * MakeBTreeNode(void)
{
	BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));

	nd->left = NULL;
	nd->right = NULL;
	return nd;
}

2.BTData GetData(BTreeNode * bt);

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

3.void SetData(BTreeNode * bt, BTData data);

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

4.BTreeNode GetLeftSubTree(BTreeNode bt);

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

5.BTreeNode GetRightSubTree(BTreeNode bt);

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

6.void MakeLeftSubTree(BTreeNode main, BTreeNode sub);

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
	if(main->left != NULL)
		free(main->left);

	main->left = sub;
}

7.void MakeRightSubTree(BTreeNode main, BTreeNode sub);

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
	if(main->right != NULL)
		free(main->right);

	main->right = sub;
}

6,7번 함수 코드를 정리해보자면
"왼쪽 오른쪽에 서브 트리가 존재한다면,해당 트리를 삭제하고 새로운 서브 트리를 연결해라 " 라고 해석할수 있을거다
위의 코드 방식은 한가지 중요한 문제점을 가진다
만일 삭제하는 서브 트리가 1개의 노드로 구성되어있다면 문제가 발생하지 않지만
2개 이상이라면 메모리 누수가 발생하게 된다