例2统计二叉树中叶子结点的数目(3) 例2统计二叉树中叶子结点的数目(4-1) 【算法2以函数返回值返回】 【算法3通过引用参数返回】 ∥函数值为T的叶子结点数 ∥引用参数和为T的叶子结点数，方法一 int leaf(BiTree T) void leaf(BiTree T.int &n) ∥利用二叉树的中序遗历，为局部变量 ∥利用二叉树的后序遭历 n■0； n=0; if(T:-NULL) if(T!-NULL) n=leaf(T->lchild)片 leaf (T->lchild,nl); ∥访问结点>叶子结点的判定和计数 leaf(T->rchild,n2): if (T->lchild-=-NULL &T->rchild--NULL )n++; ∥访问结点>叶子结点的判定和计数 n+=leaf(T->rchild); if (T->lchild=-NULL &T->rchild=-NULL )n++; n■n1+n2: return(n); 回 图 例2统计二叉树中叶子结点的数目(4-2) 【算法3通过引用参数返回】 ∥引用参数如等同于全局变量，方法二 为什么强调使用函数调用的结果？(1) ∥把T所指向的二叉树中的叶子结点数暴加到 ∥注意：在调用leaf(T,m)之前要先执行“n=0:” ·—算法/程序的健壮性！ void leaf(BiTree T,int &n) ,对于每算法/程序的任何输入，期望不异常终止 ,养成一种编程的习惯！ ∥利用二叉树的后序遮历 if(T!-NULL) ·例1 leaf (T->lchild,n); ,接口 leaf (T->rchild,n); ∥判断枝是否为空，返回TRUE/FALSE ∥访问结点>叶子结点的判定和计敷数 Status StackEmpty(Stack S); if T->lchild=-NULL &T->rchild=-NULL )n++; ∥出核（道通对战是否为空的判断） ∥若找为空，返回ERROR,否则返回OK Status Pop(Stack &S,ElemType &e); 3311Ue 图 34/106 为什么强调使用函数调用的结果？(2) 为什么强调使用函数调用的结果？(3) ,基于出栈的应用问题 ,基于出栈的应用问题 ∥方素1 Ⅱ方案2 if(StackEmpty(S)) if(Pop(S,e)==ERROR) 栈为空的一些处理 战为空的一些处理 else【 else{ Pop(S,e:I出楼出楼前楼一定非空 .已..发不为空，使用出找获得的元套 .e. 说明：此处直接使用Pop(S,e)的返回值，因为该 说明：此处不用Pop(S,e)的返回值，是因为它的 操作蕴福对栈为空的判断。在调用它后，其返回 返回值在该上下文下是唯一的，即永远为真 值有OK和ERROR两种可能！ 35/106 36/106 回
31/106 例2 统计二叉树中叶子结点的数目(3) 【算法2 以函数返回值返回】 // 函数值为T的叶子结点数 int leaf(BiTree T) { // 利用二叉树的中序遍历, n为局部变量 n = 0; if ( T != NULL ){ n = leaf ( T->lchild ); // 访问结点->叶子结点的判定和计数 if ( T->lchild==NULL && T->rchild==NULL )n++; n += leaf(T->rchild); } return (n); } 32/106 例2 统计二叉树中叶子结点的数目(4-1) 【算法3 通过引用参数返回】 // 引用参数n为T的叶子结点数，方法一 void leaf(BiTree T, int &n) { // 利用二叉树的后序遍历 n = 0; if ( T != NULL ){ leaf (T->lchild, n1); leaf (T->rchild, n2); // 访问结点->叶子结点的判定和计数 if ( T->lchild==NULL && T->rchild==NULL )n++; n = n1+n2; } } 33/106 例2 统计二叉树中叶子结点的数目(4-2) 【算法3 通过引用参数返回】 // 引用参数n等同于全局变量，方法二 // 把T所指向的二叉树中的叶子结点数累加到n // 注意：在调用leaf(T,n)之前要先执行“n＝0;” void leaf(BiTree T, int &n) { // 利用二叉树的后序遍历 if ( T != NULL ){ leaf (T->lchild, n); leaf (T->rchild, n); // 访问结点->叶子结点的判定和计数 if ( T->lchild==NULL && T->rchild==NULL )n++; } } 34/106 为什么强调使用函数调用的结果？(1) ——算法/程序的健壮性！ 对于每算法/程序的任何输入，期望不异常终止 养成一种编程的习惯！ 例1 接口 // 判断栈是否为空，返回TRUE/FALSE Status StackEmpty(Stack S); // 出栈（蕴涵对栈是否为空的判断） // 若栈为空，返回ERROR，否则返回OK Status Pop(Stack &S, ElemType &e); 35/106 为什么强调使用函数调用的结果？(2) 基于出栈的应用问题 // 方案1 if (StackEmpty(S) ) … //栈为空的一些处理 else { Pop(S, e); //出栈---出栈前栈一定非空 …e… } 说明：此处不用Pop(S, e)的返回值，是因为它的 返回值在该上下文下是唯一的，即永远为真 36/106 为什么强调使用函数调用的结果？(3) 基于出栈的应用问题 // 方案2 if ( Pop(S, e) ==ERROR) … //栈为空的一些处理 else { …e… //栈不为空，使用出栈获得的元素 } 说明：此处直接使用Pop(S, e)的返回值，因为该 操作蕴涵对栈为空的判断。在调用它后，其返回 值有OK和ERROR两种可能！
为什么强调使用函数调用的结果？(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)