馆陶网站推广【馆陶办理400电话】馆陶SEO优化、馆陶微信公众号APP客户端小程序开发、馆陶网站托管、馆陶APP开发

馆陶网站推广【馆陶办理400电话】馆陶SEO优化、馆陶微信公众号APP客户端小程序开发、馆陶网站托管、馆陶APP开发

馆陶县，河北省邯郸市下辖县 [1]  ，地处河北省东南部，以卫运河为界与山东省冠县、临清市毗邻。全县辖4镇4乡277个行政村，总面积456平方公里，其中耕地面积48万亩，总人口36万人。馆陶是千年古县，赵王“在城（今冠县东古城）西北七里陶丘侧置馆，故名馆陶”，自西汉初置县，已有2200多年历史。

馆陶县先后荣获中国蛋鸡之乡、中国黑陶艺术之乡 、中国粮画之乡、中国轻工轴承之乡、中国黄瓜之乡、中国漆画艺术之乡、全国休闲农业和乡村旅游示范县、全国电子商务进农村示范县、全国义务教育发展基本均衡县、全国中医工作先进县、全国群众体育工作先进县等等30余项国家级殊荣。

近年来，馆陶县着力打造了五张名片。一是“最大”，禽蛋交易市场金凤市场，单体全国最大，鸡蛋远销广东、广西等地，2016年交易额达到110亿元；二是“最优”，馆陶是中国著名的黑陶艺术之乡，现代黑陶艺术经过馆陶人的继承和创新，达1000多个品种；三是“最好”，馆陶是中国唯一的黄瓜之乡，馆青牌黄瓜，连续四年荣获中国绿色博览会金奖；四是“最佳”，馆陶有独一无二的富含三价有机铬的黑小麦，可应用于抑制血糖和抗肿瘤等医学领域；五是“最美”，粮画小镇被评为“中国十大最美乡村”，即将由3A级景区升级成为国家4A级旅游景区。 [2-6] 

2020年4月，被河北省体育局评选为“2019年度体育工作最佳县（市、区）”。

5.3　树的数据结构

很多数据结构可用来表示树。应该选用哪种数据结构，取决于想要执行的特定操作。举个简单的例子，如果想要做的只是定位节点的父节点，那么可以用由标号组成的结构体，加上指向表示节点之父节点的结构体的指针来表示每个节点。

作为一般规则，树的节点可以用结构体表示，这些结构体中的字段以某种方式将节点链接在一起，这种链接方式与节点在抽象的树中的连接方式类似，而树本身则可由指向表示根节点的结构体的指针来表示。因此，在谈到对树的表示时，我们主要是对节点的表示方式感兴趣。

表示方式的一种差异体现在表示节点的结构体在计算机内存中的位置上。在C语言中，可以使用标准库stdlib.h中的malloc函数为表示节点的结构体创建空间，这种情况下，节点都“漂泊”在内存中，并只能通过指针来访问。此外，可以创建由结构体组成的数组，并用数组中的元素来表示节点。这里节点还是根据它们在树中的位置链接起来的，不过也可以沿着数组的顺序来访问这些节点。因此，可以不沿着树中的路径来访问节点。基于数组的表示方式的弊端，在于没办法创建一棵节点数超过数组所含元素数量的树。接着，我们会假设这些节点都是由malloc创建的，虽然在树的大小有限制的情况下，由相同类型的结构体组成数组是可行的，而且有可能是首选方案。

5.3.1　树的指针数组表示

表示树的最简单方式之一就是为每个节点使用一个由表示节点标号的字段组成的结构体，后面再跟上指向该节点子节点的指针组成的数组。图5-6就表示了这样的结构。常量bf 是该指针数组的大小，它表示节点可以具有的最大子节点数，这个量就是分支系数（branching factor）。某节点对应数组的第i 个位置含有指向该节点第i 个子节点的指针，不存在的子节点可用NULL指针表示。

图 5-6　用指针数组表示的节点

在C语言中，该数据结构可以用如下类型声明来表示。

typedef struct NODE *pNODE;struct NODE {
    int info;
    pNODE children[BF];};复制代码

