열혈 자료구조 - 8-2 이진 트리의 구현

이진 트리 구현의 두 가지 방법

- 배열 기반의 구현

    -> 노드에 번호를 부여하고 번호에 해당하는 번호를 배열의 인덱스 값으로 활용

    -> 위에서 아래로 왼쪽에서 오른쪽으로 번호를 매김

    -> 편의상 0번째 인덱스는 사용하지 않음

- 연결 리스트 기반의 구현

    -> 양방향 연결 리스트의 노드를 사용해서 자식 노드를 저장하는 방식

 

연결 리스트 기반의 이진 트리 구현

- 구조체 정의

    -> 이 한 구조체가 필요한 노드에 대한 정의이며 이진 트리를 정의할 수 있는 구조체

    -> 트리의 주소값은 루트 노드의 주소값

typedef struct _bTreeNode
{
	BTData data;
	struct _bTreeNode * left;			// 좌측 자식 노드
	struct _bTreeNode * right;			// 우측 자식 노드
} BTreeNode;

- 노드의 생성

BTreeNode * MakeBTreeNode(void)
{
	BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));		// 노드 동적 생성

	nd->left = NULL;	
	nd->right = NULL;		// 좌 우 NULL로 초기화
	return nd;			// 노드 주소 반환
}

- 노드의 데이터 반환 / 저장

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;
}

- 서브 트리 연결

    -> main에 부모 노드를 전달하고 sub에 연결하고자 하는 서브 트리 전달

    -> 단순히 노드 하나를 연결하는 것이 아닌 트리 자체를 붙일 수 있음

    -> 연결하고자 하는 위치에 노드가 연결되어 있다면 소멸시키고 연결

    -> 단순 노드가 아닌 서브 트리가 연결되어 있을 수 있으므로 '순회'를 통해 완전 제거

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

	main->left = sub;
}

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

	main->right = sub;
}

- Main

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);          
}