Удаление элемента из дерева, С++

Написал алгоритм удаления элемента из бинарного дерева поиска. Алгоритм не рекурсивный. Так как это академическая задачка, требуют рекурсивный. Рекурсивный метод у меня не выходит. Код выкладывать смысла нет. Если у кого есть простой и понятный рекурсивный алгоритм удаления элемента из бинарного дерева поиска, буду благодарен.

Ответ

Если взять такое определение бинарного дерева. class BinaryTreeNode { public: BinaryTreeNode() : leftChild(NULL), rightChild(NULL), parent(NULL), value(-1) {} BinaryTreeNode(int val) : leftChild(NULL), rightChild(NULL), parent(NULL), value(val) {} public: static int getDepth(BinaryTreeNode * node) { int left = 0, right = 0; left = getDepth(node->leftChild); return 0; } public: BinaryTreeNode * leftChild; BinaryTreeNode * rightChild; BinaryTreeNode * parent; int value; }; То алгоритм может выглядеть так: void DeleteNodeFromBinary(BinaryTreeNode * node, int value) { if (node == NULL) return;
if (value < node->value) return DeleteNodeFromBinary(node->leftChild, value); else if(value > node->value) return DeleteNodeFromBinary(node->rightChild, value); else { if(node->leftChild == NULL && node->rightChild == NULL) { if (node->parent->leftChild == node) node->parent->leftChild = NULL; else node->parent->rightChild = NULL; delete node; } else { BinaryTreeNode * newnode = NULL; if(node->leftChild != NULL) { newnode = Rightmost(node->leftChild); } else newnode = Leftmost(node->rightChild);
if (node->parent->leftChild == node) node->parent->leftChild = newnode; else node->parent->rightChild = newnode;
newnode->parent = node->parent; newnode->rightChild = node->rightChild; newnode->leftChild = node->leftChild;
delete node; } } } BinaryTreeNode * Leftmost(BinaryTreeNode * node) { if (node == NULL) return NULL; if (node->leftChild != NULL) { return Leftmost(node->leftChild); } return node; } BinaryTreeNode * Rightmost(BinaryTreeNode * node) { if (node == NULL) return NULL; if (node->rightChild != NULL) { return Rightmost(node->rightChild); } return node; }