Last active
August 29, 2015 14:12
-
-
Save launchkit-codes/505771517f2b65310611 to your computer and use it in GitHub Desktop.
Getting started with Binary Trees and Ruby
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # Example: | |
| # | |
| # 1 | |
| # / \ | |
| # 2 12 | |
| # / | |
| # 4 | |
| class Node | |
| attr_accessor :left, :right, :value | |
| def initialize(left, right, value) | |
| @left = left | |
| @right = right | |
| @value = value | |
| end | |
| end | |
| class Tree | |
| def initialize | |
| left = Node.new(nil,nil,2) | |
| right = Node.new(nil,nil,12) | |
| left.left = Node.new(nil,nil,4) | |
| @root = Node.new(left, right, 1) | |
| end | |
| def depth | |
| puts tree_depth(@root) | |
| end | |
| def values | |
| tree_values(@root); puts | |
| end | |
| def max | |
| puts tree_max(@root) | |
| end | |
| def min | |
| puts tree_min(@root) | |
| end | |
| def total | |
| puts tree_total(@root) | |
| end | |
| private | |
| def tree_values(node) | |
| print("#{node.value} ") | |
| tree_values(node.left) unless node.left.nil? | |
| tree_values(node.right) unless node.right.nil? | |
| end | |
| def tree_depth(node) | |
| return 0 if node.nil? | |
| left = tree_depth(node.left) + 1 | |
| right = tree_depth(node.right) + 1 | |
| if left > right | |
| return left | |
| else | |
| return right | |
| end | |
| end | |
| def tree_max(node) | |
| return 0 if node.nil? | |
| max_left = tree_max(node.left) | |
| max_right = tree_max(node.right) | |
| if max_left > node.value && max_left > max_right | |
| return max_left | |
| elsif max_right > node.value | |
| return max_right | |
| else | |
| return node.value | |
| end | |
| end | |
| def tree_min(node) | |
| return 42 if node.nil? | |
| max_left = tree_min(node.left) | |
| max_right = tree_min(node.right) | |
| if max_left < node.value && max_left < max_right | |
| return max_left | |
| elsif max_right < node.value | |
| return max_right | |
| else | |
| return node.value | |
| end | |
| end | |
| def tree_total(node) | |
| return 0 if node.nil? | |
| return node.value + (tree_total(node.left) + tree_total(node.right)) | |
| end | |
| end | |
| puts "Tree nodes values:"; Tree.new.values | |
| puts "Tree depth:"; Tree.new.depth | |
| puts "Tree total:"; Tree.new.total | |
| puts "Tree max value:"; Tree.new.max | |
| puts "Tree min value:"; Tree.new.min | |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| $> ruby my_tree.rb | |
| Tree nodes values: | |
| 1 2 4 12 | |
| Tree depth: | |
| 3 | |
| Tree total: | |
| 19 | |
| Tree max value: | |
| 12 | |
| Tree min value: | |
| 1 | |
| $> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment