二叉树的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＋……＋２^ (ｋ－１) = ２^ｋ- １；

性质３证明： 

首先，由节点的角度看ｎ１＋ｎ２＋ｎ０＝ｎ，设此为（１）式； 

再从边的角度看，ｎ２下接两条边，ｎ１下接一条边，ｎ个节点两两相连一共需要ｎ－１条边，可得２＊ｎ２＋ｎ１＝ｎ－１，此为（２）式； 

由（１）式－（２）式，可得 

ｎ０－ｎ２＝１。

Atas ialah kandungan terperinci 二叉树的5个性质. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!