deleteバイナリ検索ツリー

Question

バイナリ検索ツリーのノードを削除しようとしています 印刷したときの結果は実際にはありません この削除は、実際にはバイナリツリー自体から何かキーを削除できます。

私はバイナリ検索ツリーを使い慣れました。 誰かが私のコードを手伝ってくれますか？ あなたは助けられるでしょう。

おかげ

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 

完全なコード

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

あなたはdelと属性を削除することができますが、私はそれはあなたが何をしたいかどうか分からないこと：

まず

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

あなたのコードには、メソッドminが欠けています。その方法は、削除されたノードをルートとするサブツリーで最小のノードを検索します。

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

deleteその方法が、なぜbst.delete(node)プリントなしではありません、何も返しません。ちなみに、deleteメソッドは、ノード自体ではなく、キーを要求します。あなたはBSTクラスに上記min方法を追加した後、のようなものに最後の2行を変更してみてください：であることを起こる

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

そして、あなたはそれが最初の「F」を印刷し表示されますし、我々は削除「F」ルート。その後、ルートは「G」になり、それが印刷されます。

任意のノードを削除するには、bst.delete(key)を実行します。ここで、keyは、削除するノードのキーです。