赵县小程序制作【赵县企业邮箱】赵县网站外包、赵县微信商城开发、赵县网店美工、赵县淘宝设计

赵县小程序制作【赵县企业邮箱】赵县网站外包、赵县微信商城开发、赵县网店美工、赵县淘宝设计

赵县，隶属于河北省石家庄市，古称赵州，地处石家庄市区东南40公里，总面积为675平方公里，总人口61.3万（2017年），辖11个乡镇、281个行政村。县府驻赵州镇。汉为平棘县，晋为赵国，北魏置赵郡，曾为赵州治，隋改为赵州。1913年改为赵县。赵县历史悠久，文物众多，共有文物保护单位21处。

县境位于河北平原，光热充足，地下水丰富，利于井灌，又有石津渠灌溉之利，一年四季分明，春秋两季时间短，夏冬两季时间长。东部为沙质褐土，适于雪花梨生长。赵县农业发达，玉米、小麦是主要粮食产品。特产雪花梨俗称象牙梨，个大，皮薄、汁多、含糖分高，成熟后洁白如雪，故名，是河北省大宗出口的优质水果之一。

2018年12月27日，经河北省人民政府研究，同意灵寿县、赵县、阳原县县城为河北省园林县城。 [1]  2019年3月，被列为第一批革命文物保护利用片区分县名单。

9.4.3　用于形成分支的数据结构

如果非正式地考虑9.4.2节中描述的算法，我们需要能迅速完成以下两项工作：

1. 给定某节点，找出其当前所在分支；

2. 将两个分支合并为一个分支。

有很多种数据结构可以支持这些操作。我们将研究一种简单却又能带来极佳性能的想法。关键在于将每个分支中的节点都放进一棵树中。2分支是由树的根表示的。上述两项操作现在可以按照如下方式实现。

2请务必理解，在接下来的内容中，“树”和“图”指的是不同的结构。图的节点与树的节点间存在一一对应，也就是说，每个树节点都表示一个图节点。不过，树中父子节点之间的边并不一定是图中存在的边。

1. 要找到图中节点的分支，就要找到该节点在树中的代表，然后沿着树中的路径到达表示该分支的根节点。

2. 要合并两个不同的分支，我们就要让一个分支的根节点成为另一分支根节点的子节点。

示例 9.15

我们遵循示例9.14介绍的步骤，展示按照特定步骤创建的树。首先，每个节点本身都是一棵单节点树。而第一条边{卡内奥赫，檀香山}会让我们把两棵单节点树{卡内奥赫}和{檀香山}合并为一棵双节点树{卡内奥赫，檀香山}。任何一个节点都可以作为另一个的子节点。不过在这里假设檀香山是根节点卡内奥赫的子节点。

同样，第二条边{瓦西阿瓦，珍珠城}合并了两棵单节点树，而且可以假设珍珠城是根节点瓦西阿瓦的子节点。至此，当前的分支集合可以用图9-15所示的两棵树以及9棵单节点树来表示。

图 9-15　合并分支得到的前两棵重要的树

第三条边{珍珠城，檀香山}合并了这两个分支。假设瓦西阿瓦是另一个根节点卡内奥赫的子节点。那么得到的分支就可以用图9-16中的树表示。

图 9-16　表示含4个节点的分支的树

当考虑第四条边{瓦西阿瓦，迈里}时，就要把迈里合并到用图9-16中的树表示的分支中。既可以把迈里作为卡内奥赫的子节点，也可以将卡内奥赫当作迈里的子节点。不过这里选择前者，因为这样可以让树的高度保持比较小的值，而让大分支的根节点作为小分支根节点的子节点会让树中的路径变得更长。在确定节点的分支时，长路径会让我们要花更多时间才能沿着路径到达根节点。通过遵循这样的策略，并在分支高度相同时作出任意觉得，我们可能得到图9-17中表示3条最终连通分支的3棵树。

图 9-17　使用树合并算法表示最终连通分支的树

遵循示例9.15中的经验，我们制订了这样的策略，在合并两棵树时，高度较小的根节点要成为高度较大的根节点的子节点。如果出现高度相等的情况就任选一种方式。从这一策略中得到的重要收获就是树的高度只能以树中节点数对数的速度增长，而且在实践中，树的高度往往还更小。因此，当沿着一条路径从树的节点到达其根节点时，所花的时间最多与树中节点数的对数成比例。我们可以通过对高度h 的归纳证明如下命题，从而得出这一对数边界。

命题S(h)。按照将较低高度合并到较高高度的策略形成的高度h 的树，至少有2h个节点。