在这里，字段info表示构成节点标号的信息，而BF则表示分支系数的常量。在本章中我们还将看到该声明的多个变种。

在这种表示树的数据结构和多数表示树的数据结构中，都将树表示为指向根节点的指针。因此，pNODE还是树的类型。其实，可以在pNODE的位置使用类型TREE，而且在5.6节开始介绍二叉树时，我们将采纳这一约定。不过，现在还是要使用pNODE这个名称代表“指向节点的指针”类型，因为在某些数据结构中，指向节点的指针除了表示树之外还用于其他用途。

指针数组表示使我们能在O(1)的时间内访问任意节点的第i 个子节点。然而，当树中只有少量节点有很多子节点时，这种表示会非常浪费空间。在这种情况下，数组中的多数指针都是NULL。

试着记住trie

术语trie（单词查找树）来源于单词retrieval（检索）的中间部分。它本来被人们读作tree，好在现在常见读法已经将其读为发音有区别的try了。

示例 5.10

树可以用来表示一系列单词，其表示方式可以使检查给定字符序列是否为存在的单词变得非常有效率。在这类称为单词查找树的树中，除了根节点之外，每个节点都有与之相关联的字母。由某个节点n 表示的字符串，就是从根节点到n 的路径上的字母序列。给定一组单词，单词查找树的节点就是那些表示该集合中某个单词的前缀的字符串。节点的标号是由表示该节点的字母，以及表明从根节点到该节点的字母串能否构成完整单词的布尔值组成的。如果能，就用布尔值1表示，如果不能，就用0表示。1

1在5.2节中，介绍过的标号都只有一个值。不过，值可以是任意类型的，而且标号可以是由两个或多个字段组成的结构体。在本例中，标号有一个字段是个字母，而第二个字段则是一个值要么为0要么为1的整数。

例如，假设我们的“字典”是由4个单词he、hers、his和she组成的。这些单词的单词查找树如图5-7所示。要确定单词he是否在集合中，可以从根节点n1开始，移动到标号为h的子节点n2，再从节点n2移动到标号为e的子节点n4。因为这些节点都出现在树中，而且n4的标号中还有1，所以可以得出he在该集合中的结论。

图 5-7　单词he、hers、his和she的单词查找树

再举一个例子，假设想要确定him是否在该集合中。可以从根节点开始沿着路径移动到n2，再移动到n5，这是表示前缀hi的。不过在节点n5处找不到对应字母m的子节点。所以可以得出him不在该集合中的结论。最后，如果查找单词her，那么可以找出从根节点到节点n7的路径。该节点存在，但标号不含1。因此可以得出her不在该集合中的结论，虽然以它为真前缀的单词hers在该集合中。

单词查找树中众节点的分支系数就等于构成这些单词的字母表中不同字符的数目。例如，如果不区分大小写字母，而且单词中不含撇号这样的特殊字符，那么分支系数就等于26。包含两个标号字段的节点的类型可以按照图5-8中所示的方式定义。在数组children中，可以假设字母a是用下标0表示的，而下标1表示字母b，以此类推。

typedef struct NODE *pNODE;struct NODE {
    char letter;
    int isWord;
    pNODE children[BF];};复制代码

图 5-8　字母单词查找树的定义

图5-7中抽象形式的单词查找树可以用图5-9所示的数据结构表示。通过展示前两个字段letter和isWord，以及数组children中那些具有非NULL指针的元素，从而表示节点。在children数组中，对每个非NULL的元素，标记该数组的字母是由指向子节点的指针上方的项表示的，不过该字母实际上没有出现在该结构中。请注意，根节点的letter字段是无关紧要的。

图 5-9　图5-7中所示单词查找树的数据结构

5.3.2　树的最左子节点右兄弟节点表示

使用指针数组表示节点的空间利用率可能很低，因为通常情况下，绝大多数指针都会是NULL。图5-9显然就是这种情况，其中没有哪个节点有两个以上非NULL指针。事实上，如果想想这种情况，就会发现，在任何基于26个字母的字母表的单词查找树中，指针的数量都会是表示节点的指针的数量的26倍。因为没有哪个节点会有两个父节点，而且根节点是没有父节点的，所以N个节点中只有N-1个非NULL的指针，也就是说，每26个指针中只有不到1个是有用的。

