Блог

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

Эта функция удаляет определенный узел:

 def deleteNode(self,val):
    if self.data:
        if self.data > val:
            self.left.deleteNode(val)
        elif self.data < val:
            self.right.deleteNode(val)
        else:
            if self.left is None:
                self.data = self.right
                return True
            elif self.right is None:
                self.data = self.left
                return True
            else:
                dltNode = self
                dltNode.data = self.data
                largest = self.left.findMax()
                dltNode.data = largest
                dltNode.left.deleteNode(largest)
                return True
 

Эта функция находит минимальный узел:

 def findMin(self):
    if self.data:
        if self.left is None:
            return self.data
        else:
            return self.left.findMin()
 

И это для максимального узла:

 def findMax(self):
    if self.data:
        if self.right is None:
            return self.data
        else:
            return self.right.findMax()
 

Функции findMin и findMax прекрасно работают без удаления какого-либо узла.
Если я когда-нибудь позвоню, то после удаления минимального и максимального узла они не вернут ни одного, независимо от того, должны ли они возвращать только целочисленные данные узла. Вот скриншот моего вывода:

Он должен напечатать 34 вместо Ни одного.

Вот мой полный код

Есть несколько проблем в deleteNode

• if self.data не должно быть там: это означало бы, что вы не можете удалить узел со значением 0 из дерева. Аналогичная проблема существует и в других методах ( findMin , findMax , insert , …).
• self.left.deleteNode(val) выполняется без предварительной проверки того, что self.left нет None . То же самое верно и для self.right.deleteNode(val)
• self.data = self.right присваивает ссылку на узел data атрибуту (который должен быть числом).
• Функция иногда ничего не возвращает ( None ) или True . Из-за рекурсивной природы исходный вызывающий метод получит None . Это непоследовательно.
• Функция не может справиться с удалением корневого узла, так как вызывающий будет продолжать использовать ссылку на корневой узел ( t или t2 в вашем примере кода).

Чтобы решить эти проблемы, вам следует либо создать отдельный Tree класс, либо согласиться с тем, что deleteNode возвращает корневой узел дерева, который может быть корнем, отличным от корня, на котором был сделан вызов (когда корневой узел был удален), или даже None когда это был последний узел дерева.

Вот как это будет выглядеть:

     def deleteNode(self,val):
        if self.data > val:
            if self.left:
                self.left = self.left.deleteNode(val)
        elif self.data < val:
            if self.right:
                self.right = self.right.deleteNode(val)
        else:
            if self.left is None:
                return self.right
            elif self.right is None:
                return self.left
            else:
                largest = self.left.findMax()
                self.data = largest
                self.left = self.left.deleteNode(largest)
        return self
 

Чтобы сделать это правильно, вам нужно будет использовать возвращаемое значение из этого метода, например:

 t1 = t1.deleteNode(34)
 

NB: В некоторых методах вы проверяете, есть ли self.data is None . Я понимаю, что это какое-то особое условие для указания на то, что корневой узел на самом деле не является узлом и должен рассматриваться как пустое дерево, но это не очень хороший шаблон. Вместо этого пустое дерево должно быть просто None , или вы должны определить другой Tree класс , у которого есть root атрибут, который может быть None .