[자료구조 과제] - 11주차 완전 이진 트리

1. 과제 안내문

---

이번 과제는 노드 번호가 nMaxNo까지 노드를 가지는 완전 이진트리를 생성하고, 노드 번호를 부여하는 규칙에 의하여 노드 번호가 nNo인 노드를 찾는 과제이다. 이진트리를 레벨 순회로 노드의 번호를 출력하면 트리의 모습을 쉽게 알 수 있다. 왜냐 하면 1 레벨은 노드가 1, 2 레벨은 노드가 2개, 일반적으로 n 레벨은 노드가 2n-1개이기 때문에 앞에서 레벨에 따라 개수를 분리하여 생각하면 그 구조를 쉽게 알 수 있다. 이 과제는 번호가 nMaxNo까지 가지는 완전 이진트리를 생성하고, 이 트리를 레벨 순회에 따라 노드 번호를 출력한다. 그리고 노드 번호 nNo를 가지는 노드를 찾아 올바르게 찾았는지를 확인한다. 수업시간에 실습을 통하여 마지막 노드를 가리키는 원형 리스트를 사용하여 큐를 구현하여 레벨 순회를 하면서 아래와 같이 설계한 큐의 연산자를 사용하였다.

 

void AddQ(QueuePtr &pQueue, TreePtr pTree); // pQueue에 pTree를 삽입한다.

TreePtr DeleteQ(QueuePtr &pQueue); // pQueue에 삭제한 데이터를 반환한다.

 

그런데 이번 과제에서는 큐의 연산자를 아래와 같이 설계한다. 자세한 내용의 프로그램 코드에서 주석을 확인하기 바랍니다.

 

QueuePtr AddQ(QueuePtr pQueue, TreePtr pTree); // 삽입하고 수정된 큐를 반환한다.

QueuePtr DeleteQ(QueuePtr pQueue, TreePtr &pData); // 삭제한 데이터를 저장, 수정된 큐를 반환한다.

---

 고백하자면...... 이번 과제가 제 인생에서 제일 오래걸린 과제가 아닐까 싶다...... 이진트리의 개념 자체가 어렵다기보다는 그것을 구현하는 과정에서 순환함수를 사용해야하는데, 나는 순환함수에 매우 잼병이기 때문이다 ㅠㅠ ( 다른걸 더 잘한다는 것은 아닙니다 ㅎㅎ) 이번 과제를 정리하자면 완전이진트리의 메소드를 구현하는 것이라고 할 수 있다. 다음은 실행 예제이다.

 

2. 시행결과 예시

---

노드 개수 ? 10

------------

[New Complete Tree]

Node Ctr ? 10

Lvl Trvrs : 1 2 3 4 5 6 7 8 9 10

 

Node No ? 1

Node Data : 1

 

Node No ? 9

Node Data : 9

 

Node No ? 10

Node Data : 10

 

Node No ? 11

Node Data : -1

 

Node No ? 0

 

[New Complete Tree]

Node Ctr ? 20

Lvl Trvrs : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

 

Node No ? 19

Node Data : 19

 

Node No ? 20

Node Data : 20

 

Node No ? 21

Node Data : -1

 

Node No ? 0

 

[New Complete Tree]

Node Ctr ? 30

Lvl Trvrs : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

 

Node No ? 29

Node Data : 29

 

Node No ? 30

Node Data : 30

 

Node No ? 31

Node Data : -1

 

Node No ? 0

 

[New Complete Tree]

Node Ctr ? 0

Bye, ...

---

 위에 시행 결과를 보면, 트리를 출력하는 방법은 레벨 우선 탐색이다. 큐를 사용해서 구현하였는데, 이는 코드 구현 단락에서 설명할 것이다. 트리의 요소를 레벨 우선 탐색으로 출력을 한 다음에는 정수값을 받아 해당 값이 요소인 트리의 주소를 구현하면 된다. 중요한 점은 이 부분을 순환함수로 구현해야한다는 것이다.

 

3. 코드 구현

 

 메소드를 정의하기 전에 코드를 조금 더 쉽게 이해하기 위해 구조체를 먼저 공개하겠다.

typedef struct node1 {		
	int	nData;
	struct node1 *lChild;
	struct node1 *rChild;
}	Node1, *Node1Ptr, *TreePtr;

typedef struct node2 {		
	TreePtr	pData;
	struct node2 *link;
}	Node2, *Node2Ptr, *QueuePtr;

 

- 트리 생성 메소드

 

 트리의 생성 또한 순환함수로 작성하였다. 사실 교수님의 강제성이 있긴 했지만 아무리 생각해도 트리의 생성은 순환함수로 구현하는 것이 더 간편한 것 같다. 여기서 생각해야 할 점은 마지막 잎사귀 노드들의 link는 NULL을 가리켜야 한다는 것이다. 간단하게 알고리즘을 정리하자면 최대 노드 수를 max라고 했을 때, 부모 노드의 수를 n이라고 가정하자, n * 2 + 1 이 max를 넘지 않는 다면 왼쪽 자식은 n * 2, 오른쪽 자식은 n * 2 + 1을 해당 값으로 넣어주면 된다. 다음은 나의 코드이다.

