Rumah  >  Artikel  >  二叉树的5个性质

二叉树的5个性质

藏色散人
藏色散人asal
2019-06-05 09:37:0314344semak imbas

二叉树的5个性质

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

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!

Kenyataan:
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Artikel sebelumnya:分类算法Artikel seterusnya:系统修复模式是什么意思