例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两种可能！