二叉树相关的一些知识及计算题？计算机二级二叉树算法

本文目录

• 二叉树相关的一些知识及计算题
• 计算机二级二叉树算法
• 请问二叉树的节点数怎么求的
• 二叉树中的度是怎么来计算的呢
• 怎么算二叉树的深度

二叉树相关的一些知识及计算题

本人正在学习的过程中，若有不足或者错误，希望能够指出

希望我写的这些，能够帮到看到这篇文章的你

1、二叉树的深度（好多资料都喜欢设为k），也就是层数；

2、任意一棵树的总的节点数等于总分支数＋1；

3、叶子节点，也可以称为末级节点（即最底层的节点，度为0，度的值也就是分支数）；

4、一个深度为k的满二叉树的总结点数为2^k - 1（满二叉树指除叶子节点外每一个节点都有两个分支，即只有度为2和度为0的节点）;

5、深度为k的完全二叉树，最少有2^(k -1 )个节点，最多有2^k - 1个节点（即满二叉树，是特殊的完全二叉树）。

1、一颗二叉树第六层（即深度为6）的节点树最多为？

答：二叉树每层的节点数最多为2^(k -1 )；

    一般问最多，直接考虑为满二叉树，所以第六层为2^5 ＝ 32;

2、某二叉树中度为2的节点有18个，则该二叉树中有多少个叶子节点？

答：首先需要知道两个公式：

总节点个数＝总分支数＋1

总结点个数＝度为2的节点数＋度为1的节点数＋度为0的节点数

然后就可以列等式了（数学真的是很厉害）

度为2的，分支数为节点数*2；度为1的，分支数为节点数*1；度为0的，分支数为节点数*0；

设度为2、1、0的节点数为n2、n1、n0，那么有n2 + n1 +n0 = n2 * 2 + n1 * 1 + n0 * 0 + 1

也就是一个公式n0 = n2 + 1，直接就出来了

结果：n0=19；

3、设一颗完全二叉树共有199个节点，那么该二叉树共有多少个分支节点？

答：以第二题的节点进行假设：

分支节点数 ＝ n2 + n1，也就是总节点数n － 叶子总节点数n0；

进行一个假设，这个完全二叉树深度为k，也就是前k-1层为满二叉树，那么有：

2^(k-1) - 1 《 199

这个k值怎么取应该不用我再细说，得到k＝8；所以前7层的总的节点数为2^7 - 1 =127；

那么最后一层的叶子数为：总结点数 － 前7层的叶子总数 ＝ 199 － 127 ＝ 72；

第7层肯定是有叶子节点的（不然就是满二叉树了），第七层的叶子数 ＝ 第七层的叶子数 － 度为2以及度为1的节点数 ＝ 2^7 - 72/2 = 28;

所以这个完全二叉树的总叶子节点数为：28 ＋ 72 ＝ 100；

依据开头的公式，分支节点数 ＝ 总节点数 － 叶子总节点数  ＝ 199 － 100 ＝ 99；

4、在深度为7的二叉树中，最多有多少个叶子节点？

答：先说答案，最多为满二叉树，也就是2^(7-1) ＝ 64；

5、设一颗完全二叉树共有127个节点，那么该二叉树是满二叉树吗？

答：还是先设深度为k，那么假设它为满二叉树，看能否计算出k值（记住k可是整数啊）；

有公式2^k - 1  = 127 ，得k ＝ 7；

说明肯定是满二叉树。

6、具有53个节点的完全二叉树的深度为？

答：惯例，设深度为k；

一般提到完全二叉树，先考虑前k - 1层，因为前k - 1层肯定是满二叉树，根据公式

2^(k-1) - 1 《 53

取最大的一个k值即可，得k＝6

7、设一颗完全二叉树共有700个节点，则在该二叉树中共有多少个叶子节点？

答：来来来，国际惯例，设深度k

聪明的你，有没有发现其实和第三题算是一个题（一个是求分支节点，一个叶子节点，合起来不就是总节点数么）

我就直接列公式了：2^(k -1) - 1 《 700

取最大的一个k值，得k ＝ 10 

就能够得到第10层的节点数也就是一部分叶子节点（因为第9层还有叶子节点）为：700 － 2^9 + 1 = 189；

第9层的叶子节点 ＝ 第9层节点总数 -  第9层度为2的节点和度为1的节点数  = 2^(9 - 1 ) - 188/2 -1 = 161；

所以这个二叉树中的总叶子节点数为：161 ＋ 189 ＝ 350 

公式（上面的题要是都了解了，下满的公式也就不重要了，不然可能会让你混乱）：

这里先设值，二叉树的深度为k，二叉树的节点总数为n，度为2、1、0的节点数为n2、n1、n0，第k层的节点数nk

