Created
April 3, 2011 04:07
-
-
Save ryanbriones/900168 to your computer and use it in GitHub Desktop.
trying to understand binary trees using Ruby. had this on my desktop, wanted it off, but didn't want to lose it
This file contains 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
class BinaryTree | |
def initialize | |
@size = 0 | |
@root = nil | |
end | |
def insert(data) | |
node = BinaryTreeNode.new(data) | |
if @root.nil? | |
@root = node | |
else | |
@root.insert(node) | |
end | |
end | |
def in_order | |
@root.in_order | |
end | |
def pre_order | |
@root.pre_order | |
end | |
def post_order | |
@root.post_order | |
end | |
end | |
class BinaryTreeNode | |
include Comparable | |
attr_reader :data | |
def <=>(another) | |
self.data <=> another.data | |
end | |
def initialize(data) | |
@data = data | |
@left = nil | |
@right = nil | |
end | |
def insert(node) | |
position = self <=> node | |
case position | |
when 1 | |
if(@left.nil?) | |
@left = node | |
else | |
@left.insert(node) | |
end | |
when -1 | |
if(@right.nil?) | |
@right = node | |
else | |
@right.insert(node) | |
end | |
else | |
raise "something bad happened" | |
end | |
end | |
def in_order | |
@left.in_order if @left | |
puts self.data | |
@right.in_order if @right | |
end | |
def pre_order | |
puts self.data | |
@left.pre_order if @left | |
@right.pre_order if @right | |
end | |
def post_order | |
@left.pre_order if @left | |
@right.pre_order if @right | |
puts self.data | |
end | |
end | |
tree = BinaryTree.new | |
tree.insert(5) | |
tree.insert(3) | |
tree.insert(8) | |
tree.insert(1) | |
tree.insert(4) | |
tree.in_order | |
puts | |
tree.pre_order | |
puts | |
tree.post_order | |
class BinarySearchTree < BinaryTree | |
def insert(data) | |
node = AVLNode.new(data) | |
if(@root.nil?) | |
@root = node | |
else | |
@root.insert(node) | |
end | |
end | |
end | |
class AVLNode | |
def initialize(data) | |
@data = data | |
@left = nil | |
@right = nil | |
@factor = 0 | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment