Creating A Binary Search Tree in RubyA detailed, general tutorial on the binary tree data structure ( with a C Program ) is available here : Binary Search Trees - Tutorial with C Program Source Code and Documentation. Over here, we take a quick look at a Ruby program to construct and traverse through a Binary Tree. Hopefully the documentation and the comments will enable you to figure out the important ideas involved over here. # 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 Check out some of our other Ruby Tutorials : Introduction to RubyBasic Data Structures With Ruby | Introduction to Ruby and some playing around with the Interactive Ruby Shell (irb) Introduction to Ruby - Conditional statements and Modifiers: If-then, Unless, Case Introduction to Ruby Comments - Single and Multi-Line comments Introduction to Ruby Loops - Using While, Until, For, Break, Next , Redo, Retry Introduction to Ruby - Arrays - Sorting, Filtering (Select), Transforming, Multi-Dimensional Arrays Introduction to Ruby - Strings Introduction to Ruby - Making a Script Executable Introduction to Ruby - Regular Expressions, Match, Scan Introduction to Ruby - Computing Factorials Recursively : An Example of Recursion Introduction to Ruby - Binomial Coefficients (nCr) : An Example of Recursion Introduction to Ruby - Computing a Power Set : An Example of Recursion Introduction to Ruby - Towers of Hanoi : An Example of Recursion Introduction to Ruby - Strings: Substitution, Encoding, Built-In Methods Basic Data Structures in Ruby - Insertion Sort Basic Data Structures in Ruby - Selection Sort Basic Data Structures in Ruby - Merge Sort Basic Data Structures in Ruby - Quick Sort Functional Programming with Ruby Basic Data Structures in Ruby - Stack Basic Data Structures in Ruby - The Queue Basic Data Structures in Ruby - Linked List - ( A Simple, Singly Linked List) |
Computer Science >