满二叉树叶子结点的算法

国外关于满二叉树的定义(如何确定使用哪种定义)

满二叉树(Full Binary Tree)：

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点（最后一层上的无子结点的结点为叶子结点）。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上.

满二叉树叶子结点的算法

如果有一颗深度为h,k层的满二叉树，h=k-1;

它的叶子数是： 2^h

第k层的结点数是： 2^(k-1) (1<=k<=h)

总结点数是： 2^k-1 (2的k次方减一)

总节点数一定是奇数。

国外关于满二叉树的定义

美国以及国际上所定义的满二叉树，即full binary tree,和国内的定义不同，美国NIST给出的定义为：

A binary tree in which each node has exactly zero or two children. In other words, every node is either a leaf or has two children. For efficiency, any Huffman coding is a full binary tree.满二叉树的任意节点，要么度为0，要么度为2.换个说法即要么为叶子结点，要么同时具有左右孩子。霍夫曼树是符合这种定义的，满足国际上定义的满二叉树，但是不满足国内的定义.

如何确定使用哪种定义

在国际交流场合，包括学术会议发表论文等都应该使用美国和国际定义.在国内的各种考试场合，比如研究生考试/软考/计算机等级考试等，都应该使用国内教材的定义.在校学生的校级考根据所在学校采用教材情况而定.