Как удалить узел в бинарном дереве поиска с помощью Python - PullRequest
Новая
       71

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

0 голосов
/ 06 июня 2018 
def delete_a_node(self,data):
    if self.root==None:
        print("Empty BST")
    else:
        parent=None
        node=self.root
        replace_node=None
        while(node!=None and node.data!=data):
            parent=node
            if data>=node.data:
                node=node.rightchild
                flag=1
            else:
                node=node.leftchild
                flag=0

        if node is None:
            print("node not in BST.")
        else:
            if (node.leftchild==None) and (node.rightchild==None):
                if (flag):
                    parent.rightchild=None
                else:
                    parent.leftchild=None
                del node
            elif (node.leftchild==None) or (node.rightchild==None):
                if node.leftchild==None:
                    if(flag):
                        parent.rightchild=node.rightchild
                    else:
                        parent.leftchild=node.rightchild
                else  :
                    if(flag):
                        parent.rightchild==node.leftchild
                    else:
                        parent.leftchild=node.leftchild

                del node


            else:
                 replace_node,parent=self.minimum_element(node.rightchild)
                 node=replace_node
                 if parent==None:
                     node.rightchild=None
                 else:
                     parent.leftchild=None
                  del replace_node





def minimum_element(self,node):
    if self.root==None:
        print("Empty BST")
    else:
        parent=None
        while(node.leftchild!=None):
            parent=node
            node=node.leftchild
        return (node,parent)

Здравствуйте, ребята, я пытался удалить узел из двоичного дерева поиска.Я пытался узнать это у https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/., поскольку они используют рекурсию в своем коде.Я не смог понять это хорошо.

Итак, я попытался создать этот код.Здесь я инициализирую root в методе init , а остальные два метода перед вами. 

  def __init__(self):
    self.root=None

Переменная FLAG: я использовал ее, чтобы просто найти связь между родительским узлом и узлом данных(мы хотим удалить).

Как мы знаем, есть три случая

  1. Когда у узла, который мы хотим удалить, нет дочернего элемента (он работает нормально)
  2. Когда у узла, который мы хотим удалить, есть один дочерний элемент (он работает нормально)
  3. Когда у узла, который мы хотим удалить, есть оба дочерних элемента ( ЗДЕСЬ ПРОБЛЕМА )

Пожалуйста, кто-нибудь может мне помочь с этим кодом?

Не могли бы вы показать мне,

  1. правильный метод удаления узла из BST
  2. долженЯ использую del node в Python или нет, потому что я только что прочитал, что нет необходимости освобождать пространство в Python.
  3. Не слишком ли моя сложность по сравнению с https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/ code?

Вывод:

bst.inorder () 25--15--10--4--12--22--18--24--50--35--31--44--70--66--55--90--105--120 -

bst.delete_a_node (15)

bst.inorder () 25--15--10--4--12--22--18--24--50--35--31--44--70--66--55--90--105--120 -

Заранее спасибо:)

1 Ответ

0 голосов
/ 07 июня 2018 
    def delete_a_node(self,data):
    if self.root==None:
        print("Empty BST")
    else:
        parent=None
        node=self.root
        replace_node=None
        while(node!=None and node.data!=data):
            parent=node
            if data>=node.data:
                node=node.rightchild
                flag=1
            else:
                node=node.leftchild
                flag=0


        if node is None:
            print("node not in BST.")

        else:


            if (node.leftchild==None) and (node.rightchild==None):
                if (flag):
                    parent.rightchild=None
                else:
                    parent.leftchild=None
                del node

            elif (node.leftchild==None) or (node.rightchild==None):
                if node.leftchild==None:
                    if(flag):
                        parent.rightchild=node.rightchild
                    else:
                        parent.leftchild=node.rightchild
                else  :
                    if(flag):
                        parent.rightchild==node.leftchild
                    else:
                        parent.leftchild=node.leftchild

                del node


            else:
                 replace_node=self.minimum_element(node.rightchild)
                 temp=replace_node.data
                 self.delete_a_node(replace_node.data)
                 node.data=temp

def minimum_element(self,node):
    if self.root==None:
        print("Empty BST")
    else:
        while(node.leftchild!=None):
            node=node.leftchild
        print(node.data)
        return (node)

так, с помощью в разделе комментариев.Я выполнил код.Большое спасибо, ребята.

Должен ли я использовать Del или нет Является ли использование Del плохо?

сложность вполне нормально.

...