我一直想在Ruby中实现二叉树类，但我得到的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
编辑：我的问题已经有点偏离轨道。 当前的代码设置给我的stack level too deep ，在第8行的错误但是，如果我聘请埃德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
说实话，虽然...你为什么不只是初始化左右，以零开始说起？ 他们没有价值观还没有，那么你来获得？ 它使语义上更有意义; 您创建一个新的列表包含一个元素，即左，右的元素还不存在。 我只想用：
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 - 你给裁判是很好的一个，但我认为这是在代码中的小的变化。 需要更新预购和后序代码如下
# 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 - > 10 - > 5 - > 7 - > 11 - > 18 - > 17
后序遍历
7 - > 5 - > 9 - > 17 - > 18 - > 11 - > 10
