6

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

編集：私の質問は少し軌道から外れました。現在のコード設定では、stack level too deep8行目でエラーが発生します。ただし、Ed S.のソリューションを採用すると

@left = @right = nil

次に、<<メソッドは次のように不平を言います：undefined method '<<' for nil:NilClass (NoMethodError)22行目。

誰でもこれを解決する方法を提案できますか? BinaryTree私の考えは、変数leftとrightが のインスタンスであるBinaryTree(つまり、それらの型が である) ことを何らかの方法でクラスに伝えることができれば、BinaryTreeすべてうまくいくということです。私が間違っている？

4

4 に答える 4

12

その特定のコードでは再帰を使用していないようですが:

まだ...

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 に初期化しないのですか? 彼らはまだ値を持っていないので、あなたは何を得ていますか? 意味的にはより理にかなっています。要素が 1 つの新しいリストを作成します。つまり、左右の要素はまだ存在しません。私はただ使用します：

def initialize(value=nil)
    @value = value
    @left = @right = nil
end
于 2012-08-30T20:46:38.067 に答える
2 
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
于 2012-08-30T23:19:44.393 に答える
1

コード内の無限再帰を修正する必要がある場合があります。二分木の実際の例を次に示します。再帰をどこかで終了するには、基本条件が必要です。そうしないと、無限の深さのスタックになります。

自己参照データ構造の例 - 二分木

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

于 2016-03-24T22:53:38.147 に答える
0

@ 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

于 2019-03-04T19:22:34.620 に答える