글 읽기 - 이진트리로 찾기

dgsoul 6년 전 0

트리를 구성하여 이진탐색트리로 값을 넣은 다음

루트의 왼쪽 Node개수, 오른쪽 Node개수로 중앙값을 바꿔주도록 코드를 짰습니다

6%정도에서 틀렸습니다가 나오는데

틀린 케이스를 찾기가 힘드네요.

어느 부분이 잘못된걸까요

#include<iostream>
#include<vector>
#include<stdio.h>
using namespace std;

class Node {
public:
	int data;
	Node* left;
	Node* right;
	Node* parent;
	Node() {
		left = right = parent = NULL;
	}
};

class myTree {
public:
	Node* root;
	int leftCount;
	int rightCount;
	myTree() {
		root = NULL;
		leftCount = 0;
		rightCount = 0;
	}
	bool isExternal(Node* x) {
		return x->left == NULL && x->right == NULL;
	}
	Node* findMax(Node* start) {
		Node* ptr = start;
		while (1) {
			if (ptr->right == NULL) return ptr;
			else ptr = ptr->right;
		}
	}
	Node* findMin(Node* start) {
		Node* ptr = start;
		while (1) {
			if (ptr->left == NULL) return ptr;
			else ptr = ptr->left;
		}
	}
	void push(int d) {
		if (root == NULL) {
			root = new Node;
			root->data = d;
			return;
		}
		Node* ptr = root;
		while (1) {
			if (d >= ptr->data) {
				if (ptr == root) rightCount++;
				if (ptr->right == NULL) {
					ptr->right = new Node;
					ptr->right->data = d;
					ptr->right->parent = ptr;
					break;
				}
				else ptr = ptr->right;
			}
			else {
				if (ptr == root) leftCount++;
				if (ptr->left == NULL) {
					ptr->left = new Node;
					ptr->left->data = d;
					ptr->left->parent = ptr;
					break;
				}
				else ptr = ptr->left;
			}
		}
		balance();
	}
	void balance() {
		if (rightCount == leftCount + 2) {
			Node* temp = findMin(root->right);
			if (temp == root->right) {
				temp->left = root;
				temp->parent = NULL;
				root->parent = temp;
				root->right = NULL;
				root = temp;
				rightCount--;
				leftCount++;
				return;
			}
			Node* newRoot = new Node;
			newRoot->data = temp->data;
			newRoot->left = root;
			newRoot->right = root->right;
			root->parent = newRoot;
			root->right->parent = newRoot;
			root->right = NULL;
			temp->parent->left = NULL;
			root = newRoot;
			delete temp;
			rightCount--;
			leftCount++;
		}
		else if (leftCount == rightCount + 1) {
			Node* temp = findMax(root->left);
			if (temp == root->left) {
				temp->right = root;
				temp->parent = NULL;
				root->parent = temp;
				root->left = NULL;
				root = temp;
				rightCount++;
				leftCount--;
				return;
			}
			Node* newRoot = new Node;
			newRoot->data = temp->data;
			newRoot->right = root;
			newRoot->left = root->left;
			root->parent = newRoot;
			root->left->parent = newRoot;
			root->left = NULL;
			temp->parent->right = NULL;
			root = newRoot;
			delete temp;
			rightCount++;
			leftCount--;
		}
		else return;
	}
};

int main() {
	myTree test;
	vector<int> result;
	int N, x;
	scanf("%d",&N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &x);
		test.push(x);
		result.push_back(test.root->data);
	}
	for (int i = 0; i < N; i++) {
		printf("%d\n",result[i]);
	}
}

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

문제

문제

출처

ICPC

이진트리로 찾기

dgsoul 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말