我曾经说过，递归适合处理层次结构的数据，并举了文件系统的例子。但它作为数据结构的例子并不太合适，因为数据结构通常被认为应当放在内存中，而不是在磁盘上。

对于文件系统的情况，目录中包含了一系列文件，它的存在使得文件系统具有了树形结构。不论任何领域，只要一个元素包含了一系列的其他元素，就会出现树形结构。HTML数据就是个最好的例子。

HTML数据是一系列的元素和纯文本。每个元素包含一些内容，这些内容又是更多的元素和纯文本。这是个递归定义，与文件系统很相似。实际上，HTML文档的结构也跟文件系统结构十分相近。

元素由开始标签标记，如下：

<font>
			

相应地还要有结束标签，比如：

</font>
			

开始标签可以带有一些属性-值对，此时它是这个样子：

<font size=3 color="red">
			

但不论如何，结束标签永远不会改变。它没有任何属性-值对。

开始标签和结束标签之间可以是任何HTML文本系列，包括更多的元素和纯文本。下面是HTML文档的简单例子：

<h1>What Junior Said Next</h1>

<p>But I don’t <font size=3 color="red">want</font>
to go to bed now!</p>
			

文档结构如图 1.3 “HTML文档”所示。

图 1.3. HTML文档

主文档有三个部件：<h1>元素及其内容；<p>元素及其内容；还有它们之间的空白。接下来，<p>元素有三个组件：<font>元素前面不带标签的文本；<font>元素及其内容；还有<font>元素后面的不带标签的文本。<h1>元素只有一个组件，就是不带标签的文本What Junior Said Next。

在第八章[TODO]将会讨论怎样建立HTML等语言的解析器。同时，还会讨论一个半标准化模块HTML::TreeBuilder，它可以将HTML文档转换成树形结构。

假设HTML数据已经放在了名为$html的变量内。下述代码使用HTML::TreeBuilder将文本转换成明确的树形结构：

use HTML::TreeBuilder;
my $tree = HTML::TreeBuilder->new;
$tree->ignore_ignorable_whitespace(0);
$tree->parse($html);
$tree->eof();
			

ignore_ignorable_whitespace()方法指示HTML::TreeBuilder模块不允许忽略特定的空白，如<h1>元素后面的空行（通常状态下它会被忽略）。

现在$tree代表树形结构。它由散列组成，每个散列是树中的一个节点，表示一个元素。每个散列都有个名为_tag的键，值为标签名称；还有一个_content键，值为按顺序排列的元素内容一览；_content中的每个元素可能是表示无标签文本的字符串，也可能是表示另一个元素的散列。如果标签还带有属性-值对，就把它们直接保存在散列中，属性名作为散列的键，对应的属性做作为散列值。

比如，上述例子中的<font>元素对应的树结点如下所示：

{ _tag => "font",
  _content => [ "want" ],
  color => "red",
  size => 3,
}
			

包含<font>结点的<p>元素对应的树结点如下：

{ _tag => "p",
  _content => [ "But I don't ",
              { _tag => "font",
                _content => [ "want" ],
                color => "red",
                size => 3,
              },
              " to go to bed now!",
              ],
}
			

遍历这种HTML树并去掉所有标签的函数并不困难。对每个_content一览中的元素，通过ref()函数可以识别它是否为元素。ref()对于元素返回真（因为元素是散列引用），对于普通字符串返回假：

sub untag_html {
	my ($html) = @_;
	return $html unless ref $html; # It’s a plain string

	my $text = '';
	for my $item (@{$html->{_content}}) {
		$text .= untag_html($item);
	}

	return $text;
}
			

该函数检查传给它的HTML元素是否为普通字符串，如果是，函数就直接将它返回。如果不是普通字符串，该函数假设它是个树节点，并依次处理它的内容，递归地将每一项内容转换成纯文本，然后将结果字符串累加起来，再返回结果。上例的结果是：

What Junior Said Next But I don't want to go to bed now!
			

HTML::TreeBuilder的作者Sean Burke建议不要用这种方式访问HTML::TreeBuilder对象的内部，因为作者以后可能会改变内部结构。健壮的程序应该使用模块提供的存取方法（accessor method）。但在本例中，我们先继续使用直接访问内部的方式。

借鉴dir_walk()的经验，我们可以将这个函数分解成两部分：处理HTML树的部分，和负责组合纯文本的部分：

sub walk_html {
  my ($html, $textfunc, $elementfunc) = @_;
  return $textfunc->($html) unless ref $html; # It’s a plain string

  my @results;
  for my $item (@{$html->{_content}}) {
    push @results, walk_html($item, $textfunc, $elementfunc);
  }
  return $elementfunc->($html, @results);
}
			

这个函数的结构跟dir_walk()完全一样。它需要两个辅助函数作为参数：$text用来处理纯文本字符串，$elementfunc接收一个元素和它包含的项目的值，并计算该元素对应的值。$textfunc类似于dir_walk()中的$filefunc，而$elementfunc类似于$dirfunc。

