İkili Arama Ağacını sil

Question

İkili Arama Ağacının düğümünü silmeye çalışıyorum Yazdırdığımda elde ettiğim sonuç aslında yok Bu silme işlemi, aslında ikili ağacın kendisinden herhangi bir anahtarı silebilir.

Binary Search Tree ürününe yeni geliyorum. Birisi bana kodumla yardım edebilir mi? Yardım size yardımcı olacaktır.

Teşekkür

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 

Tam Kod

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

Eğer yapmak istediğiniz buysa ben emin değilim del ile özelliklerini silmek ancak

:

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

İlk Hepsinin, verdiğiniz kod min yönteminden yoksundur. Bu yöntem düğümde köklü alt ağaç asgari düğüm silinmesini bulur:

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

delete yöntem şey dönmez, o yüzden bst.delete(node) baskılar Yok şeklindedir. Bu arada, silme yöntemi, düğümün kendisinden değil, bir anahtar bekler. Eğer BST sınıfına yukarıdaki min yöntemi ekledikten sonra, böyle bir şey için son iki satır değiştirmeyi deneyin: olur

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

Ve bunun ilk "F" yazdırır göreceksiniz ve sonra biz delete "F" kök. Bundan sonra kök "G" olur ve yazdırılır.

Herhangi bir rasgele düğümü silmek için, yalnızca silmek istediğiniz düğümün anahtarı olan bst.delete(key)'u yapın.