二叉树的性质

本文主要讲述二叉树的性质。二叉树是n个节点的有限集。它或为空树（n=0）,或由一个根节点和两棵分别称为左子树和右子树的互不相交的二叉树构成。

二叉树的第i层上至多有2^(i-1)个节点，其中i>=1，比如下图中第三层有【2^(3-1)】=4个节点

深度为k的二叉树中至多有2^(k)-1个节点。比如下图，深度为4，有【2^(4)-1】个节点，此时该二叉树为满二叉树。

对任意一棵二叉树，如果其叶子结点数，也就是度为0的节点数为n0,度为2的节点数为n2,则n0=n2+1.比如下图中度为0的节点数为8，度为2的节点数为7，经过简单的计算我们可以知道8=7+1。

现在对性质三进行解释，对于任意一棵二叉树，它的节点分为三种，一种是度为0的点n0，一种是度为1的点n1，一种是度为2的点n2。那么二叉树中的节点总数为三种之和。即n=n0+n1+n2.(n是节点总数)

继续对性质三的解释，假设二叉树中有m个分支。由于除根节点外，每一个节点都有一个分支，所以n=m+1。

继续对性质三的解释，由于每一个分支都是由度为1和度为2的节点射出的，度为1的节点射出一个分支，度为2的节点射出2个分支。由此m=n1*1+n2*2。

根据以上表达式可以推导出n0=n2+1

现在开始性质4啦，具有n个节点的完全二叉树的深度k为(log2n)+1,其中2是底数。若n=10,则它的深度k=(log2n)+1~3+1=4。

具有n个节点的完全二叉树，从上到下和从左到右的顺序对所有节点从1开始编号则对任意节点i,i=1,该节点是根节点；2i<=n,其左子节点序号为2i;2i>n,则i节点无左右子节点；2i+1<=n,右子节点序号为2i+1,2i+1>n,则该节点无右子节点。通俗讲就是一个节点若是有左右节点，那么它的的编号是它左子节点的一半，是它右子节点的编号-1的一半。

免责声明：本站文字信息和图片素材来源于互联网，仅用于学习参考，如内容侵权与违规，请联系我们进行删除，我们将在三个工作日内处理。联系邮箱：chuangshanghai#qq.com（把#换成@）