木構造

[アルゴリズム,木構造]

練習のための問題は 競技プログラミングの履歴

木構造

• Wikipedia - 二分木
• 二分木クラスとその利用

  AOJの関連する問題

• 根付き木 - アルゴリズムとデータ構造 - Aizu Online Judge
• 二分木 - アルゴリズムとデータ構造 - Aizu Online Judge
• 木の巡回 - アルゴリズムとデータ構造 - Aizu Online Judge
• 木の復元 - アルゴリズムとデータ構造 - Aizu Online Judge

Rubyによる基本的な実装

#
# N = 木構造の接点(node)の個数
#

N = 15

#
# parent, left, right が必ず必要
# RubyならGenerics使わんでもよしなに処理してくれる, 残りの処理は自分で書く
#
Node = Struct.new(:parent, :left, :right)

t = Array.new(N) { Node.new }

# 根付き木 なら
def get_depth () ...
def get_children () ...

# 二分木 なら
def get_depth () ...
def get_height () ...
def get_sibling () ...

もしJavaだったら

• 総称型(Generics)を使わないとだめだろう

// ListとかArrayListとか
List<Node> t = new ArrayList<Node>();

  ALDS1_7_A

• 木構造の接点以下に複数の子ノードが存在する場合のコードを書く
  • 子ノードが node.left , node.right でどのように表現されるか把握すればそれほど難しくないかもしれない

用意した関数を紹介しておく

get_depth ( id, nodes )

その接点の深さを求める

get_children ( id, nodes )

その接点の直下の子ノードを求める

lines = <<'EOS'
4
0 0
1 3 2 3 0
2 0
3 0
EOS

#lines = $stdin.read
array = lines.split("\n")

N = array[0].to_i
Node = Struct.new(:parent, :left, :right)

nodes = Array.new(N) { Node.new }

def get_depth(id, nodes)
  d = 0
  while ! nodes[id].parent.nil? do
    id = nodes[id].parent
    d += 1
  end
  d
end

def get_children(id, nodes)
  children = []
  c = nodes[id].left
  while not c.nil?
    children << c
    c = nodes[c].right
  end
  children
end

for i in 1...(array.size)

  carray = array[i].split(" ")
  id = carray[0].to_i
  k  = carray[1].to_i
  c  = carray.slice(2, carray.length+1).map(&:to_i)

  # set parents for each children
  c.each do |child|
    nodes[child].parent = id
  end

  # set left node for this node
  nodes[id].left = c.first

  # set left/right nodes
  c.inject do |l, r|
    nodes[l].right = r
  end
end

nodes.each_with_index do |node, index|

  children = get_children(index, nodes)

  type = if node.parent.nil?
           "root"
         elsif children.empty?
           "leaf"
         else
           "internal node"
         end

  puts "node #{index}: parent = #{node.parent.nil? ? -1 : node.parent}, depth = #{get_depth(index, nodes)}, #{type}, #{children.to_s}"
end

  ALDS1_7_B

• 木構造の接点以下に２つ以下の子ノードしかない場合のコードを書く
  • 子ノードが node.left , node.right でどのように表現されるのは変わらないが、用意するべきメソッドが難しくて辛い

用意した関数を紹介しておく

get_depth ( id, nodes )

その接点の深さを求める

get_height ( id, nodes )

その接点の高さを求める、深さと逆のため再帰的にノードを求める必要がある(Finding height in Binary Search Tree)

get_sibling ( id, nodes )

その接点と同じ階層にあるノードを求める、二分木の場合隣接するものはあるかないか２択になる

#lines = <<'EOS'
# 4
# 1 0 -1
# 0 2 -1
# 2 3 -1
# 3 -1 -1
#EOS

lines = $stdin.read
array = lines.split("\n")

N = array[0].to_i
Node = Struct.new(:parent, :left, :right)

nodes = Array.new(N) { Node.new }

def get_depth(id, nodes)
  d = 0
  while ! nodes[id].parent.nil? do
    id = nodes[id].parent
    d += 1
  end
  d
end

def get_height(id, nodes)
  #
  # puts "id = #{id}, left = #{nodes[id].left}, right = #{nodes[id].right}"
  #
  return -1 if nodes[id].nil? or id == -1

  left_id  = nodes[id].left.nil? ? -1 : nodes[id].left
  right_id = nodes[id].right.nil? ? -1 : nodes[id].right

  lefth  = get_height(left_id, nodes)
  righth = get_height(right_id, nodes)

  height = if lefth > righth
             lefth + 1
           else
             righth + 1
           end
  height
end

