河南住房与建设厅网站,小白node怎么做网站,网络推广引流是什么意思,网站设计理念介绍文章目录一、二叉树的概念及结构1.概念2.现实中的二叉树3. 特殊的二叉树#xff1a;3.二叉树的性质二、二叉树练习题总结一、二叉树的概念及结构
1.概念
一棵二叉树是结点的一个有限集合#xff0c;该集合:
或者为空由一个根节点加上两棵别称为左子树和右子树的二叉树组成…
文章目录一、二叉树的概念及结构1.概念2.现实中的二叉树3. 特殊的二叉树3.二叉树的性质二、二叉树练习题总结一、二叉树的概念及结构
1.概念
一棵二叉树是结点的一个有限集合该集合:
或者为空由一个根节点加上两棵别称为左子树和右子树的二叉树组成 如上图就是二叉树可以看出 1.二叉树每个节点的度2
2. 二叉树的子树有左右之分次序不能颠倒因此二叉树是有序树
注意对于任意的二叉树都是由以下几种情况复合而成的 2.现实中的二叉树 3. 特殊的二叉树
1满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且结点总数是2^K-1 则它就是满二叉树。 如上图这是一棵满二叉树 推导 该二叉树的高度是h 4. 则该二叉树的节点总数Sn 2^0 2^1 2^2 …2^h-1
由等比数列求前n项和公式 带入数据 有 Sn 2^h -1 (Sn为二叉树节点总数h为树的高度)
所以这就是一棵标准的满二叉树。
如果我们知道一棵满二叉树的总节点个数也可以推导出改满二叉树的节点的高度
推导如下
h log2Sn1
2完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
通俗地讲 1前面每层节点的度都是2 2最后一层节点必须连续
要注意的是满二叉树是一种特殊的完全二叉树。 比如说下面这个 解释如下
如果是这几种情况就不是完全二叉树 因为它们不符合第二点要求最后一层是连续的。
由满二叉树和二叉树的定义可知满二叉数是特殊的完全二叉树。
类似地当我们知道完全二叉树的节点数可以推导完全二叉树的高度
3.二叉树的性质
1. 若规定根节点的层数为1则一棵非空二叉树的第n层上最多有2^(n-1) 个结点. 2. 若规定根节点的层数为1则深度为h的二叉树的最大结点数是2^h - 1 . 3. 若规定根节点的层数为1具有n个结点的满二叉树的深度h log2(n1). (ps 是log以2为底n1为对数) 4. 对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2 ,则有 n0 n21 第四点解析 以下图为例度为0的节点的个数有4个度为2的节点的个数有3个则n0 n2 1
5. 对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对 于序号为i的结点有
1若i0i位置节点的双亲序号(i-1)/2i0i为根节点编号无双亲节点
2若2i1n左孩子序号2i12i1n否则无左孩子
3 若2i2n右孩子序号2i22i2n否则无右孩子
以该例子为例套进去即可。
前面三点是上面推导过的第四点和第五点是重点要记忆的 二、二叉树练习题
1. 某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为
A 不存在这样的二叉树
B 200
C 198
D 199解析 运用上面所讲的性质四即可秒杀。 4. 对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2 ,则有 n0 n21 度为2的节点有199个即n2 199那么度为n0的节点 n21 200 2.在具有 2n 个结点的完全二叉树中叶子结点个数为
A n
B n1
C n-1
D n/2解析 假设这棵完全二叉树的度为012的节点个数分别为 x0 ,x1,x2 有 x0x1x2 2n 又根据性质四x0 x2 1所以化简一下得 x21x1x2 2n 对于一棵完全二叉树来说度为1的节点的个数要么为0要么为1 以上面这棵完全二叉树为例度为1的节点只有1个 以上面这棵完全二叉树的节点为例度为1的节点有0个。 所以对于任何一颗完全二叉树来说度为1的节点只有1个或0个。 则x1 1或x1 0 当x1 1时 x21x1x2 2n --2*x2 2 2n, 所以x2 n 而当x1 0时2*x21 2nx2 (2n-1)/2节点个数不可能为小数所以不成立 所以该完全二叉树的度为1的节点个数为n 3.一棵完全二叉树的节点数位为531个那么这棵树的高度为
A 11
B 10
C 8
D 12解析 以这棵二叉树为例 对于一棵完全二叉树节点个数与高度的关系有 n 2^h-1-x(x为完全二叉树最后一层中缺少的节点的个数) 缺少的节点是相对于满二叉树来说的。 x的最好情况和最坏情况如下 当h 10时节点个数为 2^10 - 1 - x 此时x的取值范围是[0,2^9-1-1],即[0,510] 代入原数据 531 2^10 -1 -xx 492在取值范围内。 当n 11时节点个数为2^11 -1 -x 此时x的取值范围是[0,2^10-1-1]即[0,1022] 代入原数据 531 2^11 -1 -xx 1516不在取值范围内不成立。 而对于当h 12时更不可能了。 对与h 82^8 256,也不可能 所以h 10选B 4.一个具有767个节点的完全二叉树其叶子节点个数为
A 383
B 384
C 385
D 386解析 这道题的解法与第2题解法相同 直接画图分析 总结
熟知二叉树的相关知识概念和性质非常有助于进一步二叉树广度优先搜索和深度优先搜索的学习。
