度为2度为0的节点怎么算是什么意思

来源：蜘蛛抓取(WebSpider) 时间：2023-03-27 21:38 标签： 叶子结点数与度的关系

树
节点、根节点、父节点、子节点、兄弟节点
一棵树可以没有任何节点，称为空树
一棵树可以只有一个节点，也就是只有根节点
子树、左子树、右子树
节点的度：子树的个数
树的度：所有节点度中的最大值
叶子节点：度为0的节点
层数：根节点在第一层，根节点的子节点在第二层，以此类推
节点的深度：从根节点到当前节点的唯一路径上的节点总数
节点的高度：从当前节点到最远节点的路径上的节点总数
树的深度：所有节点深度中的最大值
树的高度：所有节点高度中的最大值
树的深度等于高度
有序树、无序树
二叉树 是一个有序树
（1） 每个节点的度最大为2（2）左子树和右子树是有顺序的（3）即使某节点只有一棵子树，也要区分左右子树
非空二叉树的第i层，做多有2^(i-1)个节点
在高度为h的二叉树上最多有2^h-1个结点
对于人任何一颗非空二叉树，如果叶子节点个数为n0，度为2的节点个数为n2,则有：n0=n2+1;
度为1的节点个数为n1,那么二叉树的节点总数n=n0+n1+n2;
二叉树的边数T=n1+2*n2=n-1=n0+n1+n2-1;
真二叉树：所有节点的度要么为0，要么为2
满二叉树：所有节点的度都要么为0，要么为2，所有叶子节点在最后一层
完全二叉树：叶子节点只会出现最后2层，且最后1层的叶子结点都靠左对齐
度为1的节点只有左子树
度为1的节点要么是1个，要么是0个
同样节点的二叉树，完全二叉树的高度最小
设二叉树的 高度为h,h>=1,那么
（1）至少有2^(h-1)个节点
（2）最多有2^h-1个节点
（3）总结点为n,h-1<= log2(h)<h
h=floor(log2h)+1,floor向下取整，只取前面的整数。ceiling向上取整
总结点数量n=n0+n1+n2,而且n0=n2+1=>n=2n0+n1-1
完全二叉树的n1要么为0，要么为1
（1）n1为1时，n=2n0,n必然是偶数叶子节点个数n0=n/2,非叶子节点个数n1+n2=n/2（2）n1为0时，n=2n0-1,n必然是奇数叶子节点个数n0=(n+1)/2,非叶子节点个数n1+n2=(n-2)/2
n如果是偶数 叶子节点数量n0=n/2
n如果是奇数 叶子节点数量n0=(n+1)/2
n0=floor((n+1)/2) n0=(n+1)>>1
注意：尽量避免使用乘、除/、模%、浮点数运算，效率低下

我要回帖

更多关于 叶子结点数与度的关系 的文章

 

随机推荐