满二叉树: 一棵深度为 k 且有 \({2^k - 1 }\) 个结点的二叉树.(特点: 每层都 "充满" 了结点)
完全二叉树: 深度为 k 的, 有 n 个结点的二叉树, 当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应.
具有 n 个结点的完全二叉树的深度为 log2(n) 向下取整 + 1.
满二叉树和完全二叉树的区别: 满二叉树是叶子一个也不少的树, 而完全二叉树虽然前 n-1 层是满的, 但最底层却允许在右边缺少连续若干个结点. 满二叉树是完全二叉树的一个特例.
完全二叉树中度数为 1 的结点的个数为 0 或者为 1.
在非空二叉树中, 第 i 层的结点总数不超过 \({2^{i-1}}\), i>=1.
深度为 h 的二叉树最多有 \({2^h -1}\) 个结点 (h>=1), 最少有 h 个结点.
对于任意一棵二叉树, 如果其叶结点数为 N0, 而度数为 2 的结点总数为 N2, 则 N0=N2+1;
问题: 具有 1102 个结点的完全二叉树的一定有___个叶子结点.
分析:
边数 m=n-1, 那么 m = n1 + 2*n2;
而在完全二叉树中度数为 1 的点只有 1 个或 0 个, 所以代入 0 或 1, 当 n2 为整数时得出 n2 的值,
再利用 n0=n2+1 可得叶子结点的个数.
来源: http://www.bubuko.com/infodetail-3299610.html