承德网站优化【承德开通400电话】承德网站搭建、承德微信公众号推文外包、承德开通京东拼多多设计、承德淘宝装修

承德网站优化【承德开通400电话】承德网站搭建、承德微信公众号推文外包、承德开通京东拼多多设计、承德淘宝装修

承德，河北省地级市，河北省政府批复确定的河北国际旅游城市、连接京津辽蒙的区域性中心城市 [1]  。截至2019年，全市下辖3个区、4个县、代管1个县级市和3个自治县，总面积39519平方公里，常住人口347.32万人，城镇人口180.85万人，城镇化率52.07%。 [2] 

承德地处中国东北地区、河北省东北部，南邻京津，北接赤峰和锡林郭勒，东西与朝阳、秦皇岛、唐山、张家口相邻，距省会石家庄435公里，距北京225公里。 [3]  是连接京津冀辽蒙的重要节点，具有“一市连五省”的独特区位优势，是国家甲类开放城市，中国普通话标准音采集地、中国摄影之乡、中国剪纸之乡。 [4] 

承德是首批国家历史文化名城，1703年清康熙修建避暑山庄，成为清王朝的第二个政治中心；1723年设热河厅；1733年雍正取“承受先祖德泽”之义；赐字“皇承天德”释义先皇秉承天地化育万物的恩德； [5]  设承德直隶州，始称“承德”；民国和解放初期为原热河省省会；1955年，热河省建制撤销，承德划归河北省，为省辖市。承德的避暑山庄及其周围寺庙是中国十大风景名胜、旅游胜地四十佳、国家重点风景名胜区，被联合国教科文组织批准为世界文化遗产，也是国家首批世界文化遗产。 [4] 

2012年，承德被评为中国“十大特色休闲城市”。2016年11月，承德市被中华人民共和国国家旅游局评为第二批国家全域旅游示范区。2017年10月，承德市入选国家森林城市。 [6]  2017年12月，获得“厕所革命优秀城市奖”。

程序设计还要更具防御性

图5-19中的程序有若干方面表现出了一种粗心的编程风格，这是应该避免的。具体来说，我们在没有首先检查指针是否为NULL的情况下就一路前进了。因此，在第(1)行，n是可能为NULL的。我们真应该将程序以如下形式开头。

if (n != NULL) /* then do lines (1) to (9) */else /* print an error message */复制代码

即便n不是NULL，在第(3)行还是可能看到它的leftmostChild字段是NULL，因此应该检测一下n->leftmostChild是否为NULL，如果是，就打印出错误消息，而且不去调用eval。同样，即便n的最左子节点存在，该子节点也可能没有右兄弟节点，所以在第(4)行之前还需要检查

n->leftmostChild->rightSibling != NULL复制代码

而且该程序还依赖于树中节点所含信息是正确的这一假设。例如，如果某个节点是内部节点，它的标号为二元运算符，而且我们已经假设它具有两个子节点，并且第(3)行和第(4)行的指针不可能为NULL。不过，运算符标号有可能是不正确的。要正确处理这种情形，就应该在switch语句中加入default情况，以检测意料之外的运算符标号。

作为一般规则，对程序的输入永远正确这一假设的依赖过分简单了；在现实中，“只要有可能出错，就肯定会出错。”如果某个程序要使用多次，势必会遇到那些形式不符合程序员预想的数据。在实践中多么小心都不为过。盲目地接受NULL指针，或假设输入数据总是正确的，都是常见的编程错误。

习题

1. 编写递归程序，计算用最左节点指针和右兄弟节点指针表示的树的节点数量。

2. 编写递归程序，找到树中具有最大标号的节点。假设该树节点的标号都为整数，而且是用最左子节点右兄弟节点指针表示的。

3. 修改图5-19中的程序，使其能处理含有一元减号节点的树。

4. * 编写递归程序，为最左子节点右兄弟节点指针表示的树计算左右对的数量。所谓左右对，就是指节点n 在m 左侧这样的一对节点n 和m。例如，在图5-20中，节点5就在标号为*、-、10、3和2的节点左侧，而节点10在节点3和节点2左侧，节点-在节点2左侧。因此，该树的左右对共有8对。提示：在对节点n 调用编写的递归函数时，要让该函数返回两个部分，以n 为根节点的子树中左右对的数量，还有以n 为根节点的子树中节点的数量。

