返回平衡二叉搜索树中的 Level-1 节点 Ruby？

Question

我正在使用排序数组在 Ruby 中递归创建平衡二叉搜索树。但是，我在结束 return 值时遇到问题。不是所有节点冒泡，创建树并 returning 基本级别 1 节点，树底部的最后一个节点是 returned.

似乎正在创建的节点根本 link 在一起（仅使用 p list 打印实例化 class 最后一个节点 return ).如何 link 节点和 return 级别 1 根节点？

代码：

class Node
  include Comparable

  attr_accessor :value, :left, :right

  def initialize(value, left = nil, right = nil)
    @value = value
    @left = left
    @right = right
  end
end

class Tree
  attr_accessor :sorted_arr, :arr

  def initialize(arr)
    @arr = arr
    @sorted_arr = arr.sort.uniq
  end

  #Problem: nodes not being linked together

  def build_tree(arr, start, last)
    if start > last
      return nil
    end

    mid_index = (start + last) / 2
    
    @root = Node.new(arr[mid_index])


    @root.left = build_tree(arr, start, mid_index - 1)
    @root.right = build_tree(arr, mid_index + 1, last)


    return @root
  end
end

list = Tree.new([1, 7, 4, 23, 8, 9, 4, 3, 6, 7, 9, 67, 6345, 324])
list.build_tree(list.sorted_arr, 0, list.sorted_arr.length-1)
p list

Answer 1

您应该使用 root 而不是 @root。
以 @ 开头的是实例变量，因此当您调用时：

@root.left = build_tree(arr, start, mid_index - 1)

在那个 build_tree 调用中，最终你也会调用 @root = Node.new(arr[mid_index]) 它将替换父调用中已经设置的值。

返回平衡二叉搜索树中的 Level-1 节点 Ruby？

Returning Level-1 Node In a Balanced Binary Search Tree Ruby?

ruby

data-structures

binary-search-tree