〓数据结构粉丝来C++

来源：百度知道 编辑：UC知道 时间：2024/05/10 07:30:15
具有n个结点的完全三叉树，其叶子结点共有____________个
请问这题怎样做？

设A[n']是有n'层的树有的叶子节点数。
设B[n']是有n'层的树有的总节点数。

A[n']=A[n'-1]*3 => A[n']=1*3^(n'-1);
B[n']=B[n'-1]+3^(n'-1) => B[n']=1+3+3^2...+3^(n'-1)=(3^n'-1)/2

刚才的这里错了，对不起，我看错了。

let B[n'] = n=>3^(n-1)=3^(n)/3=(2n+1)/3

所以叶子节点数目是(2n+1)/3

n=4时叶子一共有3个。正解。

不明白百度消息我。

3^n-1
就是3的n次方减去1吧。。