二叉树的5个性质

二叉树具有以下五个性质：

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中文网其它相关文章！