用Ruby實現樹

Question

至於在Ruby中我們沒有類似C++的指針，我們如何實現樹？

Answer 1

您不一定需要建築樹木的指針或參考，是嗎？

這是一個基本的例子：

class Tree 
    attr_accessor :children, :value 

    def initialize(v) 
    @value = v 
    @children = [] 
    end 
end 

t = Tree.new(7) 
t.children << Tree.new(3) 
t.children << Tree.new(11) 

t.value    # 7 
t.children[0].value # 3 
t.children[1].value # 11 

Answer 2

在Ruby中的一切使用引用語義：

a = "hello" 
b = a 
b << " world" 
puts a # => hello world 

所以建立一個樹將不會有任何難度要比它通常是。

Answer 3

一個並不真正需要明確的指針。儘管人們可能會期待這一點，因爲他們經常在C和C++中學習自引用數據結構，並期望看到相當於前面帶*號的點。我相信下面的代碼片段可能會有用。

編號：http://www.thelearningpoint.net/computer-science/basic-data-structures-in-ruby---binary-search-tre

# 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