TreePtr MakeTree(int nMaxNo, int nNo)
{	
	TreePtr tree = new Node1;
	tree->nData = nNo;
	if (nNo * 2 <= nMaxNo) {
		if (nNo * 2 <= nMaxNo) 
			tree->lChild = MakeTree(nMaxNo, nNo * 2);
		if (nNo * 2 + 1<= nMaxNo)
			tree->rChild = MakeTree(nMaxNo, nNo * 2 + 1);
		else
			tree->rChild = NULL;
	}
	else 
		tree->lChild = tree->rChild = NULL;
	return tree;
}

 다시 한번 말하지만 저는 나의 코드는 절대 정답이 아니다...... 분명 이보다 더 좋은 방법이 있을 것이다. 때문에 나의 코드를 참고하시는 분들은 이 코드가 최선이 아니라는 것을 생각해두시길 바란다 ㅠㅠ

 

- 트리를 요소로하는 큐의 add와 delete메소드 구현

 

 왜 트리를 요소로 하는 큐를 구현하라는 거지? 라는 생각이 드는 것은 당연하다. 다만 레벨 순회를 위한 필수 과정이라고만 생각하자! 큐는 앞 시간에서도 자료구조이다. 다른 점이 있다면 저장되는 값이 정수가 아닌 포인터 라는 것이다. 다음은 내가 작성한 큐의 메소드들이다.

QueuePtr AddQ(QueuePtr pQueue, TreePtr pTree)
{	
	QueuePtr pNew = new Node2;
	if (pNew) {
		pNew->pData = pTree;
		if (pQueue) {
			pNew->link = pQueue->link;
			pQueue = pQueue->link = pNew;
		}
		else
			pQueue = pNew->link = pNew;
	}
	return pQueue;
}

QueuePtr DeleteQ(QueuePtr pQueue, TreePtr &pData)
{	
	if (pQueue) {
		QueuePtr pDel = pQueue->link;
		pData = pDel->pData;
		if (pDel != pQueue) {
			pQueue->link = pDel->link;
		}
		else
			pQueue = NULL;
		delete pDel;
	}
	return pQueue;
}

 

- 레벨 순회 구현

 

 레벨 순회를 처음 들었을 때는 막막하기도 하였다. 그러나 구현 방법을 듣고나면 코드를 통한 구현은 어렵지 않다. 알고리즘을 정리하자면, 첫 노드를 add해준 후, delete를 하여 나온 트리의 왼쪽 자식과 오른쪽 자식을 차례로 추가해준다. 이 방법을 트리의 모든 요소를 만날 때 까지 반복하면 된다. 다음은 나의 소스 코드이다.

void LevelTrvs(TreePtr pTree)
{	
	QueuePtr pQueue = NULL;
	pQueue = AddQ(pQueue, pTree);
	printf("Lvl Trvrs : ");
	while (pQueue) {
		pQueue = DeleteQ(pQueue, pTree);
		printf(" %d", pTree->nData);
		if (pTree->lChild) {
			pQueue = AddQ(pQueue, pTree->lChild);
		}
		if (pTree->rChild) {
			pQueue = AddQ(pQueue, pTree->rChild);
		}
	}
	printf("\n\n");
}

 

- 탐색 함수 구현

 

 드디어 대망의 탐색 함수이다...... 함수의 기능을 설명하자면 1부터 10의 노드를 만들었을 때 6을 입력한다면 6을 요소로 가지고 있는 트리를 반환하는 함수이다. 이것을 순환함수로 만들었을 때 정말 큰 어려움이 있었다. 생성 함수는 return문이 없다 때문에 왼쪽과 오른쪽을 모두 돌아다닐 수 있는데, 탐색 함수는 두개의 return 문을 사용해야하기 때문에 왼쪽노드를 따라가다보면 최종적으로 돌아오는 함수에서 return문이 실행되어 모든 노드를 탐색하지 못한다. 이렇게 글로만 읽으면 복잡할 수 있겠지만 다음은 잘못된 예의 코드이다.

 

TreePtr FindTreeByNo(TreePtr pTree, int nNo)
{
	if (nNo == 1)
		return pTree;

	if (pTree) {
		if (pTree->nData == nNo / 2)
			return nNo % 2 ? pTree->rChild : pTree->lChild;
	}
	else
		return NULL;
        
	return FindTreeByNo(pTree->lChild, nNo);
	return FindTreeByNo(pTree->rChild, nNo);
}

 

 만약 코드를 이런식으로 작성한다고 하면, 중단 조건은 이루어질 수 있지만, 마지막 두개의 return 문 때문에 왼쪽 자식들은 탐색할 수 없는 상황이 발생한다. 내가 생각한 해결방법은 결국 모든 자식노드가 탐색되어야 하고, 이 부분을 하나의 return문으로 합쳐야 한다고 생각했기 때문에 두 함수의 결과값을 더해버렸다. 다음은 정상적으로 작동되는 코드이다.

 

TreePtr FindTreeByNo(TreePtr pTree, int nNo)
{
	if (nNo == 1)
		return pTree;

	if (pTree) {
		if (pTree->nData == nNo / 2)
			return nNo % 2 ? pTree->rChild : pTree->lChild;
	}
	else
		return NULL;
	
	return (TreePtr)((int)FindTreeByNo(pTree->lChild, nNo) + (int)FindTreeByNo(pTree->rChild, nNo));
}

 

 이렇게 한다면 왼쪽 자식노드에 닶이 없을 때 NULL이 반환되고 오른쪽 자식들을 탐색할 것이고, 왼쪽에 답이 있어도 어차피 오른쪽은 NULL이 반환 될테니 답에는 문제가 없다. 결국은 잘 작동 된다는 것이다.

 

3. 결어

 

부끄럽지만 이 과제를 수행하는데 순환함수의 문제 때문에 시간이 꽤 걸렸다. 다음은 이 블로그에 순환함수에 대해서도 정리했으면 좋겠다.