二叉树第一期：树与二叉树的概念

一、树   

1.树的定义

与线性表不同，树是一种非线性的数据结构，由N(N>=0)个结点组成的具有层次关系的集合；因其形状类似生活中一颗倒挂着的树，故将其数据结构称为树。

2.树的相关概念

总结：

• 一个树，其任意子树是互不相交的，否则就不叫树，而是图，这一树形结构，如B、C、D为根组成的树，不存在相交情况。
• 任意一个树都可以看成根和子树，子树又可以看成，根和子树，所以树这一结构，是由递归搭建的。

3.树的表示

对树这一结构，有明确的了解后，又有一个新的问题，我们该如何的去表示的树的结构呢？常见的有孩子表示法，双亲表示法，孩子双亲表示法，孩子兄弟表示法；这里将介绍最好理解的孩子表示法，和优点明显的孩子兄弟表示法

i.孩子表示法

#define MAX 10 // 已知树的最大的深度

typedef int TDatetype;

typedef struct Tree
{
	TDatetype date;
	struct Tree* child[MAX];
}Tree;

ii.左孩子右兄弟表示法

typedef int TDatetype;

typedef struct Tree
{
	TDatetype date;
	struct Tree* child;
	struct Tree* brother;
}Tree;

 4.树的实际应用

我们文件的存储方式就是以树这一结构存储，每一个盘即为一个树，所有盘则组成一个森林，下面则是Linux系统下，文件的存储结构。

二、二叉树

1.二叉树的定义

在树的定义基础上，树的度最大不超过2的(每个结点的度最大不超过2的)，即为二叉树。（注：二叉树有左孩子右孩子之分）

2.特殊的二叉树

i.满二叉树

满二叉树的定义：树的深度为h，每一层都达到含有结点的最大个数，即第x(0<x<=h)层，结点个数 = 2^(x-1)；

ii.完成二叉树

完全二叉树的定义：树的深度为h，前h-1层，结点个数达到最大值，第h层，从左到右有连续的结点。

3.二叉树的性质

• 第H层结点个数：2^(H-1)
• 高度为H的二叉树，所含有结点个数的最大值为2^H-1
• N个结点的满二叉树，其高度为以2为底，log(N+1)
• N个结点的完全二叉树，其高度为以2为底，log(N+X+1)，X为相同高度的满二叉树与完全二叉树的结点个数差的绝对值
• 终端结点的个数  = 度为2的结点个数 + 1

4.二叉树的表示

i.二叉树的顺序结构

二叉树的顺序结构：将一颗二叉树的数据，以层为顺序，依次存储在数组中（保留空结点的位置）。

typedef int BTDateType; // 重定义树的数据类型

typedef struct BinaryTree
{
	BTDateType* date; // 动态顺序表
	int size; // 当前顺序表存储数据的个数
	int capacity; // 当前顺序表的容量大小
}BinaryTree;

为什么要这么设计呢？

因为我们通过数组下标，可以得出其父亲或者两个孩子的结点位置；

1. 某结点左孩子的下标 = 该结点的下标 * 2 + 1
2. 某结点右孩子的下标 = 该结点的下标 * 2 + 2
3. 某结点的父亲下标     = (该结点的下标 - 1) / 2

读者，若不相信，可以以上面示图为例子，代入数据，进行自我验证！！！

• 根据此特性，
• 首先：我们就可以理解了，为什么要留着空结点的位置，而不是直接把数据依次存入~
• 最后：可以得出结论适合于存储完全二叉树，而不适合存储普通二叉树，因为普通二叉树，会造成大量的空间浪费。

ii.二叉树的链式结构

二叉树的链式结构，声明如下：孩子不存在，则用NULL表示；

typedef int BTDatetype;

typedef struct BinaryTree
{
	BTDatetype date; // 数据
	struct Tree* lift; // 左孩子
	struct Tree* right; // 右孩子
}BT;