在Ruby中实现二叉树
我一直在尝试在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行的undefined method '<<' for nil:NilClass (NoMethodError) 。
谁能建议如何解决这个问题？ 我的想法是，如果我能以某种方式告诉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