我一直在尝试在Ruby中实现BinaryTree类，但是我得到了stack level too deep错误，虽然我似乎没有在那段特定的代码中使用任何递归：
1. class BinaryTree
2. include Enumerable
3.
4. attr_accessor :value
5.
6. def initialize( value = nil )
7. @value = value
8. @left = BinaryTree.new # stack level too deep here
9. @right = BinaryTree.new # and here
10. end
11.
12. def empty?
13. ( self.value == nil ) ? true : false
14. end
15.
16. def <<( value )
17. return self.value = value if self.empty?
18.
19. test = self.value <=> value
20. case test
21. when -1, 0
22. self.right << value
23. when 1
24. self.left << value
25. end
26. end # <<
27.
28. end
编辑：我的问题有点偏离轨道。当前代码设置在第8行给出了stack level too deep错误。但是，如果我使用Ed S.的解决方案
@left = @right = nil
然后<<方法抱怨说：undefined method '<<' for nil:NilClass (NoMethodError)在第22行。
谁能建议如何解决这个问题？我的想法是，如果我能以某种方式告诉BinaryTree类变量left和right是BinaryTree的实例（即它们的类型是BinaryTree）它会一切都很好。我错了吗？
虽然我似乎没有在那段特定的代码中使用任何递归：
然而...
def initialize( value = nil )
@value = value
@left = BinaryTree.new # this calls initialize again
@right = BinaryTree.new # and so does this, but you never get there
end
那是无限递归。你打电话给initilize，后者又打电话给new，后者又打电话给initialize ......我们走了。
你需要在那里添加一个防护来检测你已经初始化了主节点并且现在正在初始化叶子，在这种情况下，@left和@right应该被设置为nil。
def initialize( value=nil, is_sub_node=false )
@value = value
@left = is_sub_node ? nil : BinaryTree.new(nil, true)
@right = is_sub_node ? nil : BinaryTree.new(nil, true)
end
说实话，虽然......为什么你不是只是从左到右初始化nil开始？他们还没有价值观，所以你获得了什么？它在语义上更有意义;您创建一个包含一个元素的新列表，即左侧和右侧的元素尚不存在。我会用：
def initialize(value=nil)
@value = value
@left = @right = nil
end
1. class BinaryTree
2. include Enumerable
3.
4. attr_accessor :value
5.
6. def initialize( value = nil )
7. @value = value
8. end
9.
10. def each # visit
11. return if self.nil?
12.
13. yield self.value
14. self.left.each( &block ) if self.left
15. self.right.each( &block ) if self.right
16. end
17.
18. def empty?
19. # code here
20. end
21.
22. def <<( value ) # insert
23. return self.value = value if self.value == nil
24.
25. test = self.value <=> value
26. case test
27. when -1, 0
28. @right = BinaryTree.new if self.value == nil
29. self.right << value
30. when 1
31. @left = BinaryTree.new if self.value == nil
32. self.left << value
33. end
34. end # <<
35. end
您可能需要在代码中修复无限递归。这是一个二叉树的工作示例。你需要有一个基本条件来终止你的递归，否则它将是一个无限深度的堆栈。
# Example of Self-Referential Data Structures - A Binary Tree
class TreeNode
attr_accessor :value, :left, :right
# The Tree node contains a value, and a pointer to two children - left and right
# Values lesser than this node will be inserted on its left
# Values greater than it will be inserted on its right
def initialize val,left,right
@value = val
@left = left
@right = right
end
end
class BinarySearchTree
# Initialize the Root Node
def initialize val
puts "Initializing with: " + val.to_s
@root = TreeNode.new(val,nil,nil)
end
# Pre-Order Traversal
def preOrderTraversal(node= @root)
return if (node == nil)
preOrderTraversal(node.left)
preOrderTraversal(node.right)
puts node.value.to_s
end
# Post-Order Traversal
def postOrderTraversal(node = @root)
return if (node == nil)
puts node.value.to_s
postOrderTraversal(node.left)
postOrderTraversal(node.right)
end
# In-Order Traversal : Displays the final output in sorted order
# Display smaller children first (by going left)
# Then display the value in the current node
# Then display the larger children on the right
def inOrderTraversal(node = @root)
return if (node == nil)
inOrderTraversal(node.left)
puts node.value.to_s
inOrderTraversal(node.right)
end
# Inserting a value
# When value > current node, go towards the right
# when value < current node, go towards the left
# when you hit a nil node, it means, the new node should be created there
# Duplicate values are not inserted in the tree
def insert(value)
puts "Inserting :" + value.to_s
current_node = @root
while nil != current_node
if (value < current_node.value) && (current_node.left == nil)
current_node.left = TreeNode.new(value,nil,nil)
elsif (value > current_node.value) && (current_node.right == nil)
current_node.right = TreeNode.new(value,nil,nil)
elsif (value < current_node.value)
current_node = current_node.left
elsif (value > current_node.value)
current_node = current_node.right
else
return
end
end
end
end
bst = BinarySearchTree.new(10)
bst.insert(11)
bst.insert(9)
bst.insert(5)
bst.insert(7)
bst.insert(18)
bst.insert(17)
# Demonstrating Different Kinds of Traversals
puts "In-Order Traversal:"
bst.inOrderTraversal
puts "Pre-Order Traversal:"
bst.preOrderTraversal
puts "Post-Order Traversal:"
bst.postOrderTraversal
=begin
Output :
Initializing with: 10
Inserting :11
Inserting :9
Inserting :5
Inserting :7
Inserting :18
Inserting :17
In-Order Traversal:
5
7
9
10
11
17
18
Pre-Order Traversal:
7
5
9
17
18
11
10
Post-Order Traversal:
10
9
5
7
11
18
17
=end
参考：http://www.thelearningpoint.net/computer-science/basic-data-structures-in-ruby---binary-search-tre
@ pranshantb1984 - 你提供的参考资料很好，但我认为代码有一点变化。需要更新PreOrder和PostOrder代码，如下所示
# Post-Order Traversal
def postOrderTraversal(node= @root)
return if (node == nil)
postOrderTraversal(node.left)
postOrderTraversal(node.right)
puts node.value.to_s
end
# Pre-Order Traversal
def preOrderTraversal(node = @root)
return if (node == nil)
puts node.value.to_s
preOrderTraversal(node.left)
preOrderTraversal(node.right)
end
预订遍历
10 -> 9 -> 5 -> 7 -> 11 -> 18 -> 17
邮政订单遍历
7 -> 5 -> 9 -> 17 -> 18 -> 11 -> 10