⼆叉树基础——六个重要性质（国内考试常考）
性质1：⼆叉树第i层上的结点数⽬最多为2^(i-1)(i>=1)
性质2：深度为i的⼆叉树⾄多有2 ^(i)-1个结点，⾄少有2 ^(i-1)个结点（i>=1）性质3：包含n个结点的⼆叉树的⾼度⾄少为(n)+1
性质4：在任意⼀棵⼆叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1证明：
n为总结点数，n1为度为1的结点总数，n0,n2同理；
二叉树的基本性质由（1）（2）
n=n0+n1+n2 (1)
n=n0 *0+n1 *1+n2 2+1即 n=n1+2n2+1 (2)
得：n0=n2+1
性质5：具有n个结点的完全⼆叉树的深度为floor(n)(向下取整)+1
性质6：将⼀颗完全⼆叉树依次编号1-n;
结点编号间关系：
floor （i/2）
|
i
/  \
2i      2i+1log 2log 2

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