[정올 1716] 이진트리 탐색

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=989&sca=99&sfl=wr_hit&stx=1716 

JUNGOL

#include <stdio.h>

struct Node {
	Node* pRoot;
	Node* pLeft;
	Node* pRight;
	int my;
	int Left;
	int Right;
	Node(int n) : pRoot(nullptr), pLeft(nullptr), pRight(nullptr), my(n), Left(0), Right(0) {}
};

Node* pROOT;

void Input() {
	int n;
	Node* pTmp, * pCur;
	do {
		scanf(" %d", &n);
		if (n != -1) {
			pTmp = new Node(n);
			if (pROOT == nullptr) { pROOT = pTmp; pCur = pROOT; }
			else if (pCur->Left == 0) { pCur->Left = 1; pCur->pLeft = pTmp; pTmp->pRoot = pCur; pCur = pTmp; }
			else if (pCur->Right == 0) { pCur->Right = 1; pCur->pRight = pTmp; pTmp->pRoot = pCur; pCur = pTmp; }
		}
		else {
			if (pCur->Left == 0) pCur->Left = -1;
			else if (pCur->Right == 0) pCur->Right = -1;

			while (pCur->Left != 0 && pCur->Right != 0 && pCur != pROOT) pCur = pCur->pRoot;
		}
	} while (getc(stdin) == ' ');
}
Node* Get() {
	Node* pN = pROOT;
	while (1) {
		if (pN->pLeft) pN = pN->pLeft;
		else if (pN->pRight) pN = pN->pRight;
		else break;
	}
	return (pN == pROOT) ? (nullptr) : (pN);
}

int main(void) {
	Input();
	
	while (1) {
		Node* pN = Get();
		if (pN == nullptr)	{
			printf("%d ", pROOT->my);
			break;
		}
		else { 
			printf("%d ", pN->my);
			if (pN->pRoot->pLeft == pN) {
				pN->pRoot->pLeft = nullptr;
				delete pN;
			}
			else if (pN->pRoot->pRight == pN) {
				pN->pRoot->pRight = nullptr;
				delete pN;
			}
		}
	}

	return 0;
}