Ruby/Collections/Your tree

Материал из Wiki.crossplatform.ru

(Различия между версиями)

Текущая версия на 17:55, 13 сентября 2010

Содержание

1 Create Your tree
2 infix
3 inorder / preorder / postorder
4 Loop through a tree
5 search a tree
6 to array
7 to string
8 Writing an Iterator Over a Data Structure

Create Your tree

class Tree
  attr_accessor :left
  attr_accessor :right
  attr_accessor :data
  def initialize(x=nil)
    @left = nil
    @right = nil
    @data = x
  end
  def insert(x)
    list = []
    if @data == nil
      @data = x
    elsif @left == nil
      @left = Tree.new(x)
    elsif @right == nil
      @right = Tree.new(x)
    else
      list << @left
      list << @right
      loop do
        node = list.shift
        if node.left == nil
          node.insert(x)
          break
        else
          list << node.left
        end
        if node.right == nil
          node.insert(x)
          break
        else
          list << node.right
        end
      end
    end
  end
  def traverse()
    list = []
    yield @data
    list << @left if @left != nil
    list << @right if @right != nil
    loop do
      break if list.empty?
      node = list.shift
      yield node.data
      list << node.left if node.left != nil
      list << node.right if node.right != nil
    end
  end
end
 
  items = [1, 2, 3, 4, 5, 6, 7]
  tree = Tree.new
  items.each {|x| tree.insert(x)}
  tree.traverse {|x| print "#{x} "}
  print "\n"
  # Prints "1 2 3 4 5 6 7 "

infix

class Tree
 
  attr_accessor :left
  attr_accessor :right
  attr_accessor :data
  def initialize(x=nil)
    @left = nil
    @right = nil
    @data = x
  end
  def insert(x)
    list = []
    if @data == nil
      @data = x
    elsif @left == nil
      @left = Tree.new(x)
    elsif @right == nil
      @right = Tree.new(x)
    else
      list << @left
      list << @right
      loop do
        node = list.shift
        if node.left == nil
          node.insert(x)
          break
        else
          list << node.left
        end
        if node.right == nil
          node.insert(x)
          break
        else
          list << node.right
        end
      end
    end
  end
  def traverse()
    list = []
    yield @data
    list << @left if @left != nil
    list << @right if @right != nil
    loop do
      break if list.empty?
      node = list.shift
      yield node.data
      list << node.left if node.left != nil
      list << node.right if node.right != nil
    end
  end
  def insert(x)
    if @data == nil
      @data = x
    elsif x <= @data
      if @left == nil
        @left = Tree.new x
      else
        @left.insert x
      end
    else
      if @right == nil
        @right = Tree.new x
      else
        @right.insert x
      end
    end
  end
  def inorder()
    @left.inorder {|y| yield y} if @left != nil
    yield @data
    @right.inorder {|y| yield y} if @right != nil
  end
  def preorder()
    yield @data
    @left.preorder {|y| yield y} if @left != nil
    @right.preorder {|y| yield y} if @right != nil
  end
  def postorder()
    @left.postorder {|y| yield y} if @left != nil
    @right.postorder {|y| yield y} if @right != nil
    yield @data
  end
  def search(x)
    if self.data == x
      return self
    elsif x < self.data
      return left != nil ? left.search(x) : nil
    else
      return right != nil ? right.search(x) : nil
    end
  end
 
  def to_s
    "[" +
    if left then left.to_s + "," else "" end +
    data.inspect +
    if right then "," + right.to_s else "" end + "]"
  end
  def to_a
    temp = []
    temp << left.to_a if left
    temp << data
    temp << right.to_a if right
    temp
  end
  def infix()
    if @left != nil
      flag = %w[* / + -].include? @left.data
      yield "(" if flag
      @left.infix {|y| yield y}
      yield ")" if flag
    end
    yield @data
    if @right != nil
      flag = %w[* / + -].include? @right.data
      yield "(" if flag
      @right.infix {|y| yield y} if @right != nil
      yield ")" if flag
    end
  end
end
def addnode(nodes)
  node = nodes.shift
  tree = Tree.new node
  if %w[* / + -].include? node
    tree.left  = addnode nodes
    tree.right = addnode nodes
  end
  tree
end
 
prefix = %w[ * + 32 * 21 45 - 72 + 23 11 ]
tree = addnode prefix
str = ""
tree.infix {|x| str += x}
# str is now "(32+(21*45))*(72-(23+11))"

inorder / preorder / postorder

class Tree
 
  attr_accessor :left
  attr_accessor :right
  attr_accessor :data
  def initialize(x=nil)
    @left = nil
    @right = nil
    @data = x
  end
  def insert(x)
    list = []
    if @data == nil
      @data = x
    elsif @left == nil
      @left = Tree.new(x)
    elsif @right == nil
      @right = Tree.new(x)
    else
      list << @left
      list << @right
      loop do
        node = list.shift
        if node.left == nil
          node.insert(x)
          break
        else
          list << node.left
        end
        if node.right == nil
          node.insert(x)
          break
        else
          list << node.right
        end
      end
    end
  end
  def traverse()
    list = []
    yield @data
    list << @left if @left != nil
    list << @right if @right != nil
    loop do
      break if list.empty?
      node = list.shift
      yield node.data
      list << node.left if node.left != nil
      list << node.right if node.right != nil
    end
  end
  def insert(x)
    if @data == nil
      @data = x
    elsif x <= @data
      if @left == nil
        @left = Tree.new x
      else
        @left.insert x
      end
    else
      if @right == nil
        @right = Tree.new x
      else
        @right.insert x
      end
    end
  end
  def inorder()
    @left.inorder {|y| yield y} if @left != nil
    yield @data
    @right.inorder {|y| yield y} if @right != nil
  end
  def preorder()
    yield @data
    @left.preorder {|y| yield y} if @left != nil
    @right.preorder {|y| yield y} if @right != nil
  end
  def postorder()
    @left.postorder {|y| yield y} if @left != nil
    @right.postorder {|y| yield y} if @right != nil
    yield @data
  end
end
items = [50, 20, 80, 10, 30, 70, 90, 5, 14,
         28, 41, 66, 75, 88, 96]
tree = Tree.new
items.each {|x| tree.insert(x)}
tree.inorder {|x| print x, " "}
print "\n"
tree.preorder {|x| print x, " "}
print "\n"
tree.postorder {|x| print x, " "}
print "\n"

Loop through a tree

class Tree
  attr_reader :value
  def initialize(value)
    @value = value
    @children = []
  end
  def <<(value)
    subtree = Tree.new(value)
    @children << subtree
    return subtree
  end
  def each
    yield value
    @children.each do |child_node|
      child_node.each { |e| yield e }
    end
  end
end
t = Tree.new("Parent")
puts child1 = t << "Child 1"
puts child1 << "Grandchild 1.1"
puts child1 << "Grandchild 1.2"
puts child2 = t << "Child 2"
puts child2 << "Grandchild 2.1"
t.each { |x| puts x }
# Parent
# Child 1
# Grandchild 1.1
# Grandchild 1.2
# Child 2
# Grandchild 2.1

search a tree

class Tree
 
  attr_accessor :left
  attr_accessor :right
  attr_accessor :data
  def initialize(x=nil)
    @left = nil
    @right = nil
    @data = x
  end
  def insert(x)
    list = []
    if @data == nil
      @data = x
    elsif @left == nil
      @left = Tree.new(x)
    elsif @right == nil
      @right = Tree.new(x)
    else
      list << @left
      list << @right
      loop do
        node = list.shift
        if node.left == nil
          node.insert(x)
          break
        else
          list << node.left
        end
        if node.right == nil
          node.insert(x)
          break
        else
          list << node.right
        end
      end
    end
  end
  def traverse()
    list = []
    yield @data
    list << @left if @left != nil
    list << @right if @right != nil
    loop do
      break if list.empty?
      node = list.shift
      yield node.data
      list << node.left if node.left != nil
      list << node.right if node.right != nil
    end
  end
  def insert(x)
    if @data == nil
      @data = x
    elsif x <= @data
      if @left == nil
        @left = Tree.new x
      else
        @left.insert x
      end
    else
      if @right == nil
        @right = Tree.new x
      else
        @right.insert x
      end
    end
  end
  def inorder()
    @left.inorder {|y| yield y} if @left != nil
    yield @data
    @right.inorder {|y| yield y} if @right != nil
  end
  def preorder()
    yield @data
    @left.preorder {|y| yield y} if @left != nil
    @right.preorder {|y| yield y} if @right != nil
  end
  def postorder()
    @left.postorder {|y| yield y} if @left != nil
    @right.postorder {|y| yield y} if @right != nil
    yield @data
  end
  def search(x)
    if self.data == x
      return self
    elsif x < self.data
      return left != nil ? left.search(x) : nil
    else
      return right != nil ? right.search(x) : nil
    end
  end
end
keys = [50, 20, 80, 10, 30, 70, 90, 5, 14,
        28, 41, 66, 75, 88, 96]
tree = Tree.new
keys.each {|x| tree.insert(x)}
s1 = tree.search(75)   # Returns a reference to the node
                       # containing 75...
s2 = tree.search(100)  # Returns nil (not found)

to array

class Tree
  attr_accessor :left
  attr_accessor :right
  attr_accessor :data
  def initialize(x=nil)
    @left = nil
    @right = nil
    @data = x
  end
  def insert(x)
    list = []
    if @data == nil
      @data = x
    elsif @left == nil
      @left = Tree.new(x)
    elsif @right == nil
      @right = Tree.new(x)
    else
      list << @left
      list << @right
      loop do
        node = list.shift
        if node.left == nil
          node.insert(x)
          break
        else
          list << node.left
        end
        if node.right == nil
          node.insert(x)
          break
        else
          list << node.right
        end
      end
    end
  end
  def traverse()
    list = []
    yield @data
    list << @left if @left != nil
    list << @right if @right != nil
    loop do
      break if list.empty?
      node = list.shift
      yield node.data
      list << node.left if node.left != nil
      list << node.right if node.right != nil
    end
  end
  def insert(x)
    if @data == nil
      @data = x
    elsif x <= @data
      if @left == nil
        @left = Tree.new x
      else
        @left.insert x
      end
    else
      if @right == nil
        @right = Tree.new x
      else
        @right.insert x
      end
    end
  end
  def inorder()
    @left.inorder {|y| yield y} if @left != nil
    yield @data
    @right.inorder {|y| yield y} if @right != nil
  end
  def preorder()
    yield @data
    @left.preorder {|y| yield y} if @left != nil
    @right.preorder {|y| yield y} if @right != nil
  end
  def postorder()
    @left.postorder {|y| yield y} if @left != nil
    @right.postorder {|y| yield y} if @right != nil
    yield @data
  end
  def search(x)
    if self.data == x
      return self
    elsif x < self.data
      return left != nil ? left.search(x) : nil
    else
      return right != nil ? right.search(x) : nil
    end
  end
 
  def to_s
    "[" +
    if left then left.to_s + "," else "" end +
    data.inspect +
    if right then "," + right.to_s else "" end + "]"
  end
  def to_a
    temp = []
    temp << left.to_a if left
    temp << data
    temp << right.to_a if right
    temp
  end
end
items = %w[bongo grimace monoid jewel plover nexus synergy]
tree = Tree.new
items.each {|x| tree.insert x}
str = tree.to_s
# str is now:
# "bongo,grimace,jewel,monoid,nexus,plover,synergy"
arr = tree.to_a
# arr is now:
# ["bongo",["grimace",[["jewel"],"monoid",[["nexus"],"plover",
#  ["synergy"]]]]]

to string

class Tree
  attr_accessor :left
  attr_accessor :right
  attr_accessor :data
  def initialize(x=nil)
    @left = nil
    @right = nil
    @data = x
  end
  def insert(x)
    list = []
    if @data == nil
      @data = x
    elsif @left == nil
      @left = Tree.new(x)
    elsif @right == nil
      @right = Tree.new(x)
    else
      list << @left
      list << @right
      loop do
        node = list.shift
        if node.left == nil
          node.insert(x)
          break
        else
          list << node.left
        end
        if node.right == nil
          node.insert(x)
          break
        else
          list << node.right
        end
      end
    end
  end
  def traverse()
    list = []
    yield @data
    list << @left if @left != nil
    list << @right if @right != nil
    loop do
      break if list.empty?
      node = list.shift
      yield node.data
      list << node.left if node.left != nil
      list << node.right if node.right != nil
    end
  end
  def insert(x)
    if @data == nil
      @data = x
    elsif x <= @data
      if @left == nil
        @left = Tree.new x
      else
        @left.insert x
      end
    else
      if @right == nil
        @right = Tree.new x
      else
        @right.insert x
      end
    end
  end
  def inorder()
    @left.inorder {|y| yield y} if @left != nil
    yield @data
    @right.inorder {|y| yield y} if @right != nil
  end
  def preorder()
    yield @data
    @left.preorder {|y| yield y} if @left != nil
    @right.preorder {|y| yield y} if @right != nil
  end
  def postorder()
    @left.postorder {|y| yield y} if @left != nil
    @right.postorder {|y| yield y} if @right != nil
    yield @data
  end
  def search(x)
    if self.data == x
      return self
    elsif x < self.data
      return left != nil ? left.search(x) : nil
    else
      return right != nil ? right.search(x) : nil
    end
  end
 
  def to_s
    "[" +
    if left then left.to_s + "," else "" end +
    data.inspect +
    if right then "," + right.to_s else "" end + "]"
  end
  def to_a
    temp = []
    temp << left.to_a if left
    temp << data
    temp << right.to_a if right
    temp
  end
end
items = %w[bongo grimace monoid jewel plover nexus synergy]
tree = Tree.new
items.each {|x| tree.insert x}
str = tree.to_s
# str is now:
# "bongo,grimace,jewel,monoid,nexus,plover,synergy"
arr = tree.to_a
# arr is now:
# ["bongo",["grimace",[["jewel"],"monoid",[["nexus"],"plover",
#  ["synergy"]]]]]

Writing an Iterator Over a Data Structure

class Tree
  attr_reader :value
  def initialize(value)
    @value = value
    @children = []
  end
  def <<(value)
    subtree = Tree.new(value)
    @children << subtree
    return subtree
  end
end
t = Tree.new("Parent")
puts child1 = t << "Child 1"
puts child1 << "Grandchild 1.1"
puts child1 << "Grandchild 1.2"
puts child2 = t << "Child 2"
puts child2 << "Grandchild 2.1"

Личные инструменты

Поиск

Библиотеки

Языки

Другое

Навигация

Инструменты

Просмотры

Ruby/Collections/Your tree

Материал из Wiki.crossplatform.ru

Текущая версия на 17:55, 13 сентября 2010

Содержание

Create Your tree

infix

inorder / preorder / postorder

Loop through a tree

search a tree

to array

to string

Writing an Iterator Over a Data Structure