löschen binäre Suche Baum

Question

Ich versuche, den Knoten der binären Suche Baum zu löschen Das Ergebnis, das ich bekommen habe, wenn ich ausdrucken ist eigentlich keine Diese Löschung, tatsächlich kann alles Schlüssel aus dem Binärbaum selbst löschen.

Ich bin neu in Binary Search Tree. Kann mir jemand mit meinem Code helfen? Sie helfen, wird applieciated.

Dank

def deleteMin(self): 
    self.root = self.deleteMin2(self.root) 

def deleteMin2(self, node): 
    if node.left is None: 
     return node.right 
    node.left = self.deleteMin2(node.left) 
    node.count = 1 + self.size2(node.left) + self.size2(node.right) 
    return node 

def delete(self,key): 
    self.root = self.delete2(self.root,key) 

def delete2(self,node,key): 
    if node is None: 
     return None 
    if key < node.key: 
     node.left = self.delete2(node.left,key) 
    elif(key > node.key): 
     node.right = self.delete2(node.right,key) 
    else: 
     if node.right is None: 
      return node.left 
     if node.left is None: 
      return node.right 
     t = node 
     node = self.min(t.right) 
     node.right = self.deleteMin2(t.right) 
     node.left = t.left 
    node.count = self.size2(node.left) + self.size2(node.right) + 1 
    return node 

Voll-Code

import os 
import pygraphviz as pgv 
from collections import deque 


class BST: 
    root=None 

    def put(self, key, val): 
     self.root = self.put2(self.root, key, val) 

    def put2(self, node, key, val): 
     if node is None: 
      #key is not in tree, create node and return node to parent 
      return Node(key, val) 
     if key < node.key: 
      # key is in left subtree 
      node.left = self.put2(node.left, key, val) 
     elif key > node.key: 
      # key is in right subtree 
      node.right = self.put2(node.right, key, val) 
     else: 
      node.val = val 
     node.count = 1 + self.size2(node.left) + self.size2(node.right) 
     return node 




    # draw the graph 
    def drawTree(self, filename): 
     # create an empty undirected graph 
     G=pgv.AGraph('graph myGraph {}') 

     # create queue for breadth first search 
     q = deque([self.root]) 
     # breadth first search traversal of the tree 
     while len(q) <> 0: 
      node = q.popleft() 
      G.add_node(node, label=node.key+":"+str(node.val)) 
      if node.left is not None: 
       # draw the left node and edge 
       G.add_node(node.left, label=node.left.key+":"+str(node.left.val)) 
       G.add_edge(node, node.left) 
       q.append(node.left) 
      if node.right is not None: 
       # draw the right node and edge 
       G.add_node(node.right, label=node.right.key+":"+str(node.right.val)) 
       G.add_edge(node, node.right) 
       q.append(node.right) 

     # render graph into PNG file 
     G.draw(filename,prog='dot') 
     os.startfile(filename) 

    def createTree(self): 
     #root 
     self.put("F",6) 
     self.put("D",4) 
     self.put("C",3) 
     self.put("B",2) 
     self.put("A",1) 
     self.put("E",5) 
     self.put("I",9) 
     self.put("G",7) 
     self.put("H",8) 
     self.put("J",10) 

    def get(self,key): 
     temp = self.root 
     while temp is not None: 
      #if what you are searching for is the root 
      if temp.key == key: 
       return temp.val 
      #if it's not the root 
      #check to see if what you're searching for is less than the root key 
      #if so, search left 
      elif temp.key > key: 
       temp = temp.left 
      #else search right 
      else: 
       temp = temp.right 
     return None 



    def size(self,key): 
     node = self.root 
     #if root is not none 
     while node is not None: 
     #if the given node is the current node 
      if node.key == key: 
       #return itself 
       return self.size2(node) 
     #if the node that you are at is smaller than root 
      elif node.key > key: 
       node = node.left 
      else: 
       node = node.right 

    def size2(self,n): 
     #if node is none 
     if n is None: 
      #return 0 
      return 0 
     else: 
      #else track 
      return n.count 

    def depth(self, key): 
     return self.depth2(self.root, key) 

    def depth2(self, root, key, current_depth=0): 
     #if given node is not in the tree 
     if not root: 
      return -1 
     #inspect given key against current node (root) 
     #if current node and given node is match 
     elif root.key == key: 
      return current_depth 
     #if given node is less than current node 
     elif key < root.key: 
      return self.depth2(root.left, key, current_depth + 1) 
     else: 
      return self.depth2(root.right, key, current_depth + 1) 


    def height(self,key): 
     node = self.root 
     #if root is not none 
     while node is not None: 
     #if what you are searching for is the root 
      if node.key == key: 
       #return itself 
       return self.height2(node) 
     #if the node that you are at is smaller than root 
      elif node.key > key: 
       node = node.left 
      else: 
       node = node.right 


    def height2(self,n): 
     if n is None: 
      return -1 
     else: 
      #return the max 
      return 1 + max(self.height2(n.left),self.height2(n.right)) 


    def inOrder(self,n): 
     if n is None: 
      return 0 
     else: 
      self.inOrder(n.left) 
      print n.key , ": " , n.val; 
      self.inOrder(n.right) 

    def preOrder(self,n): 
     if n is None: 
      return 0 
     else: 
      print n.key , ": " , n.val; 
      self.preOrder(n.left) 
      self.preOrder(n.right) 

    def postOrder(self,n): 
     if n is None: 
      return 0 
     else: 
      self.postOrder(n.left) 
      self.postOrder(n.right) 
      print n.key , ": " , n.val; 

# ------------------------------------------------------------------------ 
    def deleteMin(self): 
     self.root = self.deleteMin2(self.root) 

    def deleteMin2(self, node): 
     if node.left is None: 
      return node.right 
     node.left = self.deleteMin2(node.left) 
     node.count = 1 + self.size2(node.left) + self.size2(node.right) 
     return node 

    def delete(self,key): 
     self.root = self.delete2(self.root,key) 

    def delete2(self,node,key): 
     if node is None: 
      return None 
     if key < node.key: 
      node.left = self.delete2(node.left,key) 
     elif(key > node.key): 
      node.right = self.delete2(node.right,key) 
     else: 
      if node.right is None: 
       return node.left 
      if node.left is None: 
       return node.right 
      t = node 
      node = self.min(t.right) 
      node.right = self.deleteMin2(t.right) 
      node.left = t.left 
     node.count = self.size2(node.left) + self.size2(node.right) + 1 
     return node 


class Node: 
    left = None 
    right = None 
    key = 0 
    val = 0 
    count = 0 



    def __init__(self, key, val): 
     self.key = key 
     self.val = val 
     self.count += 1 




bst = BST() 
bst.createTree() 
bst.drawTree("demo.png") 
node = bst.root 
print "Get: " , bst.get("C") , "\n" 
print "Size: ", bst.size("D"), "\n" 
print "Depth:", bst.depth("B"), "\n" 
print "Height:", bst.height("B"), "\n" 
print "\n In Order" 
bst.inOrder(node) 
print "\n Pre Order \n" 
bst.preOrder(node) 
print "\n Post Order \n" 
bst.postOrder(node) 


node = bst.root 
print bst.delete(node) 

Answer 1

Sie Attribute mit del löschen können, aber dass ich nicht sicher bin, ob das ist, was Sie tun möchten:

class Node: 
    def __init__(self): 
     self.root = 1 
n = Node() 
n 
<__main__.Node object at 0x101e6f278> 
n.root 
1 
del(n.root) 
n 
<__main__.Node object at 0x101e6f278> 
n.root 
Traceback (most recent call last): 
    Python Shell, prompt 6, line 1 
builtins.AttributeError: 'Node' object has no attribute 'root' 

Answer 2

Erste von allen, der Code, den Sie geben, fehlt die Methode min. Diese Methode findet der minimale Knoten im Unterbaum am Knoten verwurzelten gelöscht werden:

def min(self, node): 
    if node.left is None: 
     return node 
    else: 
     return self.min(node.left) 

Die delete Methode nicht alles zurückgeben

, weshalb bst.delete(node) druckt Keine. Delete-Methode erwartet übrigens einen Schlüssel, nicht den Knoten selbst. Nachdem Sie die oben min Methode BST-Klasse hinzufügen, versuchen, die letzten beiden Zeilen, um etwas zu ändern wie:

print "root: " + bst.root.key 
bst.delete(bst.root.key) 
print "root: " + bst.root.key 

Und Sie werden sehen, es zuerst „F“ druckt und dann löschen wir „F“, die das passiert sein Wurzel. Danach wird Wurzel "G" und es wird gedruckt.

Um einen beliebigen Knoten zu löschen, tun Sie einfach bst.delete(key) wo Schlüssel ist der Schlüssel des Knotens, den Sie löschen möchten.