Perl教学第九篇关联数组(哈希表)

日期：2007年5月10日作者：查看:[大字体中字体小字体]

注：此处所说的树像上述链表一样是单向的，每个节点指向其子节点，但子节点并不指向父节点。
树的概念可以如下描述：

·因为每个子节点均为一个树，所以左/右子节点也称为左/右子树。（有时称左/右分支）
·第一个节点（不是任何节点的子节点的节点）称为树的根。
·没有孩子（子节点）的节点称为叶节点。
有多种使用关联数组实现树结构的方法，最好的一种应该是：给子节点分别加上left和right以访问之。例如，alphaleft和alpharight指向alpha的左右子节点。下面是用此方法创建二叉树并遍历的例程：

1 : #!/usr/local/bin/perl
2 :
3 : $rootname = "parent";
4 : %tree = ("parentleft", "child1",
5 : "parentright", "child2",
6 : "child1left", "grandchild1",
7 : "child1right", "grandchild2",
8 : "child2left", "grandchild3",
9 : "child2right", "grandchild4");
10: # traverse tree, printing its elements
11: &print_tree($rootname);
12:
13: sub print_tree {
14: local ($nodename) = @_;
15: local ($leftchildname, $rightchildname);
16:
17: $leftchildname = $nodename . "left";
18: $rightchildname = $nodename . "right";
19: if ($tree{$leftchildname} ne "") {
20: &print_tree($tree{$leftchildname});
21: }
22: print ("$nodename\n");
23: if ($tree{$rightchildname} ne "") {
24: &print_tree($tree{$rightchildname});
25: }
26: }
结果输出如下：

grandchild1
child1
grandchild2
parent
grandchild3
child2
grandchild4
注意函数print_tree()以次序“左子树、节点、右子树”来输出各节点的名字，这种遍历次序称为“左序遍历”。如果把第22行移到19行前，先输出节点明，再输出左子树、右子树，则为“中序遍历”，如果把第22行移到25行后，输出次序为左子树、右子树、节点，则为“右序遍历”。
可以用同样的方法，即连接字符串构成下标，来创建其它的数据结构，如数据库等。
进入讨论组讨论。

上一页 [1] [2] [3] [4] [5] [6]

上一篇:Perl教学第十篇格式化输出

下一篇:Perl教学第八篇子程序

Perl教学 第九篇 关联数组(哈希表)

Perl教学第九篇关联数组(哈希表)