数据结构二叉树算法_二叉树节点数算法

一.什么是树

1. 定义：

树（Tree） 是n(n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中：

有且仅有一个特定的称为根（Root）的结点；

当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、......、Tn，其中每一个集合本身又是一棵树，并且称为根的子树。

2.树还需要强调以下两点：

n>0时根结点是唯一的，不可能存在多个根结点，数据结构中的树只能有一个根结点。

m>0时，子树的个数没有限制，但它们一定是互不相交的。

2. 结点：

结点是数据结构中的基础，是构成复杂数据结构的基本组成单位。

3. 结点的度：

结点拥有的子树数目称为结点的度。

4. 结点的关系

结点子树的根结点为该结点的孩子结点。相应该结点称为孩子结点的双亲结点。 同一个双亲结点的孩子结点之间互称兄弟结点。

如图：A为B的双亲结点，B为A的孩子结点。

结点B与结点C互为兄弟结点。

5. 结点层次及树的深度：

（1），从根开始定义起，根为第一层，根的孩子为第二层，以此类推。

（2），树中结点的最大层次数称为树的深度或高度。 如图树的深度为4。

二：二叉树

1. 定义：

二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。

2.二叉树特点：

（1）每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。

（2）左子树和右子树是有顺序的，次序不能任意颠倒。

（3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

3.二叉树的性质：

4.满二叉树：

在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

5.满二叉树的特点：

（1）叶子只能出现在最下一层。出现在其它层就不可能达成平衡。

（2）叶子结点的度一定是2。

（3）在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

6.完全二叉树特点：

（1）叶子结点只能出现在最下层和次下层。

（2）最下层的叶子结点集中在树的左部。

（3）倒数第二层若存在叶子结点，一定在右部连续位置。

（4）如果结点度为1，则该结点只有左孩子，即没有右子树。

（5）同样结点数目的二叉树，完全二叉树深度最小。

（6）注：满二叉树一定是完全二叉树，但反过来不一定成立。

7.二叉树的储存结构：

二叉树的顺序存储结构就是使用一维数组存储二叉树中的结点，并且结点的存储位置，就是数组的下标索引。

三.二叉树的遍历

1. 先序遍历：先序遍历可以想象为，一个小人从一棵二叉树根节点为起点，沿着二叉树外沿，逆时针走一圈回到根节点，路上遇到的元素顺序，就是先序遍历的结果。

2. 中序遍历：中序遍历可以看成，二叉树每个节点，垂直方向投影下来（可以理解为每个节点从最左边开始垂直掉到地上），然后从左往右数，得出的结果便是中序遍历的结果。

3. 后序遍历：就是围着树的外围绕一圈，如果发现一剪刀就能剪下的葡萄（必须是一颗葡萄）（也就是葡萄要一个一个掉下来，不能一口气掉超过1个这样），就把它剪下来，组成的就是后序遍历了。

4. 层序遍历：层次遍历很好理解，就是从根节点开始，一层一层，从上到下，每层从左到右，依次写值就可以了。

5.二叉树的访问次序可以分为四种：

（1），前序遍历 根结点 > 左子树 > 右子树。

（2），中序遍历 左子树> 根结点 > 右子树。

（3），后序遍历 左子树 > 右子树 > 根结点。

（4），层序遍历 仅仅需按层次遍历就可以。

四：树的节点问题总结：

度：某个节点的子节点个数

叶结点：度为0的结点

度为4的树，说明该树中结点的子结点最多为4个

树中结点总个数=（所有的结点的度数)+1

∵ 在树中，除了根节点没有前驱结点，其他节点有且只有一个前驱节点(树的定义)

又∵ 父结点的‘度’是子结点的个数，而每个子结点前驱结点都是该父结点

结点的“度”加起来，就是把所有结点子结点的个数加起来，又因为，根结点没有父节点，所以所以没有把根结点算计进来，于是：树中结点总个数=（所有的结点的度数)+1(根节点)

（1），一个森林的所有结点数=（所有结点的度数+n(n棵树，每棵树只有一个根节点)

1.sum(所有结点个数)=20x4+10x3+1x2+10x1+1(根结点)=123个结点

2.sum(叶子节点个数)=123-20-10-1-10=82

（2） ，一个森林的所有叶子结点数=（所有结点的度数+n(n棵树，每棵树只有一个根节点)-m(度数非0的结点个数)

五.为什么计算总结点数时候要+1？(他人回答)

计算叶子结点时不需要减掉根结点-1？ 是因为结点数＝总度数+1 度数来自于父结点，度数不包括父结点自己。想计算该父结点需要其上一层的度数，该父结点占了上一层的度分之一（度≥1，说法不准确 只为了方便理解） 所以从下往上，算到根结点时，因为根结点没父结点，所以得+1（注意！此时加1只是因为第二层来源于根结点的度，记住公式右侧是总度数+1。根结点一样有度，只不过没有父结点所以没被计算，树是有根结点的，+1是不能让第二层和根结点所在的第一层断层，因为根结点的度必须使用，不然第二层就会成几个独立的树，成了森林。假设根结点的度为4，那么根结点也是题干中的那20个度数为4的结点中的一个，也就是为什么计算时不用再减1，20×4+10×3+1×2+10×1这是度数，20+10+1+10这是度数不为0的结点数，总结点数-度数不为0的结点数＝叶子结点数）。

六.再见