关于树的几类计算

求解方法归纳：
（1）求解二叉树中节点个数的方法。
非空二叉树上叶子结点数等于双分支结点数加1，即
在一颗二叉树中，所有结点分支数等于所有结点度之和
是度为0的结点,是度为1的结点,是度为2的结点。
对于一棵具有n个结点的树，则树中所有结点的度数之和为n-1。
树中所有结点度之和

---

（2）求解完全二叉树中节点个数的方法。
已知，完全二叉树形体一定，所以结点数n确定时，其树形就确定了，可以计算出高度

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

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

---

题目1：

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

答：
我们知道,树的节点的个数=树的度+1
于是树的节点个数
但同时，树的节点个数也可以写成是：叶子节点数+度为1的节点数+…+度为4的节点数,即N = N0 + 20 + 10 + 1 + 10 ，其中N0为叶子节点个数
由上述两个式子就可解出叶子节点个数为82了。

题目2：

设二叉树有2n个节点，且m<n，不可能存在（）的节点
A. n个度为0 B. 2m个度为0 C. 2m个度为1 D. 2m个度为2

这道题涉及到的知识为：:
二叉树中，叶节点的数目N0等于度为2的节点数目N2加一。 即 N0 = N2 + 1
设度为i的节点的数量为Ni，则 2n = N0 + N1 + N2
又因N0 = N2 + 1，故2n = N1 + 2N2 + 1
因此可以推算出 N1 = 2n - 2N2 -1 ，必为奇数，由此直接判断本题选C

题目3:

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

该题有两种算法。
算法一：
完全二叉树中最后一个树枝节点的编号为n/2
因此该完全二叉树最后一个数值结点的编号为768/2=384（从1开始编号），所以叶子节点个数为768-384=384
算法二：
设N为二叉树总节点数，Ni 为 度为i的节点数
N = N0 + N1 + N2， N0 = N2 + 1 ，即 N = N1 + 2N2 + 1
因此768 = N1 + 2N2+1，而N1只能等于0或1（完全二叉树中）
所以可以解出N1 = 1，N2 = 383，所以N0 = N2+1=384

题目4:

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

题目

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

这道题想了我很久，答案是 后序遍历
似乎有点难以理解，试想先序遍历、中序遍历、层次遍历都会遍历到m和n啊，层次遍历和路径无关，自然不选，但是先序和中序为何不行？

这就得先看清楚，题目中所写为 m是n的祖先，祖先可不仅仅只能是父节点。如果是父节点，那么不管哪一种都好说。而祖先的话，试想 n是m的第18代儿子，假设又是满二叉树，天呐，从记录下m开始到找到n，中间可能性有多少？2的18次方种可能，显然全部记录下来然后从中选一个是不现实的吧，所以从上往下找，这种思路本就是不可行的。（没说清楚？和这个问题很像，可以参考：戳）打个更简单的比方，一个皇帝想从几十亿的人中找到你是很难的，但是你想找那个皇帝，却是很简单的。

而既然排除了从上往下，也就排除了先序和中序，那后序为什么可以呢？因为后序遍历，无论是在左子树还是右子树，在返回的路上，都必然会经过祖先节点，所以，不管是不是递归的方法，都可以找得到这条路径。
非递归求解该问题的伪代码见第八题，只要从栈中提出n，则栈里面剩下的就是从根节点到n的路径节点。

题目6:

线索二叉树是一种( C )结构？
A. 逻辑
B. 逻辑和存储
C. 物理
D. 线性

题目7:

（）的遍历仍需要栈的支持
A. 前序线索树
B. 中序线索树
C. 后序线索树
D. 所有线索树

这是一道很简单的题目，显然选C，因为后序线索树可能不能根据线索找到直接后继节点。
这里小结一下：
先序线索二叉树可以求先序后继
先序线索二叉树不可以求先序前驱
中序线索二叉树可以求中序后继
中序线索二叉树可以求中序前驱
后序线索二叉树不可以求后序后继
后序线索二叉树可以求后序前驱

后序遍历二叉树，如果使用递归很简单，就三五句话

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

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

那么就有：n₀+n₁+n₂=n

又由于除了根节点以外，每一个结点都占有一个边，
那么就有：n-1=2n₂+n₁

综合上面的两个公式得到：
叶子结点和二度结点数目关系：n₀=n₂+1

---

如果这是一个完全二叉树，那么一度结点的个数是有限的，要么为0要么为1。所以可以最后得到结点总数目和叶子结点的关系：

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

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

综上所述：
对于完全二叉树，叶子结点和结点总数的关系是：
一个具有n个节点的完全二叉树,其叶子节点的个数n₀为: (n+1)/2 向下取整。

---

题目8:

含有二十个节点的平衡二叉树的最大深度为（）
A. 4 B. 5 C. 6 D. 7

这道题涉及到的就是平衡二叉树里的一个规律：
假设以Nh表示深度为h的平衡树中含有的最少节点数，那么N0 = 0 ,N1 = 1, N2 = 2,并且有Nh = Nh-1 + Nh-2 + 1
所以这道题很明显了，N0 = 0, N1 = 1, N2 = 2, N3 = 4, N4 = 7, N5 = 12, N6 = 20
所以选 C

题目10：

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

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

最大堆是堆的两种形式之一。
根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆（大顶堆）。
大根堆要求根节点的关键字既大于或等于左子树的关键字值，又大于或等于右子树的关键字值。

而且，大根堆还要求树是完全二叉树。
数据结构老师没教过堆排序的弱渣飘过
然后就很简单了，首先，根节点比左右节点都大，而且二叉排序树要求根节点比右节点小，那么没有右节点就得了。然后因为又要求必须是完全二叉树，所以这棵树只能有两个节点，一个根节点，一个是根节点的左节点。
所以这棵树是唯一的！！！
本以为是唯一的，但是经道友指点，还可以是只有一个根节点的情况，那么就是这两种情况啦！