ruby - 删除二叉搜索树中的一个节点。在某些地方存在逻辑错误，但我无法弄清楚？

Question

class Tree 
  attr_accessor :root
    
  def initialize 
    @root=nil
  end

  private
    
    def get_new_node(node)
      Node.new(node)
    end

  public  

  def insert(val1)
    @root = get_new_node(val1) if @root.nil?
    _insert(@root,val1)
  end

  def _insert(node,val2)
    return get_new_node(val2) if node.nil?

    if(node.val > val2)
      node.left = _insert(node.left,val2)
    else
      node.right = _insert(node.right,val2)
    end
      
    node
  end

  def search(val3,node1=nil)
    return false if node1.nil?

    if node1.val == val3
      return true
    elsif val3 < node1.val
      search(val3,node1.left)
    elsif val3 > node1.val
      search(val3,node1.right)
    else
      return false   
    end
  end

  def _post(node)
    return nil if node.nil?
    _post(node.left)
    _post(node.right)
      puts(node.val)
  end
 
  def _in(node,arr=nil)
    return nil if node.nil?
    _in(node.left,arr)
    a=node.val
    arr.push(a)
    _in(node.right,arr)
  end

  def _pre(node)
    return nil if node.nil?
    puts(node.val)
    _pre(node.left)
    _pre(node.right)
  end

  def _height(node)
    if node==null
      return 0
    else
      lh=height(node.left)
      lr=height(node.right)

      if lh > rh
        return lh+1
      else
        return rh+1
      end
    end
  end

  def _print_level(node)
    h=_height(node).to_i
    i=1;
    h.times{ bft(node,i); i+=1; }
  end

  def bft(node,level)
    return nil if node==nil

    if level == 1
      puts(node.val)
    elsif (level>1) 
      bft(node.left,level-1)
      bft(node.right,level-1)
    end
   end

  # Finds the inorder Sucessor to be replaced with the deleted node
  def _inorder_sucessor(node,val=nil) 
    a=[]
    _in(node,a)
    c = a.find_index(val)
    return a[c+1] unless val.nil? 
  end

  # Finds the node in the tree for the given value
  def delete_search(node,val) 
    if node.val == val
      return node
    elsif node.val > val
      delete_search(node.left,val)
    elsif node.val < val
      delete_search(node.right,val)
    end
  end

  # Gets the input value for the node to be deleted
  def delete(node,val) 
    return nil  if node.nil?
    node1=delete_search(node,val)
    _delete(node1,val)
  end

  # Deletes the node depend upon the value
  def _delete(node,val) 

    #a= node.left <=> node.right 

    if node.left==nil && node.right == nil
      node=nil
    elsif node.left!=nil && node.right==nil
      node=node.left
    elsif node.left==nil && node.right!=nil
      node=node.right
    elsif node.left!=nil && node.right!=nil
      node= _delete_double(node,val)
    end

    node
  end

  # Function to delete if the node has two children
  def _delete_double(node,val) 
    replace_val= _inorder_sucessor(node,val) # Finds the inorder sucessor
   
    replace_node=replace(node,val,replace_val) # Finds the node of the inorder sucessor
    node.val=replace_node.val
    
    # Replaces the node with inorder sucessor and delete's the inorder sucessor node
    replace_node=nil
    node  
  end

  def replace(node,val,replace_val) # Function to replace the node with inorder sucessor node
    if node.val == replace_val
      return node
    elsif node.val > replace_val
      replace(node.left,val,replace_val)
    else
      replace(node.right,val,replace_val)
    end
  end
end
  
class Node 
  attr_accessor :left , :right ,:val
  
  def initialize(val = nil)
    @val = val
    @left=nil
    @rigth=nil
  end
end

bst = Tree.new()

# Binary Tree creation
print ("Enter the number of nodes in the tree : ");
a = gets.chomp!;
puts ();
i = 1;
a.to_i.times { print "Enter the #{i} node : "; b=gets.chomp; bst.insert(b.to_i); i+=1;  }
#Binary Search
bst.delete(bst.root,20)
puts("PRE 20")

在上面的代码中，请通过删除功能。据我所知，我没有发现任何逻辑错误。但它有一个我无法弄清楚。请帮我解决这个问题。

期望的输出：

Tree :20 30 40 50 60 70 80
Delete 20
Modified tree
30 40 50 60 70 80

但我得到的输出是：

50 30 20 40 50 70 60 80

如您所见，它还会两次打印根节点（又名 50）。我不明白为什么会这样。必须删除的所需节点也不会被删除。

标签： rubydata-structurestreebinary-treebinary-search-tree