Дерево двоичного поиска PYTHON - Рекурсивное удаление

Question

Я работаю над двоичным деревом поиска, и мы должны реализовать метод remove с помощью рекурсии. Вот код, который нам дал.

def remove (self, x): 
    def recurse (p): 
     # Modify this method. 
     if p==None: 
      return p 
     elif x<p.data: 
      return p 
     elif x>p.data: 
      return p 
     elif p.left==None and p.right==None: # case (1) 
      return p 
     elif p.right==None:    # case (2) 
      return p 
     elif p.left==None:    # case (3) 
      return p 
     else:     # case (4) 
      return p 
    self.root = recurse (self.root) 

Очевидно, что для каждого условного выражения должно быть больше, чем просто возврат p. И я уверен, что первый, если и два elifs используются, чтобы «найти» узел, содержащий x. Однако я не уверен, как реализовать четыре случая. Любой вход был бы оценен.

Кроме того, конечной целью является использование этого метода для итерации через BST и удаления каждого узла.

Answer 1

Ну, ваш первый шаг - найти X, помните, что вы делаете это путем рекурсии, поэтому вам следует отменить функцию удаления на дочернем дереве, в котором она находится. (слева, если x < p.data, если выше ... только если они существуют). Затем вам нужно беспокоиться, что делать, если вы найдете x (x = p.data).

Я бы рекомендовал рисовать дерево и думать как алгоритм. :)

Помните о собственности BST! Дерево обязательно изменит его структуру, чтобы сохранить свойство, поэтому .. кто является новым отцом одиноких детей? советы:

Возможно, родной брат?

.

помню BST charasteristic

.

рекурсии !!!)

Answer 2

pseudo_code method_recurse требует аргумент: this_node

1. если this_node значение Нет, то не возвращать Ничего не найдено
2. если this_node является target, то возвращайте this_node
3. , если this_node меньше_than, а затем возвратите вызов self с this_node.right
4. , если this_node больше_than target, а затем возвратите вызов self с this_node.left