【数据结构初阶】第七节.树和二叉树的性质

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

一、树

1.1 树的概念

1.2 树的结点分类

1.3 结点之间的关系

1.4 树的存储结构

1.5 其他相关概念

 二、 二叉树

2.1 二叉树的概念

2.2 特殊的二叉树

2.3 二叉树的性质

2.4 性质的相关习题

总结

---

---

前言

今天我们将进入到树与二叉树的相关内容当中，本节内容讲述了二叉树和树的有关性质和概念；

让我们一起进入到今天的学习当中吧！！！！！！！！！！

---

一、树

1.1 树的概念

这是现实世界的树

而我们这里所说的树，其实是一种特殊的数据结构 

之前我们学习的不管是顺序表还是链表、队列、栈，都是一对一的线性结构。但在数据生活中还有很多一对多的情况，所有我们就要用到这种一对多的数据结构——树；

树(Tree)是n（n≥0）个结点的有限集。n=0时称为空树。

在任意一颗非空树中：

 （1）有且仅有一个特定的称为根（root）的结点
（2）当n＞1时，其余结点可分为m（m＞0）个互不相交的有限集 T 1 , T 2 , . . . , T m ；

其中每一个集合本身又是一棵树，并且称为根的子树；

 有两个点需要注意一下：  

1. 树是递归定义的——也就是说树的定义之中还用到了树的定义；
2. 树形结构中，子树之间不能有交集，否则就不是树形结构；

解释一下这两点：

比如这是一个树

 下图的子树T1和T2就是根结点A的子树。当然，D,G,H,I组成的树又是B为结点的子树，E、J、F组成的树是C为结点的树的子树。 

一些非树的例子 ：

 注：上面三个就不是树结构，只有右下角的那个称为树型结构；

---

1.2 树的结点分类

树的结点包含一个数据元素及若干指向其子树的分支;结点拥有的子树数称为结点的度（Degree） 。

度为0的结点称为叶结点(Leaf)或终端结点；度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。

如下图，因为这棵树结点的度的最大值是结点D的度，为3，所以树的度为3.

---

1.3 结点之间的关系

1. 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点;
2. 孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点;
3. 兄弟节点：具有相同父节点的节点互称为兄弟节点;

图示说明：

节点的祖先：从根到该节点所经分支上的所有节点。如上图对于结点H来说，D、B、A都是他的祖先；

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：B的子孙有D、G、H、I；

---

1.4 树的存储结构

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

 我们观察后发现，任意一棵树，它的结点的第一个孩子如果存在就是唯一的。因此，我们设置两个结点引用，分别指向该结点的第一个孩子和该结点的右兄弟。 

结点结构如表所示：

代码分析：

 class TreeNode {

        int date;  // 数据域

        TreeNode firstchild;    // 该结点的第一个孩子

        TreeNode rightbrother;  // 该结点的右兄弟

}

那么下面的树：

就可以表示成：

这种表示其实就是把一棵复杂的树变成了一棵二叉树 ；

至于二叉树是什么？这也是咱们接下来要重点聊的内容了； 

---

1.5 其他相关概念

结点的层次：从一棵树的树根开始，树根所在层为第一层，根的孩子结点所在的层为第二层，依次类推;

树的高度或深度：树中节点的最大层次;

堂兄弟节点：双亲在同一层的节点互为堂兄弟;

堂兄弟节点图示解释：

 森林：由m（m>0）棵互不相交的树的集合称为森林；

有序树和无序树：如果树中结点的子树从左到右看，谁在左边，谁在右边，是有规定的，这棵树称为有序树；反之称为无序树。

（在有序树中，一个结点最左边的子树称为"第一个孩子"，最右边的称为"最后一个孩子"。）

 二、 二叉树

2.1 二叉树的概念

简单地理解，满足以下两个条件的树就是二叉树：

1. 本身是有序树；
2. 树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；

例如，图 1a) 就是一棵二叉树，而图 1b) 则不是。

 再深入的理解就是：

一棵二叉树是结点的一个有限集合，该集合：
1. 或者为空；
2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成；

图示举例：

  从上图可以看出：
1. 二叉树不存在度大于2的结点；
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树；

注意：

对于任意的二叉树都是由以下几种情况复合而成的：

---

2.2 特殊的二叉树

满二叉树：

如果二叉树中除了叶子结点，每个结点的度都为 2；

 完全二叉树 ：

如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布；

 如图 3a) 所示是一棵完全二叉树，图 3b) 由于最后一层的节点没有按照从左向右分布，因此只能算作是普通的二叉树。 

其实完全二叉树类似这下面这种情况：

 从中我们也可以发现一些规律，如果一个完全二叉树的某一个结点没有右子树，那么该结点一定没有左子树，有右子树就一定得有左子树。它从左到右一定是连续的，中间不能出现空的。 

注意：
一个慢二叉树一定是一棵完全二叉树，但完全二叉树不一定是满二叉树。

---

2.3 二叉树的性质

性质一：若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.

解析：

我们来观察下面的图形：

---

性质2：若规定根节点的层数为1，则深度为k的二叉树的最大结点数是2^k - 1 .（深度为k意思就是有k层的二叉树）

解析：

我们前面已经知道，一棵非空二叉树的第i层上2^(i-1) 个结点，那么k层的二叉树的结点树不就是首项是1、公比是2的等比数列求和吗？

---

性质3：对任何一棵非空二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有n0 ＝n2 ＋1；

解析：

 对于二叉树来说，我们会发现（除了根节点）对于每一个结点来说，都有其对应父结点分支指向它，假设树中分枝数为 B，那么总的结点数就是B+1；

设总结点数为n，度为0的结点（即叶子结点）个数为n0、度为1的结点个数为n1、度为2的结点个数为n2，那么就有n = n0 + n1 + n2；

同时分支数B = n1 + 2 * n2，B + 1 == n；

所以就有n0 = n2 + 1；

---

2.4 性质的相关习题

第一题：

解析：

该二叉树的结点数是奇数，而对于结点数是奇数的二叉树，像这样：

你会发现，该二叉树中度为1的结点数一个都没有，这不是偶然，你观察其他的的二叉树，会发现也有这样一个规律。

---

而对于结点数是偶数的二叉树呢？

你会发现结点数为偶数的二叉树，有且仅有一个度为1的结点；

综上所述：

 那么这样我们就可以开始算了： 设叶子结点即——度为0的结点数为n0，度为1的结点数为n1（n1 == 0)，度为2的结点数为n2（n2  = n0 -1)；

即399 = n0 + n1 + n2 = 2* n0 - 1 --->n0 = 200；

---

第二题：

 解析：

 2n说明结点数是偶数个，度为1的结点个数为1，2n = n0 + n1 + n2 = 1 + n0 + (n0 - 1)

即n0 == n，叶子结点个数为n ；

---

第三题：

解析：

二叉树的性质： 

非空二叉树的叶子结点等于双分支结点数加1；

---

第四题：

解析：

 对于这个题目就要用到我们的性质四了；

2^9 == 512，即log2(531 + 1) == 9.xx，向上取整即为10，所以答案就是B；

性质四：具有n个结点的完全二叉树的深度k为 log2(n+1)上取整；

---

性质五：对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点；
2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子；
3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子；

总结

今天的内容就介绍到这里，下一句我们将继续介绍有关二叉树的编程的有关问题，以及二叉树的常见操作的使用等等；让我们下一期再见吧！！！！！！！！！！