第5到第6章的勘误表 注意：这个 c 应改为 d 1、第 92 页 倒数第 7 行： 2、第 93 页 倒数第 1 行： 原文为：均小于或等于2，所以有 应改为：的度数均小于或等于2，所以有 4、第 97 页 倒数第 1 行： BinaryNode<Type> * GetRight( ) const { return right; }//得到二叉树结点的左儿子地址。 注意：的度数 漏掉，请补上！ 注意： logn 应改为 log2n 3、第 94 页 第 16 行和第 18 行： 第 16 行： k -1 ≤ logn < k 第 18 行： 由于k是整数，所以有：k =  logn  ＋ 1。 注意：左 应改为 右！ 注意：a 应改为 i 5、第 97 页 的正文的第 2 行： 树类BanaryTree共同组成的。首先定义了二叉树的结点类BinaryNode和它的一些基本操作。 6、第 98 页 倒数第3 行和第4行之间应插入下述语句： return *this; 7、第 98 页 倒数第 16 行： int MakeEmpty ( ) { DelTree( root); root == NULL; } // 使二叉树为空。 注意：int 应改为 void

第5到第6章的勘误表 注意：二叉树的前序序列和后序序列皆为A、B 应改为 二叉树的前序序列皆为A，B 和后序序列皆为B，A 8、第 103页的第22行： 二叉树的前序序列和后序序列皆为A、B, 我们虽然可以很容易地得知结点A为根结点,但是无法确定 注意： 为 应改为 非 9、第 104 页 倒数第 9 行： int operator + ( ) const { return current != NULL; } // 判当前结点为空吗，为空返回 True。 10、第 105 页第 14 行： 子类 Preorder是通过共有继承方式(public)从基类 TreeIterator<Type> 得到的。参见类 11、第 106 页 第 1 行： Exception( current == NULL, “Advanced past end ”;} 12、第 106 页的第4行、第5行： if ( current ->GetRight ( ) != NULL ) s.Push( current->GetRight( ) ); //非空左儿子进栈。 if ( current ->GetLeft ( ) != NULL ) s.Push( current->GetLeft( ) ); //非空右儿子进栈。 13、第 108 页 中的图 5.20 中的： 注意：共 应改为 公 注意： ;} 应改为 );   注意： 左 应改为 右 注意： 右 应改为 左 注意： 应将 2 删除 <A> 2   (16) 图5.20 后序遍历时的堆栈变化 注意： 应将 <A> 删除

第5到第6章的勘误表 14、第 107 页 中的倒数第 14 行： s.MakeEmpty ( ); if ( T.Getroot( ) ) s.push ( StNode<Type>( T.Getroot( )); 注意：在最后一个 ）后，应再插入一个 ） 15、第 107 页的倒数第3行的 TimePop 应改为 TimesPop 16、 第 108 页第5行的 TimePop 应改为 TimesPop 17、第 112 页 中的图 5.24 中的(b)图：     5 5 2 2 1 4 1 4 3 3 注意： 本图正确 注意： 此处错

第5到第6章的勘误表 18、第 117 页 倒数第 17 行和第16行： 原文为： 考虑比较次数)为： log(n-1) + 2 ( log(n-2) + …… + log3 + log2 )。 应改为： 考虑最大比较次数)为： 2 log(n-1) + 4 ( log(n-2) + …… + log3 + log2 )。   19、第 119 页 中的图5. 26 的哈夫曼编码： 哈夫曼编码： E：0 T：10 C：110 S：111 注意：书上错写为 C：10 20、 第 119 页倒数第3行中的 Huffuman 应改为 Huffman 21、 第 120页的第19行中的 Huffuman 应改为 Huffman