现在，删除标签的程序可以这样写：

walk_html($tree, sub { $_[0] },
                 sub { shift; join '', @_ });
			

$textfunc的函数直接返回参数，不作任何修改。$elementfunc这个函数抛弃元素本身，然后把由内容计算而来的文本连接到一起并返回。输出结果与untag_html()相同。

如果需要一个总结文档的程序，显示出<h1>标签内的文本而忽略其他部分，可以这样写：

sub print_if_h1tag {
  my $element = shift;
  my $text = join '', @_;
  print $text if $element->{_tag} eq 'h1';
  return $text;
}
walk_html($tree, sub { $_[0] }, \&print_if_h1tag);
			

它与untag_html()基本相同，只是当处理元素的函数会在处理<h1>标签时，输出不带标签的文本。

如果想让函数返回标题内容，而不是显示出来，就得稍稍动点脑筋。考虑下面的例子：

<h1>Junior</h1>

Is a naughty boy.
			

我们应该忽略文本Is a naughty boy，不让它出现在结果中。但在walk_html()中，它只是个普通文本，跟我们不想忽略的Junior没有任何区别。似乎只需简单地抛弃非标题标签中的内容即可，但实际上并非如此：

<h1>The story of <b>Junior</b></h1>
			

我们不能只因为Junior出现在<b>内就忽略它，因为<b>标签本身还位于我们想要保留的<h1>中。

在每次调用walk_html()时将当前标签所处的上下文环境作为参数传递即可解决这个问题，但如果反方向传递信息的话，解决方式会更简单。根据文本是否能确定位于<h1>元素中，可以将文件中的每段文本划分为“保留”（KEEPER）和“可能保留”（MAYBE）两种。在处理<h1>元素时，就要将所有的“可能保留”元素提升为“保留”。最后，只需显示出“保留”，忽略“可能保留”即可：

@tagged_texts = walk_html($tree, sub { ['MAYBE', $_[0]] },
                                 \&promote_if_h1tag);

sub promote_if_h1tag {
  my $element = shift;
  if ($element->{_tag} eq 'h1') {
  	return ['KEEPER', join '', map {$_->[1]} @_];
  } else {
  	return @_;
  }
}
			

walk_html()的返回值是带有标记的文本一览。各个文本保存在匿名数组中，数组的第一个元素为MAYBE或KEEPER，第二个元素是字符串。处理纯文本的元素只负责将参数的文本标记为MAYBE。对于字符串Junior，它返回带有标记的['MAYBE', 'Junior']；对于字符串Is a naughty boy.，它返回['MAYBE', 'Is a naughty boy.']。

负责处理元素的函数更有意思。它接收一个元素，和一系列带有标记的文本。如果元素是<h1>，函数就从其余参数中提取出所有文本并连接在一起，再给结果加上KEEPER的标记。如果是其他元素，就直接返回其中的文本，不作任何改变。这些文本将作为标记文本的一部分，传递给处理上一层元素的元素处理函数。可以将它与第 1.5 节 “应用程序和目录遍历的各种形式”中的dir_walk()的最后那个例子，那个例子使用类似的方法返回文件名列表。

由于walk_html()的最终返回结果是一系列带有标签的文本，所以需要对其进行处理，抛弃那些仍标记为MAYBE的文本。这最后一步是不可避免的。这样，最顶层处理无标签文本的方式跟处理<h1>内文本的方式不同，所以必须有一段能够判断是否位于顶层的代码。因此，必须创建一个最终函数来处理顶层数据：

sub extract_headers {
  my $tree = shift;
  my @tagged_texts = walk_html($tree, sub { ['MAYBE', $_[0]] },
                                      \&promote_if_h1tag);
  my @keepers = grep { $_->[0] eq 'KEEPER'} @tagged_texts;
  my @keeper_text = map { $_->[1] } @keepers;
  my $header_text = join '', @keeper_text;
  return $header_text;
}
			

或者可以写得更紧凑些：

sub extract_headers {
  my $tree = shift;
  my @tagged_texts = walk_html($tree, sub { ['MAYBE', $_[0]] },
                                      \&promote_if_h1tag);
  join '', map { $_->[1] } grep { $_->[0] eq 'KEEPER'} @tagged_texts;
}
			

sub promote_if_h1tag {
  my $element = shift;
  if ($element->{_tag} =˜ /∧h\d+$/) {
    return ['KEEPER', join '', map {$_->[1]} @_];
  } else {
    return @_;
  }
}
				

sub promote_if {
  my $is_interesting = shift;
  my $element = shift;
  if ($is_interesting->($element->{_tag}) {
    return ['KEEPER', join '', map {$_->[1]} @_];
  } else {
    return @_;
  }
}
				

my @tagged_texts = walk_html($tree, sub { ['maybe', $_[0]] },
                                           \&promote_if_h1tag);
				

my @tagged_texts = walk_html($tree,
                              sub { ['maybe', $_[0]] },
                              sub { promote_if(
                                       sub { $_[0] eq 'h1'},
                                       $_[0])
                              });