二叉树各种计算公式总结 二叉树的计算方法

二叉树结点计算方法

二叉树叶子结点计算方法：

1、结点的度是指，该结点的子树的个数，在二叉树中，不存在度大于2的结点。

2、计算公式：n0=n2+1，n0是叶子节点的个数，n2是度为2的结点的个数，n0=n2+1=5+1=6。

3、故二叉树有5个度为2的结点，则该二叉树中的叶子结点数为6。

叶子节点数=总结点数-度数非零的节点数（戒子节点度为0）

叶子结点是离散数学中的概念，一棵树当中没有子结点（即度为0）的结点称为叶子结点，简称“叶子”。 叶子是指出度为0的结点，又称为终端结点。

例：一棵树度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1，则这棵树的叶子节点个数为多少？

解：因为任一棵树中，结点总数=度数*该度数对应的结点数+1，所以：

总结点数=1*4+2*2+3*1+4*1+1=16

叶子结点数=16-4-2-1-1（总节点数－度不为0的个数）=8

则：n0=8

其中：n0表示叶子结点。

二叉树各种计算公式总结 二叉树的计算方法

二叉树各种计算公式总结有哪些？

二叉树各种计算公式总结有n个节点的二叉树一共有2n除以n乘以 n+1这种，n层二叉树的第n层最多为2乘n减1个。二叉树节点计算公式 N 等于n0加n1加n2，度为0的叶子节点比度为2的节点数多一个。N等于1乘n1加2乘n2加1。具有n个节点的完全二叉树的深度为log2n加 1。

二叉树的含义

二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个最多只能有两棵子树，且有左右之分。

二叉树是n个有限元素的集合，该集合或者为空，或者由一个称为根的元素及两个不相交的，被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。

二叉树有叶子结点，有度为1的结点，总结点怎么算？有公式嘛？

根据叶子节点算出度为2的结点数，然后结合度为1的节点数。

公式：N0 = N2 +1

n0 是叶子节点的个数；n2 是度为2的结点的个数。

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

扩展资料：

若I为结点编号则，如果I>1，则其父结点的编号为I/2；如果2*I<=N，则其左孩子（即左子树的根结点）的编号为2*I；若2*I>N，则无左孩子；如果2*I+1<=N，则其右孩子的结点编号为2*I+1；若2*I+1>N，则无右孩子。

若结点是二叉树的根，则其后继为空；若结点是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点；若结点是其双亲的左孩子，且其双亲有右子树，则其后继为双亲右子树上按后序遍历列出的第一个结点。

参考资料来源：百度百科--二叉树

关于树的几类计算

求解方法归纳：

（1）求解二叉树中节点个数的方法。

非空二叉树上叶子结点数等于双分支结点数加1，即

在一颗二叉树中，所有结点分支数等于所有结点度之和

是度为0的结点, 是度为1的结点, 是度为2的结点。

对于一棵具有n个结点的树，则树中所有结点的度数之和为n-1。

树中所有结点度之和

（2）求解完全二叉树中节点个数的方法。

已知，完全二叉树形体一定，所以结点数n确定时，其树形就确定了，可以计算出高度

（3）求解满二叉树中节点个数的方法。

满二叉树是最严格的二叉树，当结点数n确定时，其树形就确定了，可以计算出高度 由满二叉树的性质可知：

度为1的结点数：

总结点数：

度为0的结点数：

度为2的结点数：

在度为4的树中，若有20个度为4的节点，10个度为3的节点，1个度为2的节点，10个度为1的节点，则树T的叶节点个数是？

设二叉树有2n个节点，且m

A. n个度为0 B. 2m个度为0 C. 2m个度为1 D. 2m个度为2

【2009年计算机联考真题】若一颗完全二叉树有768个结点，则该二叉树叶节点个数为？

已知一棵有2011个结点的树，其叶结点个数是11个，该树对应的二叉树中无右孩子的结点的个数是？

在二叉树中有两个结点m和n,如果m是n的祖先,可以找到从m到n的路径的遍历方式是?

线索二叉树是一种( C )结构？

A. 逻辑

B. 逻辑和存储

C. 物理

D. 线性

（）的遍历仍需要栈的支持

A. 前序线索树

B. 中序线索树

C. 后序线索树

D. 所有线索树

对于一个 二叉树 ，如下图所示：

二叉树各种计算公式总结 二叉树的计算方法

我们可以有下面的假设， 设叶子节点个数为n 0， 度为1的节点个数为n 1， 度为2的节点个数为n 2 。

那么就有： n 0 +n 1 +n 2 =n

二叉树各种计算公式总结 二叉树的计算方法

又由于除了根节点以外，每一个结点都占有一个边，

那么就有：n-1=2n 2 +n 1

(1)当n 1 =0时，n=2n 0 -1所以n 0 =(n+1)/2。这里的n为奇数。

(2)当n 1 =1时，n=2n 0 所以n 0 =n/2。这里的n为偶数。

含有二十个节点的平衡二叉树的最大深度为（）

A. 4 B. 5 C. 6 D. 7

画出一个二叉树，使它既满足大根堆的要求又满足二叉排序树的要求

这道题看似是一道开放性的题，所以看着觉得很奇怪。然而这是因为我不知道大根堆是什么东西的原因。

所谓大根堆，下面是百度百科的解释：

最大堆是堆的两种形式之一。

根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆（大顶堆）。

大根堆要求根节点的关键字既大于或等于左子树的关键字值，又大于或等于右子树的关键字值。

而且，大根堆还要求树是完全二叉树。

数据结构老师没教过堆排序的弱渣飘过

然后就很简单了，首先，根节点比左右节点都大，而且二叉排序树要求根节点比右节点小，那么没有右节点就得了。然后因为又要求必须是完全二叉树，所以这棵树只能有两个节点，一个根节点，一个是根节点的左节点。

所以这棵树是唯一的！！！

本以为是唯一的，但是经道友指点，还可以是只有一个根节点的情况，那么就是这两种情况啦！

二叉树中，80个叶子结点 70个度为1的结点 总结点数怎么算

二叉树总节点数目为N,有 N=N0+N1+N2---(公式1)；二叉树度数总和为0*N0+1*N1+2*N2 ；而由二叉树的图形可以看出除根节点外,每个结点上方对应着一个度（为更形象,可以理解成结点自己的头上有一根“绳子”挂着自己）（可验证当仅有根节点是也满足这个规律）,所以结点总数比度数少1,则有N+1=N1+2*N2(公式2)；

公式1代入公式2即可得出：N0=N2+1

N2=N0-1=80-1=79

N=N0+N1+N2=80+70+79=229

二叉树的叶子节点数公式是什么？

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

设叶子节点数为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、树的深度：也称为树的高度，树中所有结点的层次最大值称为树的深度。

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