ruby 什么是正确的逻辑修复，以获得这个二叉树删除方法正常工作？

sxpgvts3 于 2023-04-29 发布在 Ruby

关注(0)|答案(1)|浏览(112)

我正在尝试写一个方法来从二叉树中删除一个值。然而，我在删除一个有两个孩子的节点的情况下，我的逻辑失败了。我使用的是“用右树中的最低值替换删除的节点”方法，但我在保留正确的子节点指针时遇到了问题，我想从删除的节点中删除这些子节点指针。有谁能为我指明正确的方向，让它正确工作，欢迎任何关于更好代码的一般性建议。先谢谢你了。

节点#delete（）

def delete(root, value)
    if root == nil
      return root
    elsif value < root.value
      root.left = delete(root.left, value)
    elsif value > root.value
      root.right = delete(root.right, value)
    else root.value == value 
      puts 'must have found the value'
      # case 1 - no children, just delete
      if root.left.nil? && root.right.nil?
        root = nil  
      # case 2 - one child, just delete and replace with child
      elsif root.left.nil?
        root = root.right
      elsif root.right.nil?
        root = root.left
      # case 3 - 2 children, find min value in right subtree and replace with this
      else
        left_node = root.left
        root = min_value(root.right)
        root.left = left_node
      end
    end
    return root
  end

上下文编码：
节点类：

class Node
  attr_accessor :value, :left, :right
  
  def initialize(value)
    @value = value
    @left = nil
    @right = nil
  end

  def self.build_balanced_tree(array)
    ... (accurately builds a balance binary tree - ommited for brevity)
  end
end

树类

class Tree
  attr_reader :root

  def initialize(array)
    @root = Node.build_balanced_tree(array)
  end
  
  def self.build_balanced_tree(array)
    tree = Tree.new(array)
    return tree
  end

  def min_value(root)
    current = root
    current = current.left until current.left.nil?
    return current
  end

  def nice_print(node, prefix = '', is_left = true)
    nice_print(node.right, "#{prefix}#{is_left ? '│   ' : '    '}", false) if node.right
    puts "#{prefix}#{is_left ? '└── ' : '┌── ' }#{node.value}"
    nice_print(node.left, "#{prefix}#{is_left ? '    ' : '│   '}", true) if node.left
  end
end

脚本

array = [83, 65, 99, 36, 7, 90, 25, 95, 68, 39, 96, 13, 75, 89, 2]
  tree = Tree.build_balanced_tree(array)
  tree.nice_print(tree.root)
  tree.delete(tree.root, 25)
  tree.nice_print(tree.root)

ruby

来源：https://stackoverflow.com/questions/76076537/whats-the-correct-logic-fix-to-get-this-binary-tree-delete-method-working-prope

1条答案

按热度按时间

jjjwad0x1#

删除算法假设你的树是二叉搜索树，但它不是。所以算法会转到错误的子树，找不到要删除的值。build_balanced_tree插入节点，使得中序遍历对应于给定的数组顺序。所以要么你必须给它一个排序的数组，要么应该根据BST插入算法一个接一个地插入值。
案例#3缺少正确的return语句：你应该返回原始root的右子元素（在它被重新分配之前）。修改这个代码：

left_node = root.left
    root = min_value(root.right)
    root.left = left_node

致：

min_value(root.right).left = root.left
    return root.right

其他说明

主代码必须将root作为参数传递给许多方法，这并不优雅。我将把这些方法移到Node类中，并在Tree类上创建小的 Package 方法，这些方法在根节点上调用这些方法。这样主程序就不必传递那个根参数了。

代码

通过一些其他的小修改，代码可能看起来像这样，它使用BST插入算法（我省略了build_balanced_tree方法）：

class Node
  attr_accessor :value, :left, :right
  
  def initialize(value)
    @value = value
    @left = nil
    @right = nil
  end

  def insert(value)
    if value < @value
      @left = @left ? @left.insert(value) : Node.new(value)
    elsif value > @value 
      @right = @right ? @right.insert(value) : Node.new(value)
    end
    return self
  end

  def delete(value)
    if value < @value
      @left = @left&.delete(value)
    elsif value > @value
      @right = @right&.delete(value)
    else
      puts 'must have found the value'
      # case 1 - no children, just delete
      return if @left.nil? && @right.nil?
      # case 2 - one child, just delete and replace with child
      return @right if @left.nil?
      return @left  if @right.nil?
      # case 3 - 2 children, find min value in right subtree and replace with this
      @right.min_value().left = @left
      return @right
    end
    return self
  end

  def min_value()
    current = self
    current = current.left until current.left.nil?
    return current
  end

  def nice_print(prefix = '', is_left = true)
    @right&.nice_print("#{prefix}#{is_left ? '│   ' : '    '}", false)
    puts "#{prefix}#{is_left ? '└── ' : '┌── ' }#{@value}"
    @left&.nice_print("#{prefix}#{is_left ? '    ' : '│   '}", true)
  end
      
end

class Tree
  attr_reader :root

  def initialize(array)
    @root = nil
    array.each { |n| insert(n) }
  end

  def insert(value)
    @root = @root ? @root.insert(value) : Node.new(value)
  end

  def delete(value)
    @root = @root&.delete(value)
  end

  def nice_print()
    @root&.nice_print()
  end

end


array = [83, 65, 99, 36, 7, 90, 25, 95, 68, 39, 96, 13, 75, 89, 2]
tree = Tree.new(array)
tree.nice_print()
tree.delete(7) 
tree.nice_print()

赞(0）回复(0）举报 2023-04-29

我来回答

ruby 什么是正确的逻辑修复，以获得这个二叉树删除方法正常工作？

1条答案

其他说明

代码

相关问题

热门标签

最新问答