これはアカンかったです。次節点の探索のところ、ややこしすぎませんか?
あっそういえばポインタの参照を久しぶりに使いました。(rootの入れ替えのところ)
#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; } } static Node* find(Node* node, int v) { while (node != nullptr && node->key != v) { if (node->key > v) { node = node->left; } else { node = node->right; } } return node; } static Node* getSuccessor(Node* x) { if (x->right) { x = x->right; while (x->left) { x = x->left; } return x; } Node* y = x->parent; while (y && x == y->right) { x = y; y = y->parent; } return y; } static void deleteNode(Node*& root, int v) { Node* z = find(root, v); Node* y; if (!z->left || !z->right) { y = z; } else { y = getSuccessor(z); } Node* x; if (y->left) { x = y->left; } else { x = y->right; } if (x) { x->parent = y->parent; } if (!y->parent) { root = x; } else if (y == y->parent->left) { y->parent->left = x; } else { y->parent->right = x; } if (y != z) { z->key = y->key; } delete y; } void preorderWalk(const Node* node) { if (!node) { 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) { 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 if (command[0] == 'f') { scanf("%d", &v); Node* found = find(TREE.root, v); cout << (found ? "yes" : "no") << endl; } else if (command[0] == 'd') { scanf("%d", &v); deleteNode(TREE.root, v); } else { inorderWalk(TREE.root); cout << endl; preorderWalk(TREE.root); cout << endl; } } return 0; }