我在 ruby 中实现了二叉搜索树，但我在获取节点的父节点时遇到了问题

Question

由于树的初始化方式，任何节点都知道它是子节点而不是父节点。

如何在不传递父项的情况下找到父项，或者这是唯一的方法吗？除非有一种方法可以自动将引用传递给父级？

目前我创建的树是这样的：

Node[
    5,
    Node[
        2,
        nil,
        Node[
            3
        ]
    ],
    Node[
        9,
        node[
            7
        ]
    ]
]

Answer 1

绝对有可能。您可以在分配 left 或 right 时设置父级：

class Node
  attr_accessor :key, :parent
  attr_reader :left, :right

  def self.[](key, left = nil, right = nil)
    new(key, left, right)
  end

  def initialize(key, left, right)
    @key = key
    self.left = left
    self.right = right
  end

  def left=(node)
    node.parent = self if node
    @left = node
  end

  def right=(node)
    node.parent = self if node
    @right = node
  end
end

示例：

root = Node[
         5,
         Node[
             2,
             nil,
             Node[
                 3
             ]
         ],
         Node[
             9,
             Node[
                 7
             ]
         ]
       ]

root.key #=> 5
root.left.key # => 2
root.left.parent.key #=> 5
root.left.parent == root #=> true

我在 ruby 中实现了二叉搜索树，但我在获取节点的父节点时遇到了问题

I'm implementing a Binary Search tree in ruby but I'm having an issue with getting a node's parent

ruby

binary-search-tree