【しばらく編集不可モードで運営します】 編集(管理者用) | 差分 | 新規作成 | 一覧 | RSS | FrontPage | 検索 | 更新履歴

Perlで木構造を扱う - リファレンスを使って

目次

リファレンスを使って

Perlの配列はフラットなので、ネストしたデータ構造を扱うのに苦労してます。

とりあえずデータをそれっぽく並べてみる。

 $creatures = ["生物",
                ["哺乳類",["鯨",["霊長類",["人","猿"]],"犬"]],
                ["魚類",["鯖","鯛","秋刀魚"]],
                ["両生類",["蛙"]]
              ];

深さ優先でトラバースしてみる。

 sub depth_first($$) {
   my $depth = shift;
   my $raList = shift;
 
   foreach (@{$raList}) {
     if (ref($_) eq "ARRAY") {
       depth_first($depth+1, $_);
     }
     else {
       print "> " x $depth, $_, "\n";
     }
   }
 }
 
 depth_first(0 , $creatures);

実行結果

 ~/src/Perl $ perl walk.pl
 生物
 > 哺乳類
 > > 鯨
 > > > 霊長類
 > > > > 人
 > > > > 猿
 > > 犬
 > 魚類
 > > 鯖
 > > 鯛
 > > 秋刀魚
 > 両生類
 > > 蛙

あれれれ?

なにかおかしい。そもそもの $creatures からして形が変なのではという気がする。

類の名称とそれに属すもの、をデータ化するルールができていないからうまくいかない んでは? 「配列にはメンバが並ぶ」、ことと、その親のメンバの関連付け、「親の次の参照が子」というルールが矛盾してるように思う。

あっ、そうか。

そこでした。ご指摘ではっきりしました。 木構造の要素は、Node(節点)とLeaf(端点)、それからNodeから子供への参照ですね。 このルール付けが明確になっていませんでした。

というルールにしてみると、

 $creatures = ["生物",
                ["哺乳類","鯨",["霊長類","人","猿"],"犬"],
                ["魚類","鯖","鯛","秋刀魚"],
                ["両生類","蛙"]
              ];

と若干シンプルになりました。

修正版 (2003-02-20: 少し汎用化)

 #!/usr/bin/perl
 $creatures = ["生物",
               ["哺乳類","鯨",["霊長類","人","猿"],"犬"],
               "カモノハシ",
               ["魚類","鯖","鯛","秋刀魚"],
               "イソギンチャク",
               ["両生類","蛙"]
              ];
 
 sub depth_first($$$$) {
   my ($ancestry, $tree, $do_node, $do_leaf) = @_;
 
   if (ref($tree) eq "ARRAY") {
     my @node = @$tree;
     my $value = $node[0];
     my @children = @node[1..$#node];
     $do_node->($ancestry, $value);
     map { depth_first([@$ancestry, $value], $_, $do_node, $do_leaf) } @children;
   }
   else {
     my $leaf = $tree;
     $do_leaf->($ancestry, $leaf);
   }
 }
 
 # Tree風
 depth_first([],
             $creatures,
             sub { print "  " x $#{$_[0]}, "+ $_[1]\n" },
             sub { print "  " x $#{$_[0]}, "- $_[1]\n" },
            );
 
 print "\n";
 
 # パン屑リスト風
 depth_first([],
             $creatures,
             sub { print join("", map { "[$_] - " } @{$_[0]}),
                         "[$_[1]]\n"
             },
             sub { print join("", map { "[$_] - " } @{$_[0]}),
                         "$_[1]\n"
             },
            );
 
 print "\n";
 
 # flatten にも使える
 @acc = ();
 depth_first([], $creatures, sub { push @acc, $_[1] }, sub { push @acc, $_[1] });
 print "@acc\n";
  

実行結果

 ~/src/Perl $ perl walk.pl
 + 生物
   + 哺乳類
     - 鯨
     + 霊長類
       - 人
       - 猿
     - 犬
   - カモノハシ
   + 魚類
     - 鯖
     - 鯛
     - 秋刀魚
   - イソギンチャク
   + 両生類
     - 蛙
 
 [生物]
 [生物] - [哺乳類]
 [生物] - [哺乳類] - 鯨
 [生物] - [哺乳類] - [霊長類]
 [生物] - [哺乳類] - [霊長類] - 人
 [生物] - [哺乳類] - [霊長類] - 猿
 [生物] - [哺乳類] - 犬
 [生物] - カモノハシ
 [生物] - [魚類]
 [生物] - [魚類] - 鯖
 [生物] - [魚類] - 鯛
 [生物] - [魚類] - 秋刀魚
 [生物] - イソギンチャク
 [生物] - [両生類]
 [生物] - [両生類] - 蛙

 生物 哺乳類 鯨 霊長類 人 猿 犬 カモノハシ 魚類 鯖 鯛 秋刀魚 イソギンチャク 両生類 蛙

参照

perlのデータ構造クックブック
http://www.att.or.jp/perl/pdsc/indexj.html