(Tree)완전 이진 트리인지 검사하는 함수

이 글의 코드를 기반으로 작성한 코드이다.

Tree 자료구조 (tistory.com)

 

 

 

완전 이진트리가 무엇이냐 하면, 이것을 보고 있다면 알고 있을테니 생략을 한다.

완전 이진트리를 배울때 왼쪽으로 차있으면 어떻고,,,오른쪽이 차있으면 저떻고,,,

그러다 보니 검사함수에 조건문으로 왼쪽이 있냐 오른쪽이 있냐에 메달리게 되었었다.

일단 검사를 하는 것에 있어 같은 레벨의 노드를 차례대로 검사하는 것이 가장 편리할 것이기에

레벨 순회를 쓸 것이다.

아...근데 문제가 너무 어렵네...? 그래서 구글링을 했다. 레벨순회를 하면서 왼쪽을 검사하고, 오른쪽을 검사하고,,

물론 그 솔루션들도 정말 좋은 방법일 것이다. 하지만...하지만 뭔가 마음에 걸리는 찝찝함....

우리가 2차원 배열을 배울때 꼭 함께 배우는 개념이 있다. 사람들이 편의상 2차원으로 생각하지만, 

사실 메모리 안에서는 그저 일렬로 늘어선 배열일 뿐이다라고...그렇다면, 우리가 생각하는 LEVEL이란 개념도

사실 편의적인 것뿐인거 아닐까? 큐의 입장에선 그냥 데이터가 정해진 순서대로 들어가고 나가는 것 뿐이라는 것이다.

그런 시각에서 완전 이진트리의 정의를 생각해 본다면, 데이터와 데이터 사이에 공백이 없는 상태, 그리고 그 중간에 공백이 존재한다면 완전해지지 않는 다는 것. 이라는 정의로 해석해 볼 수 있다. 여기서 아이디어를 떠올릴 수 있는 물건이 있었는데 바로 '책'이다. 책을 한장 한장 넘겨가다 내용이 없는 페이지가 나왔다. 이게 내용이 있는 페이지 사이에 있는 공백페이지 인지, 제일 끝페이지 인지 확인 하려면 어떻게 해야할까? 바로, 그냥 다음페이지로 넘겨보면 된다.

bool isFull() {
		if (!isEmpty()) {
			CircluarQueue q;
			q.enqueue(root);
			while (!q.isEmpty())//LEVEL 순회 코드를 활용했다.//
			{
				BinaryNode* node = q.dequeue();
				if (node == NULL) {//빈페이지면 코드에 돌입한다.//
					if (q.isEmpty()) {//제일 끝페이지 이면//
						return true;//완전이진트리//
					}
					node = q.peek();//다음페이지를 본다.//
					if (node != NULL) {//다음페이지에 내용이 있으면//
						return false;//완전 이진트리가 아니다.//
					}
					continue;
				}
				if (node != NULL) {
					q.enqueue(node->getLeft());
					q.enqueue(node->getRight());
				}
			}
			return true;
		}
		else return false;
	}

코딩을 배울때 마다 어려운 문제에 봉착하거나, 이해가 안될땐 나만의 개념을 만들었었다. 워크스테이션,챕터,골대변수,싱크로,,,,지금 문제의 책에서 아이디어를 얻은 페이징,,,이게 남들이 보기에는 굳이?싶을 순 있겠지만, 난 나름 이렇게 배우는게 재밌다.

그리고 찾지 못한 오류가 있을 수 있으나, 여러번 검수해본 결과는 알맞게 나왔다.