馆陶400电话申请开通【馆陶企业网站建设】馆陶微信公众号小程序开发运营价格、馆陶微信公众号APP软件客户端设计运营、馆陶网页页面设计公司费用、馆陶公司网站制作方案流程改版维护大概需要多少钱

馆陶400电话申请开通【馆陶企业网站建设】馆陶微信公众号小程序开发运营价格、馆陶微信公众号APP软件客户端设计运营、馆陶网页页面设计公司费用、馆陶公司网站制作方案流程改版维护大概需要多少钱

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

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

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

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

对二叉树进行结构归纳

与普通树一样，结构归纳法也适用于二叉树。其实还可以使用更简单的模式，这种模式下的依据是空树。下面就是对这一技巧的总结。

1. 指定要证明的命题S(T )，其中T 是一棵二叉树。

2. 证明依据，即证明若T 是空树，则S(T )为真。

3. 设T 是以r 为根节点，并以TL 和TR 为子树的二叉树，以此构建归纳步骤。声明假定有归纳假设，即S(TL)和S(TR)为真。

4. 在(3)中提到的假设下证明S(T )为真。

5.7　二叉查找树

各种计算机程序中有一种同样的活动，就是维护这样一组值，用户希望：

1. 向这组值中插入元素；

2. 从这组值中删除元素；

3. 查找某元素，看看它是否在这组值中。例子之一是英语词典，我们时不时地会往里面插入一些新单词，比如fax；删除一些不再使用的单词，比如aegilops；或者是要查找一串字母，看看其是否为单词，例如，这是拼写检查器程序的一部分。

因为这个例子是我们非常熟悉的，所以不管其具体用途是什么，只要是可以按照上述定义对其执行插入、删除和查找操作的一组值，都叫作词典。再举个词典的例子，某教授可能要记录选修某课程学生的花名册。偶尔会有学生被加入这门课程（插入），或是退出该课程（删除），或是需要弄清某个学生是否选修了该课程（查找）。

二叉查找树这种带标号的二叉树是实现词典的一个好方法。假设节点的标号是按照“小于”顺序（我们会将其写作<）从一组值中选出的。例子包括具有一般小于顺序的实数或整数，或是有着用<表示的词典顺序或字母表顺序的字符串。

二叉查找树（Binary Search Tree，BST）是一种带标号的的二叉树，以下属性对这种二叉树的每个节点x 都成立：x 的左子树中所有节点的标号都小于x 的标号，而其右子树中所有节点的标号都大于x 的标号。这种属性被称为二叉查找树属性。

示例 5.22

图5-33展示了对应着集合｛Hairy，Bashful，Grumpy，Sleepy，Sleazy，Happy｝的二叉查找树，其中<顺序是词典顺序。请注意，根节点左子树在词典顺序上都小于Hairy，而右子树在字典顺序上都大于它。这一属性对该树中的每个节点都成立。

图 5-33　具有6个带字符串标号的节点的二叉查找树

5.7.1　用二叉查找树实现词典

我们可以将二叉查找树表示为任何带标号的二叉树。例如，可以按如下形式定义NODE类型。

typedef struct NODE *TREE;struct NODE {
    ETYPE element;
    TREE leftChild, rightChild;};复制代码

二叉查找树被表示为指向二叉查找树根节点的指针。元素的类型ETYPE应该得到合理的设置。在本章所有的程序中，都将假设ETYPE为int类型，从而使元素间的比较可以直接用算术比较运算符<、==和>完成。在涉及词典顺序比较的例子中，可以假设程序中的比较由诸如2.2节中讨论过的lt、eq 和gt 这样的比较函数完成。

5.7.2　二叉查找树中元素的查找

假设想在由二叉查找树T 表示的某词典中查找某个元素x。如果将x 与T 的根节点处的元素加以比较，就可以利用二叉查找树属性快速找到x，或确定x 没有出现。如果x 在根节点处，就完成了查找。否则，如果x 比根节点处的元素小，x 就只可能在左子树中被找到（根据二叉查找树属性），而如果x 比根节点处的元素大，x 就只可能出现在右子树中（还是因为二叉查找树属性）。也就是说，可以通过以下递归算法表示查找操作。

依据。如果树T 是空树，那么x 未出现。如果树T 非空，而且x 在根节点，那么x 就出现了。

归纳。如果T 非空而x 未在根节点位置，设y 是T 根节点处的元素。如果x< y，则只在根节点的左子树中查找x；如果x>y，则只在y 的右子树中查找x。二叉查找树属性保证x 不可能出现在没有查找的那棵子树中。

抽象数据类型

诸如插入、删除和查找这种可能对一组对象或特定类别执行的一系列操作，有时称为抽象数据类型或ADT。这一概念也会被称为类或模块。我们将在第7章中研究若干抽象数据类型，而在本章中，我们会看到其中一个：优先级队列。

ADT可以有多种抽象实现。例如，在本节中可看到二叉查找树是一种实现词典ADT的好方法。表是另一种看似可靠实则经常效率低下的实现词典ADT的方式。7.6节将介绍散列，另一种不错的词典实现方式。