依据。依据是h=0。这样的树肯定只有一个节点，而且因为20=1，所以命题S(0)成立。

归纳。假设S(h)对某个h≥0成立，并考虑高度为h+1的树T。在通过合并形成T 的过程中的某个时刻，树的高度第一次达到h+1。让树的高度达到h+1的唯一方式就是让某高度为h 的树T1的根节点成为某树T2根节点的子节点。T 是T1加上T2，可能还要加上一些后来要加上的其他节点，如图9-18所示。

图 9-18　形成高度为h+1的树

现在，根据归纳假设，T1至少有2h个节点。因为它的根节点成为了T2根节点的子节点，所以T2的高度也至少是h。因此，T2也至少有2h个节点。T是T1加上T2，可能还有更多节点组成的，所以T 至少有2h+2h=2h+1个节点。这就是S(h+1)，所以我们证明了归纳步骤。

现在就知道了，如果一棵树有n 个节点且高度为h，那么肯定有n≥2h。如果在两边取对数，就得到log2n≥h，也就是说，树的高度不可能大于节点数的对数。这样一来，当我们沿着任意路径从节点到达树的根节点时，都要花O(logn)的时间。

现在要更详细地描述实现这些想法的数据结构。首先，假设用NODE类型来表示节点。就像以前那样，我们假设NODE的类型为int，而且MAX至少是图中所含节点的数量。对图9-4中的例子而言，要设MAX为13。

还要假设由EDGE类型的单元组成的链表edges，这些单元是由如下声明定义的

typedef struct EDGE *EDGELIST;struct EDGE {
    NODE node1, node2;
    EDGELIST next;};复制代码

最后，对图中的每个节点而言，还需要一个与之对应的树节点。树节点是TREENODE类型的结构体，由以下内容组成。

1. 父指针，让我们能在该图的节点上构建树，并沿着树到达其根节点。父指针为NULL就标识该节点为根节点。

2. 以给定节点为根节点的树的高度。只有该节点是根节点时才使用该高度。

因此可以将TREENODE类型定义为：

typedef struct TREENODE *TREE;struct TREENODE {
    int height;
    TREE parent;}:复制代码

我们还要定义数组

TREE nodes[MAX];复制代码

以便将每个图节点与树中某个节点关联起来。应当明白，数组nodes中的每一项都是指向树中节点的指针，而该数据项也是图中节点的唯一代表。

图9-19展示了两个重要的辅助函数。第一个是find，它接受节点a，取指向其对应树节点x 的指针，沿着x 的父指针及其祖先向上，直到到达根节点。这种对根节点的搜索是由第(2)行和第(3)行执行的。如果找到了根节点，就会在第(4)行返回指向该根节点的指针。请注意，在第(1)行，NODE类型一定是int，这样才能用它来作为nodes数组的索引。

      /* 返回树的根节点位置，该位置含有对应
         图节点a的树节点x */
      TREE find(NODE a, TREE nodes[]);
      {
          TREE x;

 (1)      x = nodes[a];
 (2)      while (x->parent != NULL)
 (3)          x = x->parent;
 (4)      return x;
      }


      /* 让根节点较低的树成为根节点较高的树的子树，
         从而将根节点分别
         为x和y的树合并为一棵树 */
      void merge(TREE x, TREE y)
      {
          TREE higher, lower;

 (5)      if (x->height > y->height) {
 (6)          higher = x;
 (7)          lower = y;
          }
          else {
 (8)          higher = y;
 (9)          lower = x;
          }(10)      lower->parent = higher;(11)      if (lower->height == higher->height)(12)          ++(higher->height);
      }复制代码

图 9-19　辅助函数find和merge

第二个函数是merge，3它接受指向两个树节点的指针x 和y，要让函数正常工作，它们一定是需要合并的两棵树的根节点。第(5)行的测试确定了哪个根节点的高度更大，如果相等就直接选择y。在第(6)行至第(7)行或第(8)行至第(9)行，会根据具体的情况将较高的根节点赋值给局部变量higher，而较低的根节点则被赋值给局部变量lower。接着在第(10)行较低的根节点会成为较高根节点的子节点，而在第(11)行和第(12)行，如果T1和T2的高度相等，较高根节点（也就是现在合成的树的根节点）的高度要增加1。较低根节点的高度保持不变，不过现在这个值已经没有意义了，因为较低根节点现在已经不再是根节点了。

赵县小程序制作【赵县企业邮箱】赵县网站外包、赵县微信商城开发、赵县网店美工、赵县淘宝设计