完全二叉树叶子结点计算方法

计算叶子节点数量的方法如下：
在完全二叉树中，如果该树的深度为d，那么最后一层的节点数为$2^{d-1}$个。
如果内部节点有n个，则该完全二叉树的叶子节点数量等于n+1。
因此，我们可以通过以下方法来计算一个完全二叉树的叶子节点数量：
首先，我们需要确定完全二叉树的深度d，可以一层一层向下遍历来确定。
然后，我们可以计算出最后一层的节点数，即$2^{d-1}$。
接着，我们可以计算内部节点的数目n，即总节点数减去叶子节点数目减一，即n=总节点数-叶子节点数-1。
最后，通过公式n+1来计算完全二叉树的叶子节点数量。

import javaio;
import javautil;

class TreeNode{//节点类
public String data;//节点数据
public TreeNode lchild,rchild;//左孩子及右孩子
public TreeNode(String d){// 节点构造函数
Systemoutprintln("node created");//构造标志
data = d;
}
public TreeNode(){// 节点构造函数
Systemoutprintln("node created");
}
public void visitNode(){//输出节点数据
Systemoutprint(data);
}
}
public class BiTree{
public BiTree(){//主类构造函数
TreeNode tn = new TreeNode();//建立新树根为空
TreeNode tn2 = tn;
tnvisitNode();
Systemoutprintln("start creating tree");//开始建树标志
try{//建立二叉树
createBiTree(tn);
}catch(IOException e){
eprintStackTrace();
}
outputTree(tn);//按层输出二叉树

}
String instr;//接受输入的字符串变量
String over = new String(" ");//结束符标志
BufferedReader br = new BufferedReader(new InputStreamReader(Systemin));
public TreeNode createBiTree(TreeNode tn1)throws IOException{//从键盘输入字符串，按先序次序输入并创建二叉树
Systemoutprintln("input node");
try{//从键盘输入节点数据
instr = brreadLine();
}catch(IOException e){//捕获异常并输出异常信息
eprintStackTrace();
}
if(instrequals(over)){//如果为空则表示没有节点
Systemoutprintln("null node");
tn1 = null;
}
else{//否则建立节点，并为该节点的左孩及右孩子建立节点如此循环
tn1data = instr;
tn1lchild = new TreeNode();
tn1lchild = createBiTree(tn1lchild);
tn1rchild = new TreeNode();
tn1rchild = createBiTree(tn1rchild);
}
return tn1;
}
public void outputTree(TreeNode tn){//二叉树按层输出，传入参数树根
LinkedList ll = new LinkedList();//建立一个队列
TreeNode tm = new TreeNode("newh");//新行标志
int i = 0;
if(tn!=null){
lladdLast(tm);//标志位入队尾
lladdLast(tn);//根入队列尾
}
int numfornode=1;
while(llsize() > 1){//如果栈里有元素，取第一个队列第一个元素并输出

TreeNode tn1 = (TreeNode)llgetFirst();

if(tn1dataequals("newh")){

llremoveFirst();

Systemoutprintln();

Systemoutprintln("第"+(++i)+"层: ");

lladdLast(tn1);

numfornode=1;

}
else{

Systemoutprint("第"+numfornode+"个元素:");

tn1visitNode();//输出节点数据

llremoveFirst();//移出第一个元素

numfornode++;
}

if(!(tn1lchild==null)){//如果有左孩子，将其加入队列尾

lladdLast(tn1lchild);

}
if(!(tn1rchild==null)){

lladdLast(tn1rchild);

}
}
}
public void preOrder(TreeNode tn){
if(!(tn==null)){
tnvisitNode();
preOrder(tnlchild);
preOrder(tnrchild);
}
}
public static void main(String args[]){//程序入口
BiTree bt =new BiTree();
}
}

二叉树有50个叶子结点，且仅有一个孩子的结点数为30个，则总结点数是129个。

根据题意计算：

n0=n2+1

n0=50

n2=49

n1=30

所以结点数129。

扩展资料：

若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：

当i=1时，该节点为根，它无双亲节点。

当i>1时，该节点的双亲节点的编号为i/2。

若2i≤n，则有编号为2i的左节点，否则没有左节点。

若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点。

叶子节点数=总结点数-度数非零的节点数（戒子节点度为0）

叶子结点是离散数学中的概念，一棵树当中没有子结点（即度为0）的结点称为叶子结点，简称“叶子”。 叶子是指出度为0的结点，又称为终端结点。

扩展资料：

例：一棵树度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1，则这棵树的叶子节点个数为多少？

解：因为任一棵树中，结点总数=度数该度数对应的结点数+1，所以：

总结点数=14+22+31+41+1=16

叶子结点数=16-4-2-1-1（总节点数－度不为0的个数）=8

则：n0=8

其中：n0表示叶子结点。

---