問題に書いてあった解説どおりの実装です。delete を呼んでないのが気持ち悪いですが、まあ良いでしょう。良くないか。
#include <iostream> #include <cstdio> #include <memory> using namespace std; struct Node { int key; Node* parent; Node* left; Node* right; Node(int key = -1) : key(key), parent(nullptr), left(nullptr), right(nullptr) {}; }; struct Tree { Node* root; Tree() : root(nullptr) {}; }; static void insert(Tree& tree, int v) { Node* z = new Node(v); Node* x(tree.root); Node* y(nullptr); while (x != nullptr) { y = x; if (z->key < x->key) { x = x->left; } else { x = x->right; } } z->parent = y; if (y == nullptr) { tree.root = z; } else if (z->key < y->key) { y->left = z; } else { y->right = z; } } void preorderWalk(const Node* node) { if (node->key == -1) { return; } cout << " " << node->key; if (node->left != nullptr) { preorderWalk(node->left); } if (node->right != nullptr) { preorderWalk(node->right); } } void inorderWalk(const Node* node) { if (node->key == -1) { return; } if (node->left != nullptr) { inorderWalk(node->left); } cout << " " << node->key; if (node->right != nullptr) { inorderWalk(node->right); } } static Tree TREE; int main() { int n; cin >> n; string command; int v; for (int i = 0; i < n; i++) { cin >> command; if (command[0] == 'i') { scanf("%d", &v); insert(TREE, v); } else { inorderWalk(TREE.root); cout << endl; preorderWalk(TREE.root); cout << endl; } } return 0; }