5. 以(a)前序和(b)后序列出图5-5中（见5.2节的习题）树的节点。

6. 对如下各表达式

(i) (x+y)*(x+z)

(ii) ((x-y)*z+(y-w))*x

(iii) ((((a*x+b)*x+c)*x+d)*x+e)*x+f

完成以下操作：

(a) 构建表达式树；

(b) 写出等价的前缀表达式；

(c) 写出等价的后缀表达式。

7. 将后缀表达式ab+c *de-/f 转换为(a)中缀表达式和(b)前缀表达式。

8. 编写函数，使其可以“环游”树，并在经过节点时打印节点的名称。

9. 图5-17中的后序函数进行的操作A0、A1等各是什么？（“操作”就是如图5-13所指的那些。）

5.5　结构归纳法

第2章和第3章已经介绍了不少有关整数属性的归纳证明。可以假设某一命题对n 来说为真，或者假设命题对所有小于等于n 的整数都成立，并使用该归纳假设证明同一命题对n+1也成立。“结构归纳法”与之类似但不尽相同，适用于证明与树有关的属性。结构归纳法模拟了对树的递归算法，而且这种形式的归纳法在想要证明一些与树有关的命题时是最易于使用的。

假设要证明命题S(T )对所有的树T 都为真。作为依据，要证明S(T )对由单一节点组成的树T 为真。而对归纳部分来说，要假设T 是一棵以r 为根节点，并有子节点c1、c2、…、ck（k≥1）的树。如图5-23所示，设T1、T2、…、Tk分别是以c1、c2、…、ck为根节点的T 的子树。那么归纳步骤就是假设S(T1)、S(T2)、…、S(Tk)都为真，并证明S(T )。如果完成了这一证明，就可以得出S(T )对所有的树T 都成立的结论。这种形式的论证就叫作结构归纳法。请注意，除了要区分依据部分（1个节点）和归纳步骤（多于1个节点），结构归纳法不会提及树中具体的节点数。

图 5-23　树及其子树

示例 5.17

一般情况下，在证明对树进行操作的递归程序时会需要用到结构归纳法。举例来说，可以再次看看图5-19所示的eval函数，图5-24重现了该函数的函数体。只要将指向T 根节点的指针赋值给该函数的参数n，就可将该函数应用于树T。然后它就会计算由T 表示的表达式的值。接下来要用结构归纳法证明如下命题。

(1)      if (n->op) == 'i') /* n 指向叶子节点 */(2)          return n->value;
         else {/* n 指向内部节点 */(3)          val1 = eval(n->leftmostChild);(4)          val2 = eval(n->leftmostChild->rightSibling);(5)          switch (n->op) {(6)              case '+': return val1 + val2;(7)              case '-': return val1 - val2;(8)              case '*': return val1 * val2;(9)              case '/': return val1 / val2;
             }
         }复制代码

图 5-24　图5-19中eval(n)函数的函数体

命题S(T )。在对T 的根节点调用eval时，返回的值是T 所表示的算术表达式的值。

依据。作为依据，T 由单个节点组成。也就是说，参数n 是一个（指向）叶子节点（的指针）。因为在该节点表示操作数时，op字段具有值“i”，图5-24中第(1)行的测试会成功，第(2)行会返回操作数的值。

