CH8-2 이진트리의 구현(2)

08-2. 이진 트리의 구현 ②

헤더를 보자.

#ifndef __BINARY_TREE_H__
#define __BINARY_TREE_H__

typedef int BTData;

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

/*** BTreeNode 관련 연산들 ****/
BTreeNode * MakeBTreeNode(void);
BTData GetData(BTreeNode * bt);
void SetData(BTreeNode * bt, BTData data);

BTreeNode * GetLeftSubTree(BTreeNode * bt);
BTreeNode * GetRightSubTree(BTreeNode * bt);

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);

#endif

이 구조체를 이해하는게 중요하다.

이전에 양뱡향 연결리스트를 구현할때, 노드와 양뱡향연결리스트 구조체를 따로 구분해서 코딩했다.

양뱡향뿐만 아니라 앞에서 구현한 자료구조들은, 자료구조를 표현한 구조체와 자료구조 표현에 필요한 노드 구조체 등을 따로 구현했음.

우리가 앞으로 만드려는건, 이진트리를 구성하는 도구이다. 이 도구의 대상은 자료구조를 표현한 구조체인가, 자료구조 표현에 필요한 노드 구조체인가?

정답은 후자이다. 왜? 왜 노드만 정의하고 이진트리를 구현하는 구조체는 다루지 않는가?

윤성우 님은 위의 강의안에서, 이진 트리의 노드를 표현한 구조체라는 표현을 그냥 이진트리를 표현한 구조체 라고 바꾸고 싶었다고 한다.

하나의 노드조차 이진트리이다. 이진트리의 정의에서 이는 공노드를 갖는 이진트리이기 때문. 이진트리라는게 따로 있는게 아니다. 즉 노드 하나를 표현하는 것이 곧 이진트리의 구현과 같다.

우리가 만드는건 도구라는걸 다시 기억하자. 도구를 통해 이진트리 표현을 만들고 나서는 만들어진 트리의 주소값만 기억하면 된다.

이제 위의 구조체를 살펴보겠다.

우리는 노드를 생성하는 함수(도구)를 이용해 위의 BTreeNode를 생성하고, 노드를 잇는 함수(도구)를 통해 이진트리를 구성할 것이다.

위에서 말한 트리의 주소는 곧 루트노드의 주소이다. 루트노드의 주소만 알면 이진트리의 노드에 다 접근가능하기 때문. 따라서 트리의 주소를 안다는 것은 루트노드의 주소를 안다는 것과 같고, 루트노드의 주소가 트리의 주소 전체를 대표한다.

위와 같은 이유로, 이진트리 전체를 아우르는 구조체같은건 필요없다. 루트노드의 주소만 알면 되기 때문.