二叉树Ⅰ · 树型结构 · 二叉树 · 满二叉树 · 完全二叉树 · 二叉树的性质 · 二叉树的存储

一、树型结构（了解）

1.1 引入和特点

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

它具有以下的特点：

• 有一个特殊节点，称为根节点，根节点没有前驱节点.
• 除了根节点外，其余节点被分成 M 个互不相交的集合，其中每个集合又是一棵与树类似的子树。每颗子树的根节点有且只有一个前驱，可以有 0 个或者多个后驱。
• 树是递归定义的。

• 子树是不相交的。
• 除了根节点外，每个节点有且仅有一个父节点。
• 一棵 N 个节点的树，有 N-1 条边。

1.2 概念（重要）

节点的度： 一个节点含有的子树的个数称为该节点的度；如上图（A 节点为 6）.

树的度： 一棵树中，最大的节点的度称为树的度；如上图（树的度为 6）.

叶子节点或终端节点： 度为 0 的节点称为叶节点；如上图（ B C H I P Q K L M N 等节点为叶节点）.

双亲节点或父节点： 若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图（ A 是 B 的父节点）.

孩子节点或子节点： 一个节点含有的子树的根节点称为该节点的子节点；如上图（ B 是 A 的孩子节点）.

根节点： 一棵树中，没有双亲节点的节点；如上图（ A ）.

节点的层次： 从根开始定义起，根为第 1 层；根的子节点为第 2 层，依此类推。

树的高度： 树中节点的最大层次；如上图（树的高度为 4）.

树的深度： 深度是要相对节点来说的.

树的以下概念只需了解，在看书时只要知道是什么意思即可：

非终端节点或分支节点： 度不为0的节点； 如上图：D、E、F、G…等节点为分支节点.

兄弟节点： 具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点.

堂兄弟节点： 双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点.

节点的祖先： 从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先.

子孙： 以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙.

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

1.3 树的表示形式（了解）

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦，实际中树有很多种表示方法，例如：双亲表示法、孩子表示法、孩子兄弟表示法等等。

我们这里就简单的了解其中最常用的孩子兄弟表示法。

class Node {
	//树中存储的数据
	int value;
	//第一个孩子引用
	Node firstChild;
	//下一个兄弟引用
	Node nextBrother;
}
1
2
3
4
5
6
7
8

---

二、二叉树（重点）

2.1 概念

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

二叉树的特点：

1. 每个节点最多由两颗子树，即二叉树不存在度大于 2 的节点.
2. 二叉树的子树有左右之分，其子树的次序不能颠倒，因此二叉树是有序树。

2.2 二叉树的基本形态

上图给出了几种特殊的二叉树形态，从左往右依次是：空树、只有根节点的二叉树、节点只有左子树、节点只有右子树、节点的左右子树均在。

一般二叉树都是由上述基本形态结合而形成的。

2.3 两种特殊的二叉树

满二叉树

一个二叉树，如果每一层的节点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为 K，且节点总数是 2^k-1，则它就是满二叉树。

完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n 个节点的二叉树，树中的每个节点和深度为 K 的满二叉树中编号从 1 到 n 的节点一一对应，这时候就能称之为完全二叉树。
满二叉树是一种特殊的完全二叉树。

2.4 二叉树的性质

1. 如果规定根节点的层数为 1，则一棵非空二叉树的第 i 层上最多有 2^( i - 1 ) 个节点。
2. 若规定只有根节点的二叉树的深度为 1，则深度为 K 的二叉树的最大节点数是 2^k - 1。
3. 对于任何一棵二叉树，如果其叶节点个数为 n0，度为 2 的非叶子节点个数为 n2，则有 n0 = n2 + 1。
4. 具有 n 个节点的完全二叉树的深度 k 为 log2(n + 1) 上取整。2^k = n+1
5. 已知孩子节点下标是 i，求父亲节点的下标：（ i - 1 ）/ 2；已知父亲节点下标为 i，求孩子节点：左孩子节点下标（2 * i + 1）右孩子节点下标（2 * i + 2）。

练习题：
假设一棵完全二叉树中总共有1000个节点，
则该二叉树中_____个叶子节点，_____个非叶子节点，_____个节点只有左孩子，_____个只有右孩子。

解法：
其实可以把规模是1000个结点的二叉树，缩小成10个结点。
二叉树的规模缩小了，但是树的形状，树的性质还是没有改变。
10个结点的二叉树有5个叶子节点，5个非叶子节点，1个节点只有左孩子，0个只有右孩子。
所以1000个结点，就有500个叶子结点，500个非叶子结点，1个节点只有左孩子，0个只有右孩子。
1
2
3
4
5
6
7
8
9

2.5 二叉树的存储

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

二叉树的链式存储是通过一个一个节点引用起来的，常见的表示方式有二叉和三叉表示方法，具体如下：

//孩子表示法
class Node {
	int val;	//数据域
	Node left;	//左孩子的引用，常表示以左孩子为根的整棵左子树
	Node right;	//右孩子的引用，常表示以右孩子为根的整棵右子树
}

//孩子双亲表示法
class Node {
	int val;		//数据域
	Node left;		//左孩子的引用
	Node right;		//右孩子的引用
	Node parent;	//当前节点的根节点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14