二叉树具有以下五个性质：
1. 在二叉树的第ｉ（ｉ>=１）层最多有２＾(ｉ - １)个结点。
2. 深度为k(k>=0)的二叉树最少有k个结点，最多有２＾ｋ－１个结点。
3. 对于任一棵非空二叉树，若其叶结点数为n0，度为2的非叶结点数为n2，则ｎ0 = ｎ2 ＋１。
4. 具有n个结点的完全二叉树的深度为int_UP（log(2，ｎ+1)）。
5. 如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号１，２，３，．．．．．．，ｎ，然后按此结点编号将树中各结点顺序的存放于一个一维数组，并简称编号为i的结点为结点i（ ｉ>=１ && ｉ<=ｎ）,则有以下关系：
（1）若 ｉ= 1，则结点i为根，无父结点；若 ｉ> 1，则结点 i 的父结点为结点int_DOWN（ｉ / ２）;
（2）若 ２＊ｉ <= ｎ，则结点 ｉ 的左子女为结点 ２＊ｉ；
（3）若２＊ｉ＜＝ｎ，则结点ｉ的右子女为结点２＊ｉ＋１；
（4）若结点编号ｉ为奇数，且ｉ！＝１，它处于右兄弟位置，则它的左兄弟为结点ｉ－１；
（5）若结点编号ｉ为偶数，且ｉ！＝ｎ，它处于左兄弟位置，则它的右兄弟为结点ｉ＋１；
（6）结点ｉ所在的层次为 int_DOWN（log（2，ｉ））＋１。
部分性质的证明
性质１可以通过数学归纳法得到证明
性质２证明：
由性质１可知，ｋ层的最大节点总数可表示为２＾０＋２＾ 1＋……＋２^ (ｋ－１) = ２^ｋ- １；
性质３证明：
首先，由节点的角度看ｎ１＋ｎ２＋ｎ０＝ｎ，设此为（１）式；
再从边的角度看，ｎ２下接两条边，ｎ１下接一条边，ｎ个节点两两相连一共需要ｎ－１条边，可得２＊ｎ２＋ｎ１＝ｎ－１，此为（２）式；
由（１）式－（２）式，可得
ｎ０－ｎ２＝１。
以上就是二叉树的5个性质的详细内容，更多请关注php中文网其它相关文章！
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移，垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是，许多工具可以让 Windows 保持平稳运行。
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
179
收藏
