5、2_2_二叉树的性质.pdf

《5、2_2_二叉树的性质.pdf》由会员分享，可在线阅读，更多相关《5、2_2_二叉树的性质.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2020/3/7王道考研/1本节内容二叉树常考性质王道考研/CSKAOYAN.COM1王道考研/CSKAOYAN.COM二叉树的常考性质二叉树的常考性质常见考点1：设非空二叉树中度为0、1和2的结点个数分别为n0、n1和n2，则n0= n2+ 1（叶子结点比二分支结点多一个）BADGHCEIFLKJ124376581110912假设树中结点总数为 n，则 n = n0+ n1+ n2 n = n1+ 2n2+1n0= n2+ 1 - 树的结点数=总度数+122020/3/7王道考研/2王道考研/CSKAOYAN.COM常见考点2：二叉树第 i 层至多有2i-1个结点（i1）第 1 层：m0第

2、2 层：m1第 3 层：m2第 4 层：m3m叉树第 i 层至多有mi-1个结点（i1）二叉树的常考性质二叉树的常考性质3王道考研/CSKAOYAN.COM常见考点3：高度为h的二叉树至多有2 1个结点（满二叉树）第 1 层：m0第 2 层：m1第 3 层：m2第 4 层：m3等比数列求和公式： + q + 2+ +*+,=.(,+0*),+0至少有多少个?高度为h的m叉树至多有23+,2+,个结点二叉树的常考性质二叉树的常考性质42020/3/7王道考研/3王道考研/CSKAOYAN.COM完全二叉树的常考性质完全二叉树的常考性质常见考点1：具有n个（n 0）结点的完全二叉树的高度h为log

3、2(n + 1)或log2n+ 1124376581110913121514高为 h 的满二叉树共有 2 1 个结点高为 h-1 的满二叉树共有 23+, 1个结点23+, 1 2 123+, + 1 2 1 0）结点的完全二叉树的高度h为log2(n + 1)或log2n+ 1124376581110913121514高为 h-1 的满二叉树共有 23+, 1个结点高为 h 的完全二叉树至少 23+,个结点至多 2 1 个结点23+, 0）结点的完全二叉树的高度h为log2(n + 1)或log2n+ 1 对于完全二叉树，可以由的结点数 n 推出为0、1和2的结点个数为n0、n1和n2（突破点：完全二叉树最多只会有一个度为1的结点）8