二叉树的基本性质 二叉树的基本性质3

(1)在二叉树的第k层上,最多有2k-1(k≥1)个结点;解释:最多的时候是满二叉树,它的第1层有21-1=1个结点;第2层有22-1=2个结点;第3层23-1=4个结点;第4层有24-1=8个结点;……



(2)深度为m的二叉树最多有2m-1个结点,最少有m个结点;

(3)对于任意一棵二叉树,度为0的结点(即叶子结点)总是比度为2的结点多一个;即如果其叶子结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;

(4)具有n个结点的二叉树,其深度至少为[log2n]+1,其中[log2n]+1表示取log2n的整数部分;

(5)给定N个节点,能构成h(N)种不同的二叉树;h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。

(6)具有n个结点的完全二叉树的深度为[log2n]+1;

(7)设完全二叉树共有n个结点。如果从根结点开始,按层序(每一层从左到右)用自然数1,2,….n给结点进行编号(k=1,2….n),有以下结论:

①若k=1,则该结点为根结点,它没有父结点;若k>1,则该结点的父结点编号为INT(k/2);

②若2k≤n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点(也无右子结点);

③若2k+1≤n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。

性质1在二叉树的第i层上至多有2i-1个结点(i>=1)。

证明采用归纳法证明此性质。

当i=1时,只有一个根结点,2i-1=20=1,命题成立。

现在假定对所有的j,1<=j<i,命题成立,即第j层上至多有2j-2个结点,

那么可以证明j=i时命题也成立。由归纳假设可知,第i-1层上至多有2i-2个结点。

由于二叉树每个结点的度最大为2,故在第i层上最大结点数为第i-1

层上最大结点数的二倍,即2×(2i-2)=2i-1。

性质2深度为k的二叉树至多有2k-1个结点(k>=1)。

证明第i层的结点数为xi(1≤i≤k),深度为k的二叉树的结点数为M,xi最多为2i-1,则有:

性质3对于一棵非空的二叉树,如果叶子结点数为n0,度数为2的结点数为n2,则有n0=n2+1。

证明设二叉树中度为1的结点数为n1,二叉树中总结点数为N,因为二叉树中所有结点均小于或等于2,所以有:

N=n0+n1+n2(5-1)

再看二叉树中的分支数,除根结点外,其余结点都有一个进入分支,设B为二叉树中的分支总数,则有:

N=B+1。

由于这些分支都是由度为1和2的结点发出的,所以有:

B=n1+2*n2

N=B+1=n1+2×n2+1(5-2)

由式(5-1)和(5-2)得到:

n0+n1+n2=n1+2×n2+1

n0=n2+1

性质4具有n个结点的完全二叉树的深度k为。

证明设所求完全二叉树的深度为k,根据完全二叉树的定义和性质2可知,k-1层满二叉树的结点个数为n时,有

2k-1-1<n≤2k-1

即2k-1≤n<2k

对不等式取对数,有

k-1≤log2n<k

由于k是整数,所以有k-1=,k=,结论成立。

性质5如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第+1层,每层从左到右),则对任一结点i(1<=i<=n),有:

二叉树的基本性质 二叉树的基本性质3
(1)如果i=1,则结点i无双亲,是二叉树的根;如果i>1,则其双亲是结点。

(2)如果2i>n,则结点i为叶子结点,无左孩子;否则,其左孩子是结点2i。

(3)如果2i+1>n,则结点i无右孩子;否则,其右孩子是结点2i+1。

此外,若对二叉树的根结点从0开始编号,则相应的i号结点的双亲结点的编号为(i-1)/2,左孩子的编号为2i+1,右孩子的编号为2i+2。

此性质可采用数学归纳法证明。证明略。

这个性质是一般二叉树顺序存储的重要基础。

下面介绍两种特殊形态的二叉树:满二叉树和完全二叉树。

一棵深度为k且由2k-1个结点的二叉树称为满二叉树。图5-3(a)就是一棵满二叉树,对结点进行了顺序编号。图5-3(b)图则不是满二叉树,因为,虽然其所有结点要么是含有左右子树的分支结点,要么是叶子结点,但由于其叶子未在同一层上,故不是满二叉树。

  

(a)一棵满二叉树(b)一棵非满二叉树

图5-3满二叉树和非满二叉树示意图

一棵深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,则这棵二叉树称为完全二叉树。完全二叉树的特点是:叶子结点只能出现在最下层和次下层,且最下层的叶子结点集中在树的左部。显然,一棵满二叉树必定是一棵完全二叉树,而完全二叉树未必是满二叉树。如图5-4(a)所示为一棵完全二叉树,图5-4(b)为一棵非完全二叉树。

  

(a)一棵完全二叉树(b)一棵非完全二叉树

图5-4完全二叉树和非完全二叉树示意图

二叉树的遍历

(1)前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树;

(2)中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树;

(3)后序遍历(LRD),首先遍历左子树,然后遍历右子树,最后访问根结点。

完全二叉树的定义:深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时,称为完全二叉树。

特点:叶子结点只可能在层次最大的两层上出现;对任一结点,若其右分支下子孙的最大层次为l,则其左分支下子孙的最大层次必为l或l+1

满二叉树:一棵深度为k,且有2的(k)次方-1个节点的二叉树

特点:每一层上的结点数都是最大结点数

满二叉树肯定是完全二叉树

完全二叉树不一定是满二叉树

满二叉树是指除最后一层外,每一层上的所有结点有两个子结点,则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。

完全二叉树是指除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点。

二叉树存储结构采用链式存储结构,对于满二叉树与完全二叉树可以按层序进行顺序存储。

  

爱华网本文地址 » http://www.aihuau.com/a/25101013/182064.html

更多阅读

暗黑2新人很可能不知道的重要知识3:刷装备下

暗黑2新人很可能不知道的重要知识3:刷装备下——简介引言 本文继续上篇没说完的说。首先我要介绍很多新手不知道的单机双开方法,也就是让你自己建的不同人物都进入游戏组队,这样你可以实现增加pp数、大号带小号通关、实现BUG杀等等;然

我最想要的化妆书3 专业化妆书籍推荐

版权说明:经出版方同意授权连载,不得转载!分享到:sinaqzonerenrenkaixingdoubanmsn《我最想要的化妆书3》是畅销650000册《我最想要的化妆书》系列的重磅完结篇。相较之前两本化妆书的内容,这本化妆书3不仅保留了基础护肤、美妆的独门锦

二叉树的基本性质 二叉树的基本性质3

(1)在二叉树的第k层上,最多有2k-1(k≥1)个结点;解释:最多的时候是满二叉树,它的第1层有21-1=1个结点;第2层有22-1=2个结点;第3层23-1=4个结点;第4层有24-1=8个结点;……(2)深度为m的二叉树最多有2m-1个结点,最少有m个结点;(3)对于任意一棵二叉树,度为

踏上巴布亚新几内亚之路的现场报道3 巴布亚新几内亚港口

踏上巴布亚新几内亚之路的现场报道3(梦野现场讲述巴新抗战烈士墓地的故事 3)巴布亚新几内亚是一个有天堂鸟的国家。有关巴新抗战烈士墓园这个内容的文章,目前为止出现在各个媒体的差不多是类似的开场白,从几个月以前的网上第一个由

声明:《二叉树的基本性质 二叉树的基本性质3》为网友哒浪分享!如侵犯到您的合法权益请联系我们删除