数据结构（Java）：树&二叉树

目录

1、树型结构

1.1 树的概念

1.2 如何判断树与非树

 1.3 树的相关概念

1.4 树的表示形式

1.4.1 孩子兄弟表示法

2、二叉树

2.1 二叉树的概念

2.2 特殊的二叉树

 2.3 二叉树的性质

2.4 二叉树的存储

2.5 二叉树的遍历

---

1、树型结构

1.1 树的概念

树型结构是一种非线性数据结构，是由有限个节点构成的具有层次关系的集合，它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

树型结构具有以下特点：

1. 有一个特殊的结点，称为根结点，根结点没有前驱结点
2. 除根节点外，每个节点都只有一个前驱，可以有多个或0个后继
3. 树是递归定义的
4. 树型结构中，子树之间不能有交集，否则就不是树型结构

1.2 如何判断树与非树

树满足以下性质：

1. 树的子树是不可相交的

2. 在树中，除根节点外，每个节点有且仅有一个父节点

3. N个节点的树具有N-1条边 

 1.3 树的相关概念

• 结点的度：一个结点含有子树的个数称为该结点的度
• 树的度：一棵树中，所有结点度的最大值称为树的度
• 叶子结点：度为0的节点，即叶子结点没有孩子
• 双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点
• 子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点
• 根结点：一棵树中，没有双亲结点的结点
• 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
• 树的高度或深度：树中结点的最大层次

1.4 树的表示形式

树有很多种表示方式，如：双亲表示法， 孩子表示法、孩子双亲表示法、孩子兄弟表示法

我们这里只介绍最常用的孩子兄弟表示法。

1.4.1 孩子兄弟表示法

孩子兄弟表示法，即左孩子右兄弟表示法。

一个节点，只存储数据和其第一个孩子、第一个兄弟的引用。

---

2、二叉树

2.1 二叉树的概念

二叉树由n个结点构成的有限集(n≥0)，n=0时为空树，n>0时为非空树。

二叉树可以为空树。

二叉树是一种特殊的树，二叉树的特点是每个节点最多有两个子节点（也就是说二叉树的度最多为2），并且这两个子节点有明确的左右之分，不能颠倒。

---

2.2 特殊的二叉树

两种特殊的二叉树：

1. 满二叉树：一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。如果一棵二叉树的层数为k，且结点总数是 ，则它就是满二叉树。
2. 完全二叉树：对于深度为K的，有n 个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。

注意：满二叉树是一种特殊的完全二叉树。 

---

 2.3 二叉树的性质

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 (i>0)个结点

2. 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 (k>=0)

3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的结点个数为n2,则有：n0＝n2＋1

4. 具有n个结点的完全二叉树的深度k为 上取整

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i 的结点有（存在的情况下）：

• 父节点下标：(i-1)/2
• 左孩子下标：2i+1
• 右孩子下标：2i+2

6.节点个数 = 分支数+1（二叉树和树均适用） 

7.对于完全二叉树，度为1的节点只有1个或0个

---

2.4 二叉树的存储

二叉树的存储结构分为：顺序存储和类似于链表的链式存储。

二叉树的链式存储是通过一个一个的节点引用起来的，常见的有孩子表示法、孩子双亲表示法。

孩子表示法：

孩子双亲表示法：

---

到这里，我们再来回顾下二叉树的概念：

二叉树是：

1. 空树
2. 非空：根节点、根节点的左子树、根节点的右子树组成的

可以看出二叉树定义是递归式的。 

---

2.5 二叉树的遍历

遍历是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如：打印节点内容、节点内容加 1)。

• 前序遍历：依次访问：根节点---左子树---右子树
• 中序遍历：依次访问：左子树---根节点---右子树
• 后序遍历：依次访问：左子树---右子树---根节点
• 层序遍历：从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

---

OK~本次博客到这里就结束了，

感谢大家的阅读~欢迎大家在评论区交流问题~

如果博客出现错误可以提在评论区~

创作不易，请大家多多支持~