1、一般二叉树的性质
性质1、在非空二叉树的i层上，至多有2^i个结点。
性质2、高度为K的二叉树中，最多有2^(k+1)-1个结点。
性质3、对于任何一棵非空的二叉树，如果叶结点的个数为n0，度为2的结点个数为n2，则有n0=n2+1。
2、完全二叉树
定义：如果一棵二叉树中，只有最下面的两层结点度数小于2，其余各层结点度数都等于2，并且最下面一层的结点，都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
性质1、具有n个结点的完全二叉树的高度k为[log^2n]。
性质2、对于具有n个结点的完全二叉树，如果按照从上（根结点）到下(叶结点)和从左到右的顺序对二叉树中的所有结点从0开始到n-1进行编号，则对于任意的下标为i的结点，有：
（1）如果i=0，则它是根结点，它没有父结点；如果i>0,则它的父结点的下标为（i-1）/2。
（2）如果2i+1
（3）如果2i+2
3、满二叉树
定义：如果一棵二叉的任何结点或者是树叶，或有两棵非空子树，则此二叉树称作满二叉树。
性质、在满二叉树中，叶结点的个数比分支结点个数多1。
4、扩充二叉树
定义：扩充二叉树是对一个已有二叉树的扩充，扩充后原二叉树的结点都变为度数为2的分支结点。也是就是说，如果原结点的度数为2，则不变；度数为1，则增加一个分支；度数为0，则增加两个分支。
性质1、在扩充二叉树中，外部结点的个数比内部结点的个数多1。
性质2、对任意扩充二叉树，外部路径长度E和内部路径长度I之间满足以下关系：E=I+2n，其中n是内部结点个数。
更多常见问题的相关技术文章，请访问常见问题栏目进行学习！
以上就是必须懂的二叉树公式的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
401
收藏