每种抽象实现依次可通过若干种不同的数据类型来具体实现。举例来说，可以使用二叉树的左子节点右子节点实现作为实现二叉查找树的数据结构。这一数据结构，加上用于插入、删除和查找的恰当函数，就成了词典ADT的一种实现。

在程序中使用ADT的一个重要原因是，ADT底层的数据只能通过ADT的操作（比如插入）来访问。这一限制是防御性编程的一种形式，可以防止操作数据的函数以意料之外的方式对数据进行偶发变更。使用ADT的第二个重要原因在于，ADT让我们可以重新设计数据结构和实现其操作的函数，在不担心会为程序其余部分引入错误的前提下，这样可能提高操作的效率。如果只有用于ADT操作的接口函数被正确地重写，就不会出现新的错误。

示例 5.23

假设想要在图5-33的二叉查找树中查找Grumpy。将Grumpy与根节点处的Hairy相比较，发现Grumpy在词典顺序上要先于Hairy，因此要对左子树调用lookup。

左子树的根节点是Bashful，而将该标号与Grumpy相比，发现前者要先于后者。因此要对Bashful的右子树递归地调用lookup。现在发现Grumpy在这一子树的根节点处，并返回TRUE。这些步骤是由具有图5-34模式的词典顺序比较函数执行的。

     BOOLEAN lookup(ETYPE x, TREE T)
     {(1)      if (T == NULL)(2)          return FALSE;(3)      else if (x == T->element)(4)          return TRUE;(5)      else if (x < T->element)(6)          return lookup(x, T->leftChild);
         else /* x 一定是大于T->element */(7)          return lookup(x, T->rightChild);
     }复制代码

图 5-34　如果x 在T 中，函数lookup(x,T)会返回TRUE，否则返回FALSE

更具体地讲，图5-34中的递归函数lookup(x,T)使用左子节点右子节点数据结构实现了这一算法。请注意，lookup返回的是BOOLEAN类型的值，这一类型实际上与int相同，不过它定义的值只有TRUE和FALSE，分别定义为1和0。BOOLEAN类型是在1.6节中引入的。此外，请注意，这里的lookup函数只接受能由=、<等运算符比较的类型。如果要让它处理示例5.23中用到的字符串那样的数据，就需要重写。

在第(1)行，lookup会确定T 是否为空。如果不为空，那么lookup在第(3)行会确定x 是否存储在当前节点。如果x 不在该节点，那么lookup就会根据x 是小于还是大于当前节点存储的元素，递归地查找左子树或右子树。

5.7.3　二叉查找树元素的插入

向二叉查找树T 中增加一个新元素x 是很简单的，以下递归算法简要描述了处理思路。

依据。如果T 是空树，用一棵由单个节点构成的树替代T，并在该节点处放上x。如果T 非空而且其根节点处有元素x，那么x 已经在字典中，不需要再做任何事情。

归纳。如果T 非空，而且x 不在其根节点处，那么如果x 小于根节点处的元素，就将x插入左子树，如果x 大于根节点处的元素，就将x 插入右子树。

如图5-35所示的insert(x,T)函数为左子节点右子节点数据结构实现了这一算法。在第(1)行发现T的值为NULL时，就会新建一个节点，该节点就成了树T。第(2)到第(5)行会创建该树，并在第(10)行返回。

      TREE insert(ETYPE x, TREE T)
      {
 (1)      if (T == NULL) {
 (2)          T = (TREE) malloc(sizeof(struct NODE));
 (3)          T->element = x;
 (4)          T->leftChild = NULL;
 (5)          T->rightChild = NULL;
          }
 (6)      else if (x < T->element)
 (7)          T->leftChild = insert(x, T->leftChild);
 (8)      else if (x > T->element)
 (9)          T->rightChild = insert(x, T->rightChild);(10)      return T;
      }复制代码

图 5-35　insert(x,T)函数将x 添加到T 中

如果在T 的根节点处没找到x，那么在第(6)到第(9)行，会根据相应的情况对左子树或右子树调用insert函数。被该插入操作修改过的子树，会分别在第(7)或第(9)行成为T 的根节点的左子树或右子树的新值。第(10)行会返回增加过元素的树。

请注意，如果x 在T 的根节点，那么第(1)、第(6)和第(8)行的测试都不会成功。这种情况下，insert会在什么都不做的情况下返回T，这是正确的，因为x 已经在树中了。

示例 5.24

继续示例5.23的问题，从技术上理解，对字符串进行比较需要的代码与图5-35相比稍有不同，图5-35中<这样的算术比较要替代为对lt 这样恰当定义的函数的调用。图5-36展示了向图5-33插入Filthy后的二叉查找树。首先对根节点调用insert，发现Filthy<Hairy。因此，在图5-35的第(7)行，对左子节点调用insert。结果发现Filthy>Bashful，所以接着在第(9)行对右子节点调用insert。这样就到了Grumpy，它从词典顺序上在Filthy之后，因此就要对Grumpy的左子节点调用insert。

馆陶400电话申请开通【馆陶企业网站建设】馆陶微信公众号小程序开发运营价格、馆陶微信公众号APP软件客户端设计运营、馆陶网页页面设计公司费用、馆陶公司网站制作方案流程改版维护大概需要多少钱