满二叉树

编辑:香料网互动百科 时间:2020-06-05 08:53:58
编辑 锁定
除最后一层无任何子节点外,每一层上的所有结点都有两个子结点二叉树。
中文名
满二叉树
外文名
Full Binary Tree
类    别
二叉树
性    质
出度为0或2

满二叉树基本信息

编辑

满二叉树定义:

又叫Full Binary Tree. 除最后一层无任何子节点外,每一层上的所有结点都有两个子结点(最后一层上的无子结点的结点为叶子结点)。也可以这样理解,除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上.|

满二叉树结点

如果一颗树深度为d,最大层数为k
它的叶子数是: 2^d
第k层的结点数是: 2^(k-1)
总结点数是: 2^k-1 (2的k次方减一)
总节点数一定是奇数。
定义介绍
美国以及国际上所定义的满二叉树[1]  ,即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.换个说法即要么为叶子结点,要么同时具有左右孩子。霍夫曼树是符合这种定义的,满足国际上定义的满二叉树,但是不满足国内的定义.

满二叉树确定使用

编辑
在国际交流场合,包括学术会议发表论文等都应该使用美国和国际定义.在国内的各种考试场合,比如研究生考试/软考/计算机等级考试等,都应该使用国内教材的定义.在校学生的校级考根据所在学校采用教材情况而定.
参考资料
  • 1.    完全二叉树与满二叉树  .csdn[引用日期2014-12-12]
  • 词条标签:
    计算机学