Как правильно освобождать память при удалении узлов в бинарном дереве поиска?

Question

[tj57]

Есть реализация класса бинарного дерева, в котором присутствует функция для удаления узлов дерева.
Как правильно освобождать память в различных случаях ?

TreeNode<Node>* Tree<Node>::delete_node(TreeNode<Node> *z)
{
	TreeNode<Node>* y;
	TreeNode<Node>* x;
	if (z->left == 0 || z->right == 0)/* в этой и следующих двух строках ищем вершину y, которую мы потом вырежем из дерева.
									  Это либо z, либо следующий за z */
		y = z;
	
	else
		y = find_succsessor(z->get_data());
	if (y->left != 0) /* x - указатель на существующего ребенка y или 0 если таковых нет */
		x = y->left;
	else
		x = y->right;
	if (x != 0)
		x->parent = y->parent;
	if (y->parent == 0)
		root = x;
	else
	{
		if (y == (y->parent)->left)
			(y->parent)->left = x;
		else
			(y->parent)->right = x;
	}
	if (y != z)
		z->data = y->get_data();
	return y;
}

Answer 1

[devalone]

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

Comments

[tj57]

Не совсем понял. Можно поподробнее ?

[devalone]

tj57: что-то такое:

class BinaryTree {
public:
    struct Node {
        int value;
        Node* left = nullptr;
        Node* right = nullptr;
    };
    Node* root = nullptr;

    void removeNode(Node* node)
    {
        std::queue<Node*> removeQueue;

        while (node) {
            if (node->left)
                removeQueue.push(node->left);
            if (node->right)
                removeQueue.push(node->right);
            delete node;
            node = nullptr;

            if (!removeQueue.empty()) {
                node = removeQueue.front();
                removeQueue.pop();
            }
        }
    }

    void removeValue(int value)
    {
        Node* node = findNodeByValue(value);
        if (node)
            removeNode(node);
    }
    Node* findNodeByValue(int value)
    {
        Node* currentNode = root;
        while (currentNode) {
            if (currentNode->value == value)
                break;
            else if (value > currentNode->value)
                currentNode = currentNode->right;
            else if (value < currentNode->value)
                currentNode = currentNode->left;
        }
        return currentNode;
    }
};

Код не проверял, поэтому может где-то и ошибся, но суть, думаю, понятна.