完全⼆叉树的叶⼦节点数公式_数据结构中⼆叉树的度
⾸先说说什么是度：通俗的讲⼆叉树中连接节点和节点的线就是度，有n个节点，就有n-1个度，节点数总是⽐度要多⼀个，那么度为0的节点⼀定是叶⼦节点，因为该节点的下⾯不再有线；度为1的节点即：该节点只有⼀个分⽀；同理度为2的节点就是有两个分⽀。在⼆叉树中不可能存在度为3或⼤于3的节点！
关于度和节点之间的关系还有很多公式：度为0的节点数为度为2的节点数加1，即n0=n2+1
例如：已知767个节点的完全⼆叉树，求其叶⼦节点个数：
n0=n2+1;
n=n0+n1+n2;
由上⾯，消掉n2得到：n=2n0+n1-1;
由于完全⼆叉树度为1的只有0个或1个两种情况，所以，将0或1带⼊上⾯公式，整理后得：
n0=(n+1)/2或者n0=n/2;
看看n是否能被2整除，能则⽤n0=n/2。否则⽤n0=(n+1)/2
既叶⼦节点为n0=(n+1)/2=384
再⽐如⼀棵⼆叉树有10个度为1的节点，7个度为2的节点，则⼆叉树有多少个节点(25)
根据刚才说的，节点数⽐度数多1，可以列出计算式⼦：二叉树公式
10 * 1 + 7 * 2 + 1 = 25

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。