结构推理 假设二叉树采用链接方法存储,编写一个计算一棵二又树t的高度的函数。
【正确答案】(1)数据结构
   采用二叉树的链接表示。
   (2)思路
   对一棵二叉树t,考察它左右子树的高度,取其中大的一个,再加1即为t的高度。
   (3)算法
   int depth(BinTree t){
       PBinTreeNode pbtree;
       int dl,dr;
       pbtree=t;
       if(pbtree==NULL)return-1;
       dl=depth(pbtree->llink);
       dr=depth(pbtree->rlink);
       return(dl>dr?dl:dr)+1;
   }
   (4)代价分析
   设树中的结点个数为n,递归访问次数只可能是n。所以,时间代价为O(n);空间代价为O(h),h为二叉树的高度。
【答案解析】