def get_sibling(id, nodes)
  if nodes[id].parent.nil?
    -1
  else
    pid = nodes[id].parent
    p = nodes[pid]

    #puts "p.right => #{p.right.class}, p.left #{p.left.class}"

    if p.left.nil? and p.right.nil?
      -1
    else
      if p.right == id
        return p.left.nil? ? -1 : p.left
      end
      if p.left  == id
        return p.right.nil? ? -1 : p.right
      end
    end
  end
end

for i in 1...(array.size)
  carray = array[i].split(" ")
  id    = carray[0].to_i
  left  = carray[1].to_i
  right = carray[2].to_i

  # puts "id #{id}, left #{left}, right #{right}"

  # set parents for each children
  nodes[left].parent  = id if left  != -1
  nodes[right].parent = id if right != -1

  # set left/right nodes
  nodes[id].left  = left if left != -1
  nodes[id].right = right if right != -1
end

for index in 0...nodes.size

  node = nodes[index]
  parent  = node.parent.nil? ? -1 : node.parent
  depth   = get_depth(index, nodes)
  sibling = get_sibling(index, nodes)

  degree = 0
  degree += node.right.nil? ? 0 : 1
  degree += node.left.nil?  ? 0 : 1

  height  = get_height(index, nodes)

  type = if node.parent.nil?
           "root"
         elsif degree == 0
           "leaf"
         else
           "internal node"
         end

  puts "node #{index}: parent = #{parent}, sibling = #{sibling}, degree = #{degree}, depth = #{depth}, height = #{height}, #{type}"
end

# node 0: parent = -1, sibling = -1, degree = 2, depth = 0, height = 3, root
# node 1: parent = 0, sibling = 4, degree = 2, depth = 1, height = 1, internal node
# node 2: parent = 1, sibling = 3, degree = 0, depth = 2, height = 0, leaf
# node 3: parent = 1, sibling = 2, degree = 0, depth = 2, height = 0, leaf
# node 4: parent = 0, sibling = 1, degree = 2, depth = 1, height = 2, internal node
# node 5: parent = 4, sibling = 8, degree = 2, depth = 2, height = 1, internal node
# node 6: parent = 5, sibling = 7, degree = 0, depth = 3, height = 0, leaf
# node 7: parent = 5, sibling = 6, degree = 0, depth = 3, height = 0, leaf
# node 8: parent = 4, sibling = 5, degree = 0, depth = 2, height = 0, leaf

  ALDS1_7_C

• 根節点、左部分木、右部分木の順で節点の番号を出力する。これを木の先行順巡回 (preorder tree walk) と呼びます。
• 左部分木、根節点、右部分木の順で節点の番号を出力する。これを木の中間順巡回 (inorder tree walk) と呼びます。
• 左部分木、右部分木、根節点の順で節点の番号を出力する。これを木の後行順巡回 (postorder tree walk) と呼びます。

用意した関数を紹介しておく

pre_parse ( root, nodes )

根節点、左部分木、右部分木の順で節点の番号を出力する

in_parse ( root, nodes )

左部分木、根節点、右部分木の順で節点の番号を出力する

post_parse ( root, nodes )

左部分木、右部分木、根節点の順で節点の番号を出力する

#lines = <<'EOS'
#9
#0 1 4
#1 2 3
#2 -1 -1
#3 -1 -1
#4 5 8
#5 6 7
#6 -1 -1
#7 -1 -1
#8 -1 -1
#EOS
 
lines = $stdin.read
array = lines.split("\n")
 
N = array[0].to_i
Node = Struct.new(:parent, :left, :right)
 
nodes = Array.new(N) { Node.new }
 
for i in 1...(array.size)
  carray = array[i].split(" ")
  id    = carray[0].to_i
  left  = carray[1].to_i
  right = carray[2].to_i
 
  # puts "id #{id}, left #{left}, right #{right}"
 
  # set parents for each children
  nodes[left].parent  = id if left  != -1
  nodes[right].parent = id if right != -1
 
  # set left/right nodes
  nodes[id].left  = left if left != -1
  nodes[id].right = right if right != -1
end
 
def pre_parse(id, nodes)
  return if id.nil?
  print " #{id}"
  pre_parse(nodes[id].left, nodes)
  pre_parse(nodes[id].right, nodes)
end
 
def in_parse(id, nodes)
  return if id.nil?
  in_parse(nodes[id].left, nodes)
  print " #{id}"
  in_parse(nodes[id].right, nodes)
end
 
def post_parse(id, nodes)
  return if id.nil?
  post_parse(nodes[id].left, nodes)
  post_parse(nodes[id].right, nodes)
  print " #{id}"
end
 
root = 0
for i in 0...nodes.size
  root = i if nodes[i].parent.nil?
end
 
puts "Preorder"
pre_parse(root, nodes)
puts ""
 
puts "Inorder"
in_parse(root, nodes)
puts ""
 
puts "Postorder"
post_parse(root, nodes)
puts ""