二叉树的节点总数n ＝ n2 + n1 + n0，n0 ＝ n2 + 1

总节点个数n = 总分支个数 ＋ 1 ＝ n2 * 2 + n1 * 1 + n0 * 0 + 1

二叉树为满二叉树：节点总数n = 2^k - 1，第k层的节点数nk ＝ 2^(k - 1 )
    第一次写，题目是自己在网上找的，但分析是自己分析的；有点乱，后续会把它精简，毕竟有一个从繁到简的过程；

    分析的不知是否正确，若有错误，希望能够给我留言，我会及时改正的。

计算机二级二叉树算法

1、二叉树的概念

二叉树是一种特殊的树形结构，每个结点最多只有两棵子树，且有左右之分不能互换，因此，二叉树有五种不同的形态。

2、二叉树的性质

性质1 在二叉树的第k层上，最多有2^(k-1)(k≥1）个结点。

性质2 深度为m的二叉树最多有2^m-1个结点。

性质3 在任意一棵二叉树中，度为0的结点（叶子结点）总是比度为2的结点多一个。

性质4 具有n个结点的二叉树，其深度不小于表示为log2n的整数部分。

3、满二叉树与完全二叉树

（1）满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m－1个结点。

（2）完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。

（3）满二叉树是完全二叉树，而完全二叉树一般不是满二叉树。

4、完全二叉树的性质

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

性质2 完全二叉树中度为1的结点数为0或1。

5、二叉树的遍历

1、前序遍历：先访问根结点、然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

2、中序遍历：先遍历左子树、然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。

3、后序遍历：先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。

请问二叉树的节点数怎么求的

完全二叉树的叶子节点数公式为：

设叶子节点数为n0, 度为1的节点数为n1，度为2的节点数为n2，总节点为n。

1、当n为奇数时（即度为1的节点为0个），n0= (n+1)/2。

2、当n为偶数（即度为1的节点为1个）， n0= n/2。

n1，n2，都可以求。

特殊类型：

1、满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

2、完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。

3、完全二叉树的特点是叶子结点只可能出现在层序最大的两层上，并且某个结点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。

相关术语：

1、结点：包含一个数据元素及若干指向子树分支的信息。

2、结点的度：一个结点拥有子树的数目称为结点的度。

3、叶子结点：也称为终端结点，没有子树的结点或者度为零的结点。

4、结点的层次：从根结点开始，假设根结点为第1层，根结点的子节点为第2层，依此类推，如果某一个结点位于第L层，则其子节点位于第L+1层。

5、树的深度：也称为树的高度，树中所有结点的层次最大值称为树的深度。

以上内容参考   百度百科-二叉树

二叉树中的度是怎么来计算的呢

度=节点总数-1。在树中，每个节点有多少条边出去，该节点的度就为多少。也就是说，一条边贡献一个度。而树中，边的条数是节点数减去1。计算节点数一般的方法是 n=n0+n1+n2+... 所以度和节点的关系就是，度=节点总数-1

n为奇数时，完全二叉树中没有度为1的节点：我们可以这样看，完全二叉树第一层有一个节点，若想完全二叉树的总结点数是奇数，下面的每一行节点数都必须是偶数。所以，每个节点要么度为0，要么度为2。此时  n = n0 + n2

n为偶数时，完全二叉树中只有一个度为1的节点：完全二叉树第一层有一个节点，若想总节点数为偶数，最后一层必须是奇数个节点。那么单独出来的这个节点的双亲，度就为1。而且也只有它一个度为1的节点。 此时 n = n0 + 1 + n2

怎么算二叉树的深度

二叉树的深度计算，首先要判断节点，以下是计算二叉树的详细步骤：

1、一颗树只有一个节点，它的深度是1；

2、二叉树的根节点只有左子树而没有右子树，那么可以判断，二叉树的深度应该是其左子树的深度加1；

3、二叉树的根节点只有右子树而没有左子树，那么可以判断，那么二叉树的深度应该是其右树的深度加1；

4、二叉树的根节点既有右子树又有左子树，那么可以判断，那么二叉树的深度应该是其左右子树的深度较大值加1。

一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。

具有n个节点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个叶子节点，至多有2k-1个节点。

扩展资料

二叉树深度的性质：

1、在非空二叉树中，第i层的结点总数不超过, i》=1；

2、深度为h的二叉树最多有个结点(h》=1)，最少有h个结点；

3、对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

4、具有n个结点的完全二叉树的深度为

5、有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

若I为结点编号则 如果I》1，则其父结点的编号为I/2；

如果2*I《=N，则其左孩子（即左子树的根结点）的编号为2*I；若2*I》N，则无左孩子；