让这个二叉树删除方法正常工作的正确逻辑修复是什么？

Question

我正在尝试编写一种方法来从二叉树中删除一个值。但是，对于删除具有两个子节点的节点的情况，我的逻辑失败了。我正在使用“从正确的树方法中用最低值替换已删除的节点”，但是我在保留我想要从已删除节点中获取的正确子节点指针时遇到了问题。任何人都可以指出我正确的方向以使其正常工作，并且欢迎任何有关更好代码的一般性建议。提前致谢。

节点#删除（）

  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)

Answer 1

您的删除算法假定您的树是二叉搜索树，但事实并非如此。因此该算法转到了错误的子树并且没有找到要删除的值。

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

类上创建小包装方法，在根节点上调用这些方法。这样主程序就不必传递那个根参数。

代码

通过一些其他的小改动，代码可能看起来像这样，它使用了 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()