Question

假设二叉树采用链接方法存储，编写一个计算一棵二又树t的高度的函数。

Answer 1

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