为什么强调使用函数调用的结果？(4) 为什么强调使用函数调用的结果？（⑤） ,例2 printf()的使用 。例3教材P131算法6.4 Status CreateBiTree(BiTree &T){ 。接口 int printf(const char *format [ if (I(T=(...)malloc(...))exit(OVERFLOW); ag®8nt].,,）: CreateBiTree(T->Ichild); CreateBiTree(T->rchild); Returns the number of characters printed,or a negative value if an error occurs. (from MSDN-Microsoft Developer Network) Why? ,遭常的使用 1)malloc失败，调用exit退出程序的执行 printf(“Helo,world!\n”y 2)返回只有一种值：0K→ Wy?一般的应用不关心输出的字符数 调用CreateBiTree时无须判断1 37106 回 38/106 图 例3释放二叉树的所有结点空间 例4副除并释放二叉树中以元素值为x的结点作为根的各子树(1) 【思略】 【本例特征】 ,二叉树为空时，不必释放： 若T不为空，则先释放其左右子树的所有结点的空间，再释放 如何选择二叉树的先序、中序、后序遗历来解决问题，它们 根结点的空间一后序。 对问题求解有何影申？ 若在释放子树的空间前，先释放根结点的空间，则需要将子 【思路】 树的根结点的指针暂存到其他变量：否则，无法找到子树。 整个过程分为两个方面： 【算法门 ·请历中查找元素值为x的结点 void deleteBiTree(BiTree&T){∥此处T应为引用参数 ·查到该结点时，调用例3的算法释放子树空间。 if(T!-NULL) deleteBiTree(T->lchild ) 需要考忠的问愿是： deleteBiTree(T->rchild ) ·如何将全部的结点找到并释放？ ∥访问结点>释放结点的空间 ·外层查找采用的墙历次序对本算法有何影响？ free(T); T■NULL 从以下3个算法中可以看出，利用先序遭历是最合适的：中序和 后序，存在一定的多余操作。 图 40/106 回 例4删除并释放二叉树中以元素值为x的结点作为根的各子树(2) 例4删除并释放二叉树中以元素值为x的结点作为根的各子树(3) 【算法1】 【算法2】 void deleteXTree(BiTree &T,ElemType x) void deleteXTree(BiTree &T,ElemType x) ∥基于先序的查找 ∥基于中序的查找 if(T!-NULL) if (T!-NULL) ∥访问结点>判断是否为指定结点>释放树空间 ∥若T->data■x,则此步骤多余 if(T->data=■x）deleteBiTree(T)i deleteXTree(T->lchild,x): else ∥访问结点>判断是否为指定结点>释放树空间 ∥此处else不能省略 if (T->data=-x) deleteXTree(T->child,x); deleteBiTree(T); deleteXTree(T->rchild,x); else deleteXTree(T->rchild,x); 图 图37/106 为什么强调使用函数调用的结果？(4) „ 例2 printf( )的使用 „ 接口 int printf( const char *format [, argument]... ); Returns the number of characters printed, or a negative value if an error occurs. (from MSDN—Microsoft Developer Network) „ 通常的使用 printf(“Hello, world!\n”) Why? 一般的应用不关心输出的字符数 38/106 为什么强调使用函数调用的结果？(5) „ 例3 教材P131 算法6.4 Status CreateBiTree(BiTree &T){ … if ( !(T=(…)malloc(…) ) ) exit(OVERFLOW); CreateBiTree(T->lchild); CreateBiTree(T->rchild); … } Why? 1) malloc失败，调用exit退出程序的执行 2) 返回只有一种值：OK Æ 调用CreateBiTree时无须判断！ 39/106 【思路】 ™·二叉树为空时，不必释放； ™·若T不为空，则先释放其左右子树的所有结点的空间，再释放 根结点的空间——后序。 ™若在释放子树的空间前，先释放根结点的空间，则需要将子 树的根结点的指针暂存到其他变量；否则，无法找到子树。 【算法】 ™void deleteBiTree(BiTree &T){ // 此处T应为引用参数 ™if ( T != NULL ){ ™deleteBiTree(T->lchild ); ™deleteBiTree(T->rchild ); ™// 访问结点->释放结点的空间 ™free(T); ™T = NULL; ™} ™} 例3 释放二叉树的所有结点空间 40/106 例4 删除并释放二叉树中以元素值为x的结点作为根的各子树 (1) 【本例特征】 如何选择二叉树的先序、中序、后序遍历来解决问题，它们 对问题求解有何影响？ 【思路】 整个过程分为两个方面： ™·遍历中查找元素值为x的结点 ™·查到该结点时，调用例3的算法释放子树空间。 需要考虑的问题是： ™·如何将全部的结点找到并释放？ ™·外层查找采用的遍历次序对本算法有何影响？ ™从以下3个算法中可以看出，利用先序遍历是最合适的；中序和 后序，存在一定的多余操作。 41/106 【算法1】 ™void deleteXTree(BiTree &T, ElemType x) ™{ ™// 基于先序的查找 ™if ( T != NULL ){ ™// 访问结点->判断是否为指定结点->释放树空间 ™if ( T->data== x ) deleteBiTree(T); ™else{ ™// 此处else不能省略 ™deleteXTree(T->lchild, x); ™deleteXTree(T->rchild, x); ™} ™} ™} 例4 删除并释放二叉树中以元素值为x的结点作为根的各子树 (2) 42/106 【算法2】 ™void deleteXTree(BiTree &T, ElemType x) ™{ ™// 基于中序的查找 ™if ( T != NULL ){ ™// 若T->data== x，则此步骤多余 ™deleteXTree(T->lchild, x); ™// 访问结点->判断是否为指定结点->释放树空间 ™if ( T->data== x) ™deleteBiTree(T); ™else ™deleteXTree(T->rchild, x); ™} ™} 例4 删除并释放二叉树中以元素值为x的结点作为根的各子树 (3)