归纳。假设节点n 不是（指向）叶子节点（的指针）。归纳假设就是，S(T' )以n的某个子节点为根节点的每棵树T' 都为真。必须使用这一推理证明S(T )对以n 为根节点的树T 成立。

因为假设运算符都是二元的，所以n有两棵子树。根据归纳假设，第(3)行和第(4)行计算出val1和val2的值，分别是左子树和右子树的值。图5-25展示了这两棵子树，val1存放着T1的值，val2存放着T2的值。

图 5-25　调用eval(n)返回T1和T2的值的和

如果看看第(5)行到第(9)行的switch语句，就会发现不管根节点n 处出现什么运算符，它都会被应用到val1和val2这两个值上。例如，如果根节点处存放着+，如图5-25所示，那么第(5)行返回的值就是val1+val2，正如这应该是树T1和T2对应表达式的和。现在就完成了归纳步骤。

因此可以得出S(T )对所有的表达式树T 都成立的结论，eval函数能正确地求出表示表达式的树的值。

示例 5.18

现在来考虑一下图5-22中的computeHt函数，图5-26重现了该函数的函数体。该函数接受（指向）节点n（的指针）作为参数，并计算n 的高度。我们将通过结构归纳法证明以下命题。

(1)        n->height = 0;(2)        c = n->leftmostChild;(3)        while (c != NULL) {(4)            computeHt(c);(5)            if (c->height >= n->height)(6)                n->height = 1+c->height;(7)            c = c->rightSibling;
           }复制代码

图 5-26　图5-22中computeHt(n)函数的函数体

命题S(T )。在对指向树T 根节点的指针调用computeHt时，T 中每个节点的正确高度都会被存储在该节点的height字段中。

依据。如果树T 只有一个节点n，那么在图5-26中的第(2)行，c 会被赋上NULL值，因为n 没有子节点。因此，第(3)行的测试会立即失败，而且while循环的循环体永远都不会执行。因为第(1)行会将n->height置为0（这对叶子节点而言是正确的值），所以可以得出结论，当T 只有一个节点时S(T )成立。

归纳。现在假设n 是有多个节点的树T 的根节点，那么n 至少有一个子节点。我们可以在归纳假设中假定，在第(4)行调用computeHt(c)时，以c 为根节点的子树中每个节点（包括c 本身）的height字段中都被装入了正确的高度。现在需要证明，第(3)行到第(7)行的while循环可以正确地将n->height置为比n 的子节点的最大高度大1。要做到这一点，就需要执行另一次归纳，这是嵌套在该结构归纳法证明过程中的，就像是程序中循环嵌套在另一个循环中那样。该归纳使用的是“普通的”归纳法而不是结构归纳法，它的命题如下。

命题S' (i )。在第(3)到第(7)行的循环执行i 次之后，n->height的值要比n 前i 个子节点的最大高度大1。

依据。依据是i=1的情况。因为n->height在循环外——第(1)行——会被置为0，并且肯定不会有比0还小的高度，所以第(5)行的测试会得到满足。第(6)行就会将n->height置为比n 的第一个子节点的高度大1。

归纳。假设S' (i )为真。也就是说，在循环的迭代i 次之后，n->height会比前i 个子节点的最大高度大1。如果有第i+1个子节点，那么第(3)行的测试会成功，而且会第i+1次执行循环体。第(5)行的测试会将新的高度与之前的最大高度相比较。如果新高度c->height比前i 个高度中最大值加1要小，就不用对n->height进行任何改变。这是对的，因为前i+1个子节点的最大高度是可以与前i 个子节点的最大高度相同的。不过，如果新的高度比之前的最大值大，第(5)行的测试就会成功，这样n->height就会被置为比第i+1个子节点的高度大1，这是正确的。

现在可以回到结构归纳了。当第(3)行的测试失败时，就已经考虑过n 的所有子节点了。内层的归纳S' (i )说明，当子节点的总数为i 时，n->height要比n 各子节点的最大高度大1。这就是n 的正确高度。将归纳假设S 应用于n 的各子节点，就得到结论：正确的高度已经存储到每个子节点的height字段中。因为已经得知n 的高度也已经正确地计算出来，所以可以得出结论：T 中所有节点都被赋上了它们正确的高度值。

现在已经完成了结构归纳法的归纳步骤，并得出结论：对每棵树调用computeHt都可以正确地计算树中每个节点的高度。

结构归纳法的模板

下面简述了进行正确的结构归纳法证明的过程。

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

2. 证明依据，也就是只要T 是一棵单节点的树，S(T )就为真。

3. 建立归纳步骤，设T 是以r 为根节点的树，而且有k≥1棵子树，分别为T1、T2、…、Tk。表示假定有归纳假设，即S(Ti )对每棵子树Ti（i=1、2、…、k）都为真。

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

5.5.1　结构归纳法为何有效

要说明结构归纳法为何是一种有效的证明方法，其原因与普通归纳法有效的原因类似：如果结论为假，那么就会有个最小的反例，而且该反例既有可能违背依据，也可能违背归纳过程。也就是说，假设有命题S(T )，已经证明了它的依据和结构归纳步骤，而存在一棵树或多棵树可以让S 为假。设T0是可以让S(T0)为假的这样一棵树，并设T0与让S 为假的任一棵树的节点一样少。

有两种情况。第一种，假设T0由单个节点组成。那么根据依据，有S(T0)为真，所以这种情况不可能发生。

现在就只剩下T0有多个节点的情况了，这里假设T0有m个节点，那么T0就是由根节点r 与一个或多个子节点构成。设以这些子节点为根的树分别是T1、T2、…、Tk 。这里可以声明T1、T2、…、Tk 的节点数均不超过m-1。因为如果某棵树（假如是Ti）的节点数达到或超过m，那么由Ti（可能还有其他子树）和根节点r 组成的T0就至少会有m+1个节点。这与T0刚好有m 个节点的假设是矛盾的。

因为T1、T2、…、Tk 这些子树的节点数都不超过m-1，所以就可以知道这些树都不能违背S，因为选择了T0是让S为假的最小子树。因此可知S(T1)、S(T2)、…、S(Tk)都为真。而假设已经得到证明的归纳步骤说明了S(T0)也为真，这样又与T0违背S 的假设产生了矛盾。

在考虑完这两种可能的情况后，我们就知道：不管一棵树只有一个节点还是有多个节点，T0都不可能是S 的例外。因为S 是没有例外的，所以S(T )一定对所有的树T 都为真。

5.5.2　习题

1. 通过结构归纳法证明：

(a) 图5-15的前序遍历函数会以前序打印出树的标号；

(b) 图5-17中的后序函数会以后序列出标号。

2. * 假设分支系数为b 的单词查找树是用具有图5-6中所示格式的节点表示的。用结构归纳法证明：如果树T 有n 个节点，那么它的节点中有1+(b-1)n 个NULL指针。那么，共有多少非NULL指针？

3. * 节点的度是指节点所具有的子节点的数目。2用结构归纳法证明：在任意树T 中，节点的数目都要比节点的度之和大1。

2分支系数和度是相关的概念，但它们是不同的，分支系数是树中各节点度的最大值。

4. * 用结构归纳法证明：在任意树T 中，叶子节点的数目都要比具有右兄弟节点的节点的数目大1。

5. * 用结构归纳法证明：在任意用最左子节点右兄弟节点的数据结构表示的树T 中，NULL指针的数目都要比节点的数目大1。

6. * 在5.2节开始的部分，我们给出了树的递归定义和非递归定义。使用结构归纳法证明：每棵以递归方式定义的树在非递归定义下也是同样的树。

7. ** 证明习题(6)的逆命题：每棵以非递归方式定义的树在以递归方式定义时也是相同的树。

树的归纳的谬误形式

我们常常会想着对树的节点数进行归纳，就是假设命题对具有n 个节点的树成立，并证明它对具有n+1个节点的树也成立。如果不够谨慎，就很可能作出这种荒谬的证明。

在第2章中对整数进行归纳证明时，我们提出了一种合理的方法，就是试着用S(n)证明命题S(n+1)，并称这种方法为“后靠”。有时候有人可能把这一过程看作从S(n)开始并证明S(n+1)，称这种方法为“前推”。在整数的情况下，这基本上是相同的意思。不过，对树而言，我们不能先假设命题对具有n 个节点的树成立，并在某个位置加上一个节点，然后就说证明了结果对所有具有n+1个节点的树都成立。

例如，声明S(n)：“所有具有n 个节点的树都有一条长度为n-1的路径。”n=1的依据情况显然为真。在错误的“归纳”中，可能会作出如下论证：“假设有一棵具有n 个节点的树T，它有一条长n-1的路径，假如说是到节点v 的。给v 加上子节点u。现在就有了一棵具有n+1个节点的树，而且它有一条长度为n 的路径，这样就证明了归纳步骤。”

当然，上述论证是谬误的，因为它没有证明结果对所有具有n+1个节点的树都为真，而只是证明了对选出的一些树为真。正确的证明不能是从n个节点“前推”到n+1个节点，因为我们不会从这一过程得出所有可能的树。我们必须从任意具有n+1个节点的树开始“后靠”，小心地选出一个节点，并将其删除，从而得到一棵具有n个节点的树。

承德网站优化【承德开通400电话】承德网站搭建、承德微信公众号推文外包、承德开通京东拼多多设计、承德淘宝装修