【正确答案】(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为二叉树的高度。
【答案解析】