二叉树具有以下五个性质:
1. 在二叉树的第i(i>=1)层最多有2^(i - 1)个结点。
2. 深度为k(k>=0)的二叉树最少有k个结点,最多有2^k-1个结点。
3. 对于任一棵非空二叉树,若其叶结点数为n0,度为2的非叶结点数为n2,则n0 = n2 +1。
4. 具有n个结点的完全二叉树的深度为int_UP(log(2,n+1))。
5. 如果将一棵有n个结点的完全二叉树自顶向下,同一层自左向右连续给结点编号1,2,3,......,n,然后按此结点编号将树中各结点顺序的存放于一个一维数组,并简称编号为i的结点为结点i( i>=1 && i<=n),则有以下关系:
(1)若 i= 1,则结点i为根,无父结点;若 i> 1,则结点 i 的父结点为结点int_DOWN(i / 2);
(2)若 2*i <= n,则结点 i 的左子女为结点 2*i;
(3)若2*i<=n,则结点i的右子女为结点2*i+1;
(4)若结点编号i为奇数,且i!=1,它处于右兄弟位置,则它的左兄弟为结点i-1;
(5)若结点编号i为偶数,且i!=n,它处于左兄弟位置,则它的右兄弟为结点i+1;
(6)结点i所在的层次为 int_DOWN(log(2,i))+1。
部分性质的证明
性质1可以通过数学归纳法得到证明
性质2证明:
由性质1可知,k层的最大节点总数可表示为2^0+2^ 1+……+2^ (k-1) = 2^k- 1;
性质3证明:
首先,由节点的角度看n1+n2+n0=n,设此为(1)式;
再从边的角度看,n2下接两条边,n1下接一条边,n个节点两两相连一共需要n-1条边,可得2*n2+n1=n-1,此为(2)式;
由(1)式-(2)式,可得
n0-n2=1。
Atas ialah kandungan terperinci 二叉树的5个性质. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!