Как удалить узел в Ternary Tree?

Question

Я работаю над реализацией Java-программы по вставке и удалению узла в троичном дереве.

Я могу внедрить вставку без каких-либо проблем, но я сталкиваюсь с некоторыми затруднениями при осуществлении операции удаления.

Итак, мой вопрос:

Как удалить узел из троичного дерева, если у него есть один или несколько дочерних узлов?

Было бы хорошо, если бы вы могли поделиться какой-либо логикой или псевдокодом для реализации функции "удаления".

Answer 1

Я нашел решение.

---

предполагать n это узел, который мы хотим удалить, l это его левый ребенок, r это правильный ребенок и m это его средний ребенок.

• Если n является корневым узлом, а затем сделать nnull,

• Если n не является корневым узлом, проверьте m не null, Если это так, просто рекурсивно вызовите текущую процедуру m, поскольку m Матчи n по значению: мы удалим последний соответствующий узел!

• Если m является null, тогда мы имеем следующие возможные случаи:

  • Если оба l а также r являются null, а затем сделать l, r а также m значения в родительском узле n быть null,

  • Если только один узел, скажем x, (или l или же r) нет null затем заменить x ненулевое значение с n и удалите x,

  • Если оба l а также r не null затем найдите узел z с максимальным значением в левом поддереве n и заменить z ценность с с n и удалить узел z,