応用情報技術者試験のプログラミングの問題を実装（令和5年秋）

最近暇つぶしに応用情報技術者試験の問題を解いています。

少しでも理解を深めるため、応用情報技術者試験のプログラミング分野の問題をc/c++で実装しました。
令和5年秋の問題となります。
少しでも試験問題の理解の助けになればと思い共有します。

過去問は以下のサイト様より確認しています。
https://www.ap-siken.com/apkakomon_pm.php

注意点

・開発環境はvisual studio 2022 です
・cとc++混じってます
・newで動的確保していますが、deleteとか一切していないです。

コード

main.cpp

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



typedef struct Node
{
	int key;
	Node* left;
	Node* right;
}Node;

Node* NewNode(int k)
{
	Node* node = new Node();
	node->key = k;
	return node;
}
Node* search(Node* t, int k)
{
	if(t == NULL)
	{
		return NULL;
	}
	else if(t->key == k)
	{
		return t;
	}
	else if(t->key > k)
	{
		return search(t->left, k);
	}
	else // t->key が k より小さい場合
	{
		return search(t->right, k);
	}
}

Node* insert(Node* t, int k)
{
	if(t == NULL)
	{
		t = NewNode(k);
	}
	else if(t->key > k)
	{
		t->left = insert(t->left, k);
	}
	else if(t->key < k)
	{
		t->right = insert(t->right, k);
	}
	return t;
}

/* 試験問題外 */
int height(Node* t)
{
	if (t == NULL) 
	{
		return 0;
	}

	int leftHeight = height(t->left);
	int rightHeight = height(t->right);
	return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);

}
Node* rotateR(Node* t)
{
	Node* a = t->left;
	Node* b = a->right;
	a->right = t;
	t->left = b;
	return a;
}

Node* rotateL(Node* t)
{
	Node* a = t->right;
	Node* b = a->left;
	a->left = t;
	t->right = b;
	return a;
}

Node* balance(Node* t)
{
	int h1 = height(t->left) - height(t->right);
	if(h1 == 2)/**ウ***/
	{
		int h2 = height(t->left->right) - height(t->left->left);/**エ**/
		if(h2 > 0)
		{
			t->left = rotateL(t->left);
		}
		t = rotateR(t);
	}
	else if(h1 == -2)/**オ***/
	{
		int h3 = height(t->right->left) - height(t->right->right);/***カ***/
		if(h3 > 0)
		{
			t->right = rotateR(t->right);
		}
		t = rotateL(t);
	}
	return t;
}

Node* insertB(Node* t, int k)
{
	if(t == NULL)
	{
		t = NewNode(k);
	}
	else if(t->key > k)
	{
		t->left = insertB(t->left, k);
	}
	else if(t->key < k)
	{
		t->right = insertB(t->right, k);
	}
	t = balance(t);
	return t;
}


/*試験問題外*/
int space = 0;
void printKeys(Node* node)
{
	if (node == NULL)
	{
		return;
	}

	for (int i = 0; i < space; i++)
	{
		printf("  ");
	}

	// キー値を出力
	printf("%d\n", node->key);

	space++;

	// 左側の子ノードを出力
	printKeys(node->left);

	// 右側の子ノードを出力
	printKeys(node->right);

	space--;

}


int main(void)
{
	Node* node = NULL;

	// 図1
	node = insert(node, 6);
	node = insert(node, 3);	
	node = insert(node, 9);
	node = insert(node, 1);
	node = insert(node, 5);

	// 設問2 (2)
	node = insertB(insertB(node,4),8);

	while(true)
	{
		system("cls");

		space = 0;
		printKeys(node);
		
		printf("\n\n");
		
		int input1, input2;

		scanf_s("%d %d", &input1, &input2);
		if(input1 < 1)
		{
			break;
		}

		if(input1 == 1)
		{
			node = insert(node, input2);
		}

		if(input1 == 2)
		{
			node = insertB(node, input2);
		}
	}

	return 0;
}

説明

コメントの //図1 の箇所で　試験問題の図1を再現。
// 説明2(2)で同様の試験問題の箇所を再現しています。

出力の処理はAIに聞きつつ雑に変更しているため、ゴミコードです。
試験には含まれていないので無視してください。

以下のように出力されます。
非常に分かりづらいです（ツリー形式で出力したかった…）
// 以降はコメントです。実際には出力されません

5　　　　// 一番上のノード
  3　　　　//左の子のノード
    1       // 左の子ノード
    4       // 右の子ノード
  8　　　// 左の子ノード
    6　   // 左の子ノード
    9     // 右の子ノード

また、出力された後以下の形式でノードを追加することができます。
insert関数で10を挿入したい場合
1 10
insertB関数で20を挿入したい場合
2 10
など…
0 0 等の入力で終了します。

以上です。