第5到第6章的勘误表 22、第 122 页 中的正数第 12 行： 结点C 的地址。若要寻找结点A 的第 3 个儿子，必须首先根据结点A的指针场 firson 找到 注意： firson 应改为 firstson 23、第 135页中的程序 6.3 中的第 5 行： BSTNode * rightt; // 给出结点的右儿子的地址。 注意：删除该 t 24、第 137 页 第 7 行： if ( X < T->data ) T = T->left else if ( X > T->data ) T = T->right; else return T; 注意：此处应插入一个 ； 25、第 141 页 倒数第 8 行及第 7 行： else if ( x < T->data ) return Insert( x, T->left ) // 转向左子树。 else if ( x > T->data ) return Insert( x, T->right ) // 转向右子树。 注意：此处应插入一个 ；   注意：此处应插入一个 ； 26、第 147 页 倒数第 4 行： 假定Q的平衡度原来为-1,那末结点Q的平衡度将由+1变为0，以结点Q为根子树由于高度 注意：+1 应改为 －1

第5到第6章的勘误表 27、第 151 页 第 5 行： 原文为： if ( T == NULL ) return ( T = new BSTNode<Type> (x) ) != NULL; // 创建根结点。 应改为： if ( T == NULL ) { T = new BSTNode<Type> (x); if ( T ) T->BalanceFactor = 0; return T != NULL; } // 创建根结点。 28、第 151 页倒数 第 13 行： 原文为： new_ptr = new BSTNode(x); 应改为： new_ptr = new BSTNode<Type>(x); new_ptr->BalanceFactor = 0;

第5到第6章的勘误表 29、第 160 页 第 19 行： 原文为： 从第一个着色为红色的“哨兵”结点开始，向下搜索。在搜索过程中，我们将力图保证当前结 应改为： 从第一个着色为红色的“哨兵”结点(或根)开始，向下搜索。在搜索过程中，我们将力图保证当前结 注意： 应补上 (或根) 30、第 160 页 倒数第 2 行： 原文为： 那么它的二个儿子都是黑色的,我们可以应用A,B,C三种情况中的任何一种进行变换调整,使得X 注意： A,B,C 应改为 上述 注意：任何 应改为 其中 31、第 160 页 倒数第 4 行： 原文为： 注意：如果T有二个红色的儿子，那末无论进行上述情况B或C的变换调整都是可行的， 注意： B 应改为 (2) 注意： C 应改为 (3)

第5到第6章的勘误表 32、第 161 页正文的正数 第 6 行： 原文为： 32、第 161 页正文的正数 第 6 行： 原文为： 的情况；当前结点X 是黑色的，结点T是红色的，父结点P是黑色的。我们可以进行变换调 注意： X 应改为 X’ 33、第 161 页正文的正数 第 7 行： 原文为： 整，参照图6.34(c)，使得结点X’的父结点P是红色的，结点P的父结点T是黑色的，结点X 注意： X 应改为 X’ 34、第 161 页正文的正数 第 12、13 行： 原文为： 一旦到达一个其二个儿子着色都为黑色的结点或者该结点本身就是红色结点的情况，整个问 题就得到了解决。因为，这保证了删除算法中，被删结点的最终状态必为下列二种状态之一： 注意：此处插入 结点及 注意：此处插入 为黑时

第5到第6章的勘误表 注意：59 应改为 61 35、第 174 页 图 6.44： N 2n 最接近的小于 2n的素数 3 8 7 4   N 2n 最接近的小于 2n的素数 3 8 7 4 16 13 5 32 31 6 64 59 128 127 256 251 9 512 503 10 1024 1019 11 2048 2039 12 4096 4061 8192 8191 14 16384 16363 15 32768 32719 65536 65519   图6.44 最接近2的次幂的素数表

第5到第6章的勘误表 36、第 175 页 倒数第 1 行： (4731)10 (4731)13 = 4*133 + 7* 132 + 3*131 + 1 = ( 110011)10 注意：1 应删除 37、第 177页的倒数第 6 行： 注意：1 应改为 x 1 1 α 1 ＋ 2 α (1-x) 第 177页的倒数第 5行： 注意： α 应删除 1 1 1 ＋ 2 α (1- α)