要克服树的指针数组表示空间利用率低的问题，方法之一就是使用链表来表示节点的子节点。节点对应链表所占据的空间是与该节点子节点的数量成正比的。不过，这种表示方式在时间上要付出代价，访问第i 个子节点所需时间为O(i )，因为在到达第i 个节点之前必须遍历长度为i-1的链表。与之相比，使用指针数组表示子节点的话，就可以在O(1)时间内到达第i 个子节点，跟i 完全没有关系。

在树的这种最左子节点右兄弟节点（leftmost-child-right-sibling）表示中，要为每个节点放入一个指向其最左子节点的指针，而节点没有指向它其他子节点的指针。要找到节点n 的第二个及后续的子节点，可以为这些节点创建一个链表，其中每个子节点c 都指向n 的子节点中紧挨在c 右侧的那个，该节点称为c 的右兄弟节点。

示例 5.11

在图5-1中，n3是n2的右兄弟节点，n4是n3的右兄弟节点，n4没有右兄弟节点。沿着n1指向其最左子节点n2的指针，然后移到指向n2右兄弟节点n3的指针，接着再到指向n3右兄弟节点n4的指针，就能找出n1的子节点。接着就会发现一个为NULL的右兄弟节点指针，并知道n1没有更多子节点了。

图5-10简要绘出了图5-1所示树的最左子节点右兄弟节点表示。向下的箭头是指最左子节点链接，而向右的箭头则是右兄弟节点链接。

图 5-10　图5-1中所示树的最左子节点右兄弟节点表示

在树的最左子节点右兄弟节点表示中，节点是按照如下方式定义的。

typedef struct NODE *pNODE;struct NODE {
    int info;
    pNODE leftmostChild, rightSibling;};复制代码

info字段存放着与节点相关联的标号，而且可以是任一类型的。字段leftmostChild和rightSibling指向最左子节点以及相应的右兄弟节点。请注意，尽管leftmostChild给出了有关该节点自身的信息，但节点的rightSibling字段才是真正表示该节点父节点全部子节点的链表的那一部分。

示例 5.12

现在将图5-7中的单词查找树表示成最左子节点右兄弟节点的形式。首先，节点的类型如下。

typedef struct NODE *pNODE;struct NODE {
    char letter;
    int isWord;
    pNODE leftmostChild, rightSibling;};复制代码

根据示例5.10中描述过的模式，前两个字段是表示信息的。图5-7中的单词查找树可表示为图5-11所示的数据结构。请注意，每个叶子节点都有为NULL的最左子节点指针，而每个最右子节点都有为NULL的右兄弟节点指针。

图 5-11　所示单词查找树的最左子节点右兄弟节点表示

举个与最左子节点右兄弟节点表示的用途有关的例子。在图5-12中，函数seek(let,n)会接受字母let 以及指向节点n 的指针作为参数。它会返回一个指针，指向n 的子节点中letter字段里有let 的那个子节点，如果不存在这样的节点，返回的就是NULL指针。如果发现let，或是检查过所有的子节点，就会达到第(6)行，并跳出该循环。不管是哪种情况，c都存放着正确的值，如果存在存放了let 的子节点，就是指向该节点的指针，如果不存在，就是NULL指针。

请注意，seek函数的运行时间与找到所要找的子节点所必须检查的子节点数成正比，如果根本找不着这样的节点，那么运行时间就与节点n的子节点数成正比。与之相比的是，如果使用树的指针数组表示，seek会直接返回字母let对应的数组元素的值，花的时间为O(1)。

     pNODE seek(char let, pNODE n)
     {(1)      c = n->leftmostChild;(2)      while (c != NULL)(3)          if (c->letter == let)(4)              break;
             else(5)              c = c->rightSibling;(6)      return c;
     }复制代码

图 5-12　找到所需字母对应的子节点

馆陶网站推广【馆陶办理400电话】馆陶SEO优化、馆陶微信公众号APP客户端小程序开发、馆陶网站托管、馆陶APP开发