結果

問題 No.566 だいたい完全二分木
ユーザー jokin_tokeijokin_tokei
提出日時 2017-09-10 14:06:54
言語 C
(gcc 12.3.0)
結果
MLE  
実行時間 -
コード長 3,350 bytes
コンパイル時間 1,203 ms
コンパイル使用メモリ 33,152 KB
実行使用メモリ 817,024 KB
最終ジャッジ日時 2024-11-07 12:35:57
合計ジャッジ時間 4,297 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 MLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define THOUSAND 1000
#define SUCCESS 1
#define FAILURE 0

typedef struct node {
	int data;
	struct node* left;
	struct node* right;
} NODE;

NODE* make_tree(NODE* root, int k, int node_num, int max_height);
void show_tree(NODE *root);
int left_judgement(NODE *root, int k);
NODE* insert_data(NODE* root, int data);
NODE* new(int data);
//void delete_left(NODE *root, int last_data);

void roughly_binary_tree() {
	int k = 0, node_num = 0, min_height = 0, max_height = 0;
	NODE *root = NULL;

	scanf("%d", &k);

	node_num = (int) pow(2, k) - 1;
	min_height = k;
	max_height = 3 * k;

	make_tree(root, k, node_num, max_height);
}

NODE* make_tree(NODE* root, int k, int node_num, int max_height) {
	int i, j;
	NODE *p = NULL;
	p = root;

	static int stopper=0;
	//	printf("%d", node_num);

	if (k < 4) {
		for (i = 0; i < node_num; i++) {
			p = insert_data(p, i + 1);
		}
		show_tree(p);
		exit(0);
	}

	for (i = 0; i < max_height + 1; i++) {
		p = insert_data(p, node_num - (max_height + 1) + i + 1);
	}

	for (j = node_num - (max_height +1) ; j > 0; j--) {
		insert_data(p, j);
	}

	if (left_judgement(p, k)) {
		show_tree(p);
		return p;
	} else {
		p->left = make_tree(NULL, k, node_num - (max_height + 1),
				max_height - 1);
	}

	return NULL;
}

void show_tree(NODE *root) {
	NODE *p;

	p = root;

	if (p == NULL) {
		return;
	}

	printf("%d ", p->data);
	show_tree(p->left);
	show_tree(p->right);
}

int left_judgement(NODE *root, int k) {
	static int height = 1;

	if (root == NULL) {
		if (height <= 3 * k) {
			return SUCCESS;
		} else {
			return FAILURE;
		}
	}

	height++;
	return left_judgement(root->left, k);
}

NODE* insert_data(NODE* root, int data) {
	NODE *p;

	p = root;

	if (p == NULL) {
		return new(data);
	}

	if (data <= p->data) {   // equal is left
		p->left = insert_data(p->left, data);
	} else if (p->data < data) {
		p->right = insert_data(p->right, data);
	}

	return root;
}

NODE* new(int data) {
	NODE *p;

	p = malloc(sizeof(NODE));

	if (p == NULL) {
		printf("memory error\n");
		exit(0);
	}
	p->data = data;
	p->left = p->right = NULL;

	return p;
}

NODE* search_data(NODE *root, int s_data) {
	NODE *p = NULL;

	p = root;

	if (p->data == s_data) {
		return p;
	} else if (s_data <= p->data) {
		return search_data(p->left, s_data);
	} else {
		return search_data(p->right, s_data);
	}

}

//void delete_left(NODE *root, int last_data) {
//	NODE *target = NULL;
//	NODE *p = NULL;
//
//	target = search_data(root, last_data);
//
//	for(p = root; ;){
//		if(p->left == target){
//			p->left = NULL;
//		}
//	}
//
//
//}

void order() {
	int nama_height = 0, num = 0;
	int other_height[THOUSAND] = { };
	int i, j;

	int rank = 1;

	scanf("%d %d\n", &nama_height, &num);

	for (i = 0; i < num; i++) {
		scanf("%d\n", &other_height[i]);
	}

	for (j = 0; j < num - 1; j++) {
		if (nama_height < other_height[j]) {
			rank++;
		}
	}

	printf("%d", rank);

	switch (rank % 10) {
	case 1:
		printf("st\n");
		break;
	case 2:
		printf("nd\n");
		break;
	case 3:
		printf("rd\n");
		break;
	default:
		printf("th\n");
		break;
	}

}

int main(void) {
//	NODE *root = NULL;
//	int data[6] = { 2, 1, 5, 4, 7,3 };
//	int i = 0;
//
//	for (i = 0; i < 6; i++) {
//		root = insert_data(root, data[i]);
//	}
//	show_tree(root);
	roughly_binary_tree();

	return 0;
}
0