Created
October 20, 2008 07:08
-
-
Save bastos/18032 to your computer and use it in GitHub Desktop.
Binary tree example!
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
| #!/usr/bin/env ruby | |
| # -*- coding: utf-8 -*- | |
| require 'rubygems' | |
| class BinaryTree | |
| attr_reader :root | |
| # Por padrão busca por root primeiro | |
| def search(value, node=@root) | |
| if node == nil | |
| return nil | |
| elsif value < node.value | |
| return search(value, node.left) | |
| elsif value > node.value | |
| return search(value, node.right) | |
| else | |
| return node | |
| end | |
| end | |
| def traverse_inorder( node=@root, &block ) | |
| return if node.nil? | |
| traverse_inorder( node.left, &block ) | |
| yield node | |
| traverse_inorder( node.right, &block ) | |
| end | |
| def traverse_preorder( node=@root, &block ) | |
| return if node.nil? | |
| yield node | |
| traverse_preorder( node.left, &block ) | |
| traverse_preorder( node.right, &block ) | |
| end | |
| def traverse_postorder( node=@root, &block ) | |
| return if node.nil? | |
| traverse_postorder( node.left, &block ) | |
| traverse_postorder( node.right, &block ) | |
| yield node | |
| end | |
| def add(value, node=@root) | |
| if node == nil | |
| node = BinaryTreeNode.new(value) | |
| @root = node if not @root | |
| return node | |
| else | |
| if value < node.value | |
| node.left = add(value, node.left) | |
| elsif value > node.value | |
| node.right = add(value, node.right) | |
| else | |
| raise "Item duplicado" | |
| end | |
| return node | |
| end | |
| end | |
| end | |
| class BinaryTreeNode | |
| attr_accessor :value, :left, :right, :is_root | |
| def initialize(value) | |
| @value = value | |
| end | |
| def left=(node) | |
| puts "Adicionado #{node.value} a #{self.value} esquerda" | |
| @left=node | |
| end | |
| def to_s | |
| "#{@value}" | |
| end | |
| def right=(node) | |
| puts "Adicionado #{node.value} a #{self.value} direita" | |
| @right=node | |
| end | |
| end |
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
| #!/usr/bin/env ruby | |
| require 'rubygems' | |
| require 'open-uri' | |
| require 'cgi' | |
| require 'misc' | |
| cgi = CGI.new() # New CGI object | |
| puts "Content-type: text/html\n\n" | |
| if cgi.has_key?('number_of') | |
| number_of = cgi['number_of'].to_i | |
| else | |
| number_of = 3 | |
| end | |
| nodes_inputs = "" | |
| (1..number_of).each do |i| | |
| nodes_inputs += "<p>Nó #{i} <input name=\"node[]\"/> </p>" | |
| end | |
| cgi.params['node[]'] = [10,3,11,40] unless cgi.include?('node[]') | |
| begin | |
| if cgi.params.has_key?('node[]') | |
| tree = BinaryTree.new | |
| cgi.params['node[]'].uniq.each do |e| | |
| tree.add(e.to_i) | |
| end | |
| name = "#{ENV['REMOTE_ADDR']}" | |
| if cgi.params.has_key?('find') | |
| create_image_with_found_element(tree, tree.search(cgi['find'].to_i), name ) | |
| else | |
| create_image(tree, name) | |
| end | |
| img = "<img src=\"#{name}.png\" alt=\"Árvore\">" | |
| else | |
| img = cgi.params | |
| end | |
| rescue => e | |
| img = "<h1>ERRO #{e} :( Baleiando!<h1>" | |
| end | |
| puts <<END | |
| <html><head><meta content="text/html; charset=utf-8" http-equiv="Content-Type"/> | |
| <title>arvore</title> | |
| </head><body> | |
| <form method="POST"> | |
| #{img} | |
| <h1>Coloque os nós que você quer na árvore!</h1> | |
| <div>Número de Nós: <input name="number_of" value="#{number_of}"/></div> | |
| #{nodes_inputs} | |
| <div>Encontrar: <input name="find"/></div> | |
| <input type="submit" value="Enviar"/> | |
| </form> | |
| </body></html> | |
| END |
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
| require 'arvore' | |
| require 'graphviz' | |
| def create_image(tree, name="teste") | |
| g = GraphViz::new( "G" ) | |
| tree.traverse_preorder do |node| | |
| ngnode = g.add_node(node.to_s) | |
| if node.left | |
| ngnode << g.add_node(node.left.to_s) | |
| end | |
| if node.right | |
| ngnode << g.add_node(node.right.to_s) | |
| end | |
| end | |
| g.output( :output => "png", :file => "#{name}.png" ) | |
| end | |
| def create_image_with_found_element(tree, found, name="teste") | |
| g = GraphViz::new( "G" ) | |
| tree.traverse_preorder do |node| | |
| if found == node | |
| ngnode = g.add_node(node.to_s, :shape => "box", :style => "filled", :color => ".7 .3 1.0") | |
| else | |
| ngnode = g.add_node(node.to_s) | |
| end | |
| if node.left | |
| if found == node.left | |
| ngnode << g.add_node(node.left.to_s, :shape => "box", :style => "filled", :color => ".7 .3 1.0") | |
| else | |
| ngnode << g.add_node(node.left.to_s) | |
| end | |
| end | |
| if node.right | |
| if found == node.right | |
| ngnode << g.add_node(node.right.to_s, :shape => "box", :style => "filled", :color => ".7 .3 1.0") | |
| else | |
| ngnode << g.add_node(node.right.to_s) | |
| end | |
| end | |
| end | |
| g.output( :output => "png", :file => "#{name}.png" ) | |
| end |
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
| #!/usr/bin/env ruby | |
| # -*- coding: utf-8 -*- | |
| require 'arvore' | |
| require 'graphviz' | |
| def create_image(tree, name="teste") | |
| g = GraphViz::new( "G" ) | |
| tree.traverse_preorder do |node| | |
| ngnode = g.add_node(node.to_s) | |
| if node.left | |
| ngnode << g.add_node(node.left.to_s) | |
| end | |
| if node.right | |
| ngnode << g.add_node(node.right.to_s) | |
| end | |
| end | |
| g.output( :output => "png", :file => "#{name}.png" ) | |
| end | |
| def create_image_with_found_element(tree, found, name="teste") | |
| g = GraphViz::new( "G" ) | |
| tree.traverse_preorder do |node| | |
| if found == node | |
| ngnode = g.add_node(node.to_s, :shape => "box", :style => "filled", :color => ".7 .3 1.0") | |
| else | |
| ngnode = g.add_node(node.to_s) | |
| end | |
| if node.left | |
| if found == node | |
| ngnode << g.add_node(node.left.to_s, :shape => "box", :style => "filled", :color => ".7 .3 1.0") | |
| else | |
| ngnode << g.add_node(node.left.to_s) | |
| end | |
| end | |
| if node.right | |
| if found == node | |
| ngnode << g.add_node(node.right.to_s, :shape => "box", :style => "filled", :color => ".7 .3 1.0") | |
| else | |
| ngnode << g.add_node(node.right.to_s) | |
| end | |
| end | |
| end | |
| g.output( :output => "png", :file => "#{name}.png" ) | |
| end | |
| tree = BinaryTree.new | |
| (1..20).each { |i| | |
| begin | |
| tree.add(rand(100)) | |
| rescue | |
| # pass | |
| end | |
| } | |
| create_image(tree, name="teste") | |
| create_image_with_found_element(tree, tree.search(rand(100)), "found") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment