class YmDataTree::Tree

Attributes

root[RW]

Public Class Methods

new() click to toggle source
# File lib/ym_data_tree.rb, line 6
def initialize
  @root = nil
  @in_order_traversal_datas = []
  @post_order_traversal_datas = []
  @pre_order_traversal_datas = []
end

Public Instance Methods

clear() click to toggle source
# File lib/ym_data_tree.rb, line 41
def clear
  @pre_order_traversal_datas = []
  @in_order_traversal_datas = []
  @post_order_traversal_datas = []
end
insert(data) click to toggle source
# File lib/ym_data_tree.rb, line 13
def insert(data)

  @tempNode = Node.new
  @tempNode.data = data
  if @root == nil
    @root = @tempNode
  else
    @current = @root
    @parent = nil
    status = true
    while status
      @parent = @current
      if data < @parent.data
        @current = @current.leftChild
        if @current == nil
          @parent.leftChild = @tempNode
          status = false
        end
      else
        @current = @current.rightChild
        if @current == nil
          @parent.rightChild = @tempNode
          status = false
        end
      end
    end
  end
end
traverse(node,*command) click to toggle source
# File lib/ym_data_tree.rb, line 46
def traverse(node,*command)
  clear
  if command.first.eql? :pre_order_traversal
    pre_order_traversal(node)
  elsif command.first.eql? :in_order_traversal
    in_order_traversal(node)
  elsif command.first.eql? :post_order_traversal
    post_order_traversal(node)
  elsif command.first.eql? :breadth_first_traversal
    breadth_first_traversal(node)
  elsif command.first.eql? :deep_first_traversal
    deep_first_traversal(self,command[1])
  else
    puts "Unknown Command"
  end
end

Private Instance Methods

breadth_first_traversal(node) click to toggle source
# File lib/ym_data_tree.rb, line 89
def breadth_first_traversal(node)
  if node != nil
      @ordered = [node]
      @quequ = []
      @datas = [node.data]
      count = 0
    while count < 2
      @ordered.each do |node|
        if node != nil
          if node.leftChild != nil
            @quequ.push(node.leftChild)
            @datas.push(node.leftChild.data)
          end
          if node.rightChild != nil
            @quequ.push(node.rightChild)
            @datas.push(node.rightChild.data)
          end
        end
      end
        @ordered = @quequ
        count += 1
      end
      @datas
    end
end
deep_first_traversal(tree,command) click to toggle source
# File lib/ym_data_tree.rb, line 114
def deep_first_traversal(tree,command)
    @datas = []
    @datas_left = []
    @datas_right = []
    node = tree.root
    if node != nil
      @left = node.leftChild
      @rigth = node.rightChild
      if command.eql? :pre_order_traversal
        @datas_left = tree.traverse(@left,command)
        @datas_right = tree.traverse(@rigth,command)
      elsif command.eql? :in_order_traversal
        @datas_left = tree.traverse(@left,command)
        @datas_right = tree.traverse(@rigth,command)
      elsif command.eql? :post_order_traversal
        @datas_left = tree.traverse(@left,command)
        @datas_right = tree.traverse(@rigth,command)
      end
      @datas_left.each{|data|  @datas.push(data)}
      @datas.push(node.data)
      @datas_right.each{|data| @datas.push(data)}
      @datas
    end
end
in_order_traversal(node) click to toggle source

PRIVATE METHODS

# File lib/ym_data_tree.rb, line 65
def in_order_traversal(node)
    if node != nil
     in_order_traversal(node.leftChild)
      @in_order_traversal_datas.push(node.data)
     in_order_traversal(node.rightChild)
    end
    @in_order_traversal_datas
end
post_order_traversal(node) click to toggle source
# File lib/ym_data_tree.rb, line 73
def post_order_traversal(node)
  if node != nil
      post_order_traversal(node.leftChild)
      post_order_traversal(node.rightChild)
      @post_order_traversal_datas.push(node.data)
  end
  @post_order_traversal_datas
end
pre_order_traversal(node) click to toggle source
# File lib/ym_data_tree.rb, line 81
def pre_order_traversal(node)
   if node != nil
     @pre_order_traversal_datas.push(node.data)
     pre_order_traversal(node.leftChild)
     pre_order_traversal(node.rightChild)
   end
   @pre_order_traversal_datas
end