글 읽기 - 트리 구현 중 자식포인터 할당에 대해 질문드립니다.

jh1one 5년 전 0

트리를 구현하다가 이해가 안되는 점이 있어 질문드립니다.

1991 문제에서는 <부모 왼쪽자식 오른쪽자식>과 같은 포맷으로 노드를 입력하고 있습니다.

노드 삽입 시 부모 노드를 탐색해야 해서,
각 노드를 <데이터, 왼쪽자식포인터, 오른쪽자식포인터>를 갖도록 하였고
트리객체는 모든 노드를 treeArr라는 배열에 넣어 관리하도록 하였습니다.

그런데 노드 삽입 도중 트리의 높이가 3을 초과하게 되면 삽입하고자 하는 노드에 대한 포인터 할당이 되지 않습니다.
더 정확하게는 부모노드의 자식포인터에 새 노드를 가리키는 포인터를 넣어주지만
함수 실행이 끝난 뒤에 확인해보면 부모노드의 자식포인터는 여전히 null값을 지닙니다.

예를 들면 다음과 같은 트리를 입력하려고 하면
    A
↙   ↘
    B       C
↙      ↙ ↘
D      E       F
              ↙
            G

A~F까지는 부모 노드와 자식 노드간 연결이 잘 되지만, F노드에서 G노드로 향하는 포인터가 null을 갖게 됩니다.
그러나 디버깅해보면 treeArr배열에는 G노드가 분명히 입력되어있습니다.

다른 구조의 트리들로 여러 번 테스트해봐도 트리 높이 3을 마지막으로 그 이상의 노드들에 대해서는 자식 포인터가 할당이 되지 않습니다. 혹시 이유를 아는 분이 계시다면 답변 부탁드립니다.

문제가 복잡해서 최대한 자세히 설명하려고 노력하였으나 그래도 글이 장황하여 이해가 안되는 부분이 있다면 알려주세요. 고치겠습니다.

긴 글인데도 관심갖고 읽어 주셔서 감사합니다.

아래는 혹시 글이 이해가 안되실까봐 참고용으로 넣은 소스코드입니다.

void Insert(char parentData, char leftData, char rightData){
		TreeNode* leftChild = new TreeNode();
		TreeNode* rightChild = new TreeNode();

		if (!treeSize) {    //트리가 공백일 때 삽입 처리
			TreeNode* parent = new TreeNode();
			parent->data = parentData;
			treeArr[++treeSize] = *parent;
			
			if (leftData != '.') {
				leftChild->data = leftData;
				treeArr[++treeSize] = *leftChild;
				treeArr[treeSize - 1].leftChild = &(treeArr[treeSize]);
			}
			
			if (leftData != '.') {
				rightChild->data = rightData;
				treeArr[++treeSize] = *rightChild;
				treeArr[treeSize - 2].rightChild = &(treeArr[treeSize]);
			}
		}
		else {    //트리가 공백이 아닐 때 삽입 처리
			for (int i = 1; i <= treeSize; i++) {
				if ((treeArr[i]).data == parentData) {
					
					if (leftData != '.') {
						leftChild->data = leftData;
						treeArr[++treeSize] = *leftChild;
						(treeArr[i]).leftChild = leftChild;
					}

					if (rightData != '.') {
						rightChild->data = rightData;
						treeArr[++treeSize] = *rightChild;
						(treeArr[i]).rightChild = rightChild;
					}
					return;
				}
			}
		}
	}

doju 5년 전 0

16번째 줄에서 rightData가 아니라 leftData를 검사하고 있습니다.
오른쪽 자식만 있는 노드가 새로 추가될 경우 19번째 줄에서 treeArr[treeSize - 2]는 엉뚱한 노드를 가리키게 됩니다.
이 문제에는 부모 노드가 자식 노드보다 먼저 주어진다는 보장이 없습니다. 예제에서 각 줄의 순서가 뒤바뀌더라도 프로그램은 같은 답을 출력해야 합니다.

jh1one 5년 전 1

@doju

doju님 답변감사합니다. 제가 doju님 덕분에 제가 생각치 못했던 곳을 발견하게 되었네요. 아직 성공은 못했지만 doju님 답변 덕분에 실마리가 보이는 것 같습니다. 긴 질문 글인데도 관심갖고 답변 남겨 주셔서 다시 한 번 더 감사드립니다! ^^

jh1one 5년 전 1

@doju
doju님께서 답변해주신 1991번 문제 해결하였습니다.

doju님 댓글의 마지막 조건을 제가 잘못 이해하고 있어서 골머리를 앓고 있었는데 덕분에 문제를 제대로 이해하고 다시 구현할 수 있었습니다. 감사합니다.

#include<iostream>
using namespace std;
class Tree;

class TreeNode{
	friend class Tree;
private:
	char data;
	TreeNode *leftChild;
	TreeNode *rightChild;

public:
	TreeNode(char val = 0) : data(val)    {    data = val;    }
	void Visit() {    cout << data;    }
};

class Tree{
private:
	TreeNode* root;
	TreeNode* rootSet[26];
	int rootCount;
public :
	Tree() {    rootCount = 0;    }

	void CreateTree(char parentData, char leftData, char rightData) {
		TreeNode* parent = new TreeNode();
		TreeNode* leftChild = new TreeNode();
		TreeNode* rightChild = new TreeNode();

		parent->data = parentData;
		if (parent->data == 'A') root = parent;
		if (leftData != '.') {
			leftChild->data = leftData;
			parent->leftChild = leftChild;
		}

		if (rightData != '.') {
			rightChild->data = rightData;
			parent->rightChild = rightChild;
		}
		rootSet[rootCount++] = parent;
	}
    
	void UnionTree() {
		for (int i = 0; i < rootCount; i++) {
			TreeNode* parent = rootSet[i];
			bool leftFull = parent->leftChild ? false : true;
			bool rightFull = parent->rightChild ? false : true;
			for (int j = 0; j < rootCount; j++) {
				if (!leftFull && parent->leftChild && parent->leftChild->data == rootSet[j]->data) { 
					parent->leftChild = rootSet[j];
					leftFull = true;
				}
				if (!rightFull && parent->rightChild && parent->rightChild->data == rootSet[j]->data) {
					parent->rightChild = rootSet[j];
					rightFull = true;
				}
				if (leftFull&&rightFull) break;
			}
		}
	}
    
	void PreOrder()const { PreOrder(root);}

	void PreOrder(TreeNode* node)const {
		TreeNode* currNode = node;
		if (currNode) {
			currNode->Visit();
			PreOrder(currNode->leftChild);
			PreOrder(currNode->rightChild);
		}
	}

	void InOrder()const { InOrder(root); }

	void InOrder(TreeNode* node)const {
		TreeNode* currNode = node;
		if (currNode) {
			InOrder(currNode->leftChild);
			currNode->Visit();
			InOrder(currNode->rightChild);
		}
	}

	void PostOrder() { PostOrder(root); } const

	void PostOrder(TreeNode* node)const {
		TreeNode* currNode = node;
		if (currNode) {
			PostOrder(currNode->leftChild);
			PostOrder(currNode->rightChild); 
			currNode->Visit();
		}
	}
};

int main() {
	int n;
	cin >> n;
	Tree tree;

	for (int i = 0; i < n; i++) {
		char data, left, right;
		cin >> data >> left >> right;
		tree.CreateTree(data, left, right);
	}
    
	tree.UnionTree();
	tree.PreOrder();
	cout << '\n';
	tree.InOrder();
	cout << '\n';
	tree.PostOrder();
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

트리 구현 중 자식포인터 할당에 대해 질문드립니다.

jh1one 5년 전 0

doju 5년 전 0

jh1one 5년 전 1

jh1one 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말