全然二叉树与满二叉树

全然二叉树与满二叉树

去笔试了非常多次，每次都有有关于二叉树的题目，并且当中最多的是关于全然二叉树，然而全然二叉树在哥心中的形态一直非常模糊，究其原因是我把全然二叉树和满二叉树搞混了。事实上满二叉树是全然二叉树的特例，由于满二叉树已经满了，而全然并不代表满。所以形态你也应该想象出来了吧，满指的是出了叶子节点外每一个节点都有两个孩子，而全然的含义则是最后一层没有满，并没有满。

以下贴定义：

满二叉树(Full Binary Tree)：

　　除最后一层无不论什么子 节点 外，每一层上的全部结点都有两个子结点（最后一层上的无子结点的结点为 叶子结点 ）。也能够这样理解，除叶子结点外的全部结点均有两个子结点。节点数达到最大值。全部叶子结点必须在同一层上.

一颗树深度为h，最大层数为k，深度与最大层数同样，k=h;

　　它的叶子数是： 2^h 　　第k层的结点数是： 2^(k-1) 　　总结点数是： 2^k-1 (2的k次方减一) 　　总节点数一定是奇数。

全然二叉树(Complete Binary Tree)

　　若设二叉树的深度为h，除第 h 层外，其他各层 (1～h-1) 的结点数都达到最大个数，第 h 层全部的结点都连续集中在最左边，这就是全然二叉树。 　　全然二叉树是由 满二叉树 而引出来的。对于深度为K的，有N个结点的二叉树，当且仅当其每个结点都与深度为K的满二叉树中编号从1至n的结点一一相应时称之为全然二叉树。 　　若一棵二叉树至多仅仅有最以下的两层上的结点的度数能够小于2，而且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为全然二叉树。

霍夫曼树：每一个节点要吗没有子节点，要么有两个子节点

看以下的题目：

一棵全然二叉树有770个节点，那么它的叶子节点便是

259个

转载于:.html