Как найти родителя заданного элемента в бинарном дереве?

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

Для решения этой задачи можно воспользоваться рекурсивным или итеративным алгоритмом.

Рекурсивный алгоритм:

1. Проверить, если текущий узел является пустым или равным заданному элементу, вернуть текущий узел.
2. Если значение заданного элемента меньше значения текущего узла, рекурсивно вызвать функцию для левого поддерева.
3. Если значение заданного элемента больше значения текущего узла, рекурсивно вызвать функцию для правого поддерева.

Пример реализации рекурсивной функции на языке C:

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Node* findParent(struct Node* root, int element) {
    if (root == NULL || root->data == element) {
        return root;
    }
    
    if (element < root->data) {
        return findParent(root->left, element);
    } else {
        return findParent(root->right, element);
    }
}

Итеративный алгоритм:

1. Присвоить указатель на корень дерева текущему узлу.
2. Пока текущий узел не равен NULL:
3. Если значение левого потомка текущего узла равно заданному элементу, вернуть указатель на текущий узел.
4. Если значение правого потомка текущего узла равно заданному элементу, вернуть указатель на текущий узел.
5. Если значение заданного элемента меньше значения текущего узла, переместиться в левый потомок.
6. Если значение заданного элемента больше значения текущего узла, переместиться в правый потомок.
7. Если ни один из условий не выполняется, присвоить текущему узлу значение его левого потомка.

Пример реализации итеративной функции на языке C:

struct Node* findParent(struct Node* root, int element) {
    struct Node* current = root;
    
    while (current != NULL) {
        if (current->left != NULL && current->left->data == element) {
            return current;
        }
        
        if (current->right != NULL && current->right->data == element) {
            return current;
        }
        
        if (element < current->data) {
            current = current->left;
        } else if (element > current->data) {
            current = current->right;
        } else {
            break;
        }
    }
    
    return NULL;
}

В обоих случаях, если элемент не найден в дереве, будет возвращено значение NULL.