Как удалить обьект из дерева с помощью списка?

Question

[Sneiksus]

Есть узел бинарного дерева

class Node{
    public int val;
    public Node left;
    public Node right;
}

при создании каждого нового узла он также добавляется в список

List<Node> l = new List<Node>();
Node n = new Node();
l.add(n);

и теперь мне нужно при удалении узла из списка с помощью removeAt(), чтобы удаленный узел также удалился из других узлов которые содержат ссылку на него в своих left right свойствах(Например чтобы после удаления там был null). Как это можно сделать на c#?

Comments

[Василий Банников]

Сохранить заранее этот элемент, пройтись циклом по всем элементам, и удалить в них.

[#]

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

- поддерживаю Роман по поводу свойства Parent
- но прежде чем самоудаляться из него, вам все таки надо определиться с дочерними поддеревьями. тут подход рассмотрен BasiC2k, но для больших деревьев, рекурсия может быть критически ресурсоемкой. есть подходы эмуляции хвостовой рекурсии циклом* ))) можно и по вашему списку, хотя и его наличие для больших деревьев, скорее источник ошибок )))
- если по характеру задачи дочерние ветви удалять не следует, у вас проблема.. если одна подветвь, то ее вероятно можно пристегнуть вместо удаляемого элемента. если две... то подход к задаче надо пересмотреть в принципе* )))

удачи ))

ps * - это намек что могу обсудить подробнее. в профиле есть телеграм )))

Answer 1

[Роман]

Заведите ещё свойство Parent на родительский узел. Тогда при удалении, можно обратиться к родительской и удалить узел из ее свойств, чтобы не обходить дерево.

Answer 2

[Sergey В.]

Нужно использовать рекурсивную функцию.
На вход подаётся нода, далее - идёт проверка, если у неё есть дочерние ноды, то идёт новый вызов этой функции и т.д.
К конце кода, когда обработаны (удалены) все дочерние ноды - идёт удаление поданной на вход ноды.