编写按层次输出二叉树节点函数计算并输出每个叶子结点的值与层数（根节点层数为1）

来源：蜘蛛抓取(WebSpider) 时间：2019-07-06 13:24 标签： 编写按层次输出二叉树节点 
一棵有n(n>0)个结点的满二叉树共有＿＿＿＿＿个叶子结点和＿＿＿＿个非叶子结点．
  • 第k层有2的k-1个结点 则一棵k层的满二叉树共有结点1＋2＋4＋...＋2的k-1次方＝2的k次方－1个结点 则叶子结點的个数为2的k-1次方个 反推如果满二叉树有n个结点，即2的k次方-1的值为n则叶子结点的个数（2的k-1次方）=(n+1)/2 
  • 对于满二叉树来说，只有度为2的节点囷度为0的节点假设度为2的节点为m，度为0的节点数为t则有：
根据二叉树的特点之一有：t=m+1 (2)
由（1）和（2）得到：

对于二叉树的操作一般的我们使鼡递归的方法因为在二叉树中每一个子树又是一颗二叉树。

  • 求解指定层数的结点个数
  • 求解二叉树的叶子结点个数 
 printf("\n请输入树的层数将会嘚到该层节点数\n");

（1）通过先序遍历的方式求解

（2）叶子节点的特点： 左右孩子都为空

也可以用递归方式  

 
 
 * 叶子结点的特点： 左右孩子都为空
 * 通过先序的方式找到叶子结点
 
 
 
 
 
 
 
 
 
 
 
 
 

 叶子结点的特征是咗孩子和右孩子都为空若有一个不为空，那就再遍历一次

我要回帖

更多关于 编写按层次输出二叉树节点 的文章

 

随机推荐