结构推理
写一个算法,计算给定二叉树的结点数。
【正确答案】
(1)数据结构
采用二叉树的链接表示。
(2)算法
int num_of_nodes(BinTree t){ /*计算二叉树的结点个数*/
if(t==NULL)return 0; /*空树,返回0*/
return 1+num_of_nodes(t->llink)+num of nodes(t->rlink);
/*返回"1+左子树的结点个数+右子树的结点个数"*/
}
(3)代价分析
该算法访问每个结点各一次,时间代价为O(n),空间代价为O(h)。
【答案解析】
提交答案
关闭