”数据结构： typedefstructbinode { telemetypedata； struct BINODE *lchild，*rchild； }BiNode，*BiTtree； ”递归函数intgettreedeep(bittreet ) /计算二叉树深度(if ) t==null ) return 0； else{inta=gettreedeep(t-lchild )； intb=gettreedeep(t-rchild； 返回(ab )？ (a 1 ) 3360 ) b1 )； }
如图(a )所示，制作这个二叉树，并给出如上递归实现的古典算法，该递归过程会变成什么样呢？
在递归过程中，GetTreeDeep函数会被自己多次调用，所以给它们添加标签吧：
函数的返回值做什么？ 步骤
进入gettreedeep----"函数----"访问A 0
inta=gettreedeep(t-lchild )； 1--”访问B 1
inta=gettreedeep(t-lchild )； 访问0-- " b的左空节点2
intb=gettreedeep(t-rchild； 访问0-- " b的右空节点3
此时，符号2、3函数完成，得到a=0，在步骤2、3中得到的步骤1的函数的a值为1，在步骤1中得到的与步骤0对应的返回值为2的情况下，计算到树的高度为2，这是根节点左侧部分的树的部分的计算值
intb=gettreedeep(t-rchild； —— )访问C 4
inta=gettreedeep(t-lchild )； 2 —— )访问D 5
inta=gettreedeep(t-lchild )； 1 —— )访问F 6
inta=gettreedeep(t-lchild )； 0 —— )访问f的左空节点7
intb=gettreedeep(t-rchild； 0 —— )访问f的右空节点8
由于步骤7和8返回值为0，步骤6的返回值为1，与步骤4对应的返回值为2，接着，执行到该访问c的右节点：
intb=gettreedeep(t-rchild； —— )访问E 9
inta=gettreedeep(t-lchild )； 1 —— )访问G 10
inta=gettreedeep(t-lchild )； 0 —— )访问g的左空节点11
intb=gettreedeep(t-rchild； 0 —— )访问g的右空节点12
根据该类推可知步骤8的返回值为1，在此访问e的右节点：
intb=gettreedeep(t-rchild； 1 —— )访问H 13
inta=gettreedeep(t-lchild )； 0 —— )访问h的左空节点14
intb=gettreedeep(t-rchild； 0访问0 ——》h的右空节点15
从这里返回，比较每个节点的返回值是大还是小
1 )首先，比较步骤13和步骤10的返回值。 两者大小相同，返回1.1，步骤9得到返回值2
2、比较步骤9和5，两者同样为2，所以步骤4的返回值为2.1，为3
3 )比较步骤4和步骤1，前者为3，后者为1，由于取前者，最后返回3 ) 1，得到步骤0的返回值为4的最终结果。
# include stdio.h # include string.h # include stdlib.htypedefstructbitnode { chardata； struct BiTNode *lchild，*rchild； }BiTNode，*BiTree； //二叉树的建立bitreecreate(bitreet ) { char ch； ch=getchar (； if(ch=='# ' ) T=NULL； else{if (！ (t=(bitnode* ) malloc(sizeof ) ) ) ) ) printf ) )空间分配错误！ ' )； T-data=ch； t-lchild=create(t-lchild )； t-rchild=create(t-rchild )； }return T； (//二叉树的前序递归扫描voidpreorder(bitreet ) if ) t ) printf )“%c '，T-data”； preorder(t-lchild )； preorder(t-rchild )； }//二叉树的节点数intsumleaf(bitreet ) if ) t==null ) {return 0； }else{returnsumleaf(t-lchild ) sum leaf (t-rchild ) 1； (//二叉树的中序递归扫描voidzhexu (bitreet ) if ) t ) zhexu ) t-lchild )； printf('%c '，T-data )； 中墟(t-rchild )； ()//二叉树的后序递归扫描voidhouxu(bitreet ) if ) t ) houxu ) t-lchild )； Houxu(t-Rchild )； printf('%c '，T-data )； ()//二叉树的深度intdepth ) bitreet ) ) /每层找左再找右的int m，n； if(t==null ) {return 0； }else{m=Depth(t-lchild )； n=Depth(t-Rchild )； if(Mn ) return ) m1； ELSEreturn(n1； }} int main () ) { BiTree T； int sum，dep； t=create(t； preorder(t； 打印((n )； 中墟(t； 打印((n )； Houxu(t； 打印((n )； sum=sumleaf(t )； printf('%d”，sum )； DEP=Depth(t； printf((n%d )，dep )； 返回0； }