树
树的介绍
什么是树
-
树是一种递归数据结构，包含一个或多个数据节点的集合，其中一个节点被指定为树的根，其余节点被称为根的子节点。
-
除根节点以外的其他节点均被划分为多个非空集，其中每个空集都称为子树。
-
树的节点或者在它们之间保持父子关系，或者它们是姐妹节点。
-
在一般树中，一个节点可以有任意数量的子节点，但只能有一个父节点。
-
下图显示了一棵树，其中节点A是树的根节点，而其他节点可以视为A的子节点。
基本术语
- 根节点 ：-根节点是树层次结构中的最高节点。 换句话说，根节点是没有任何父节点的节点。
- 子树 ：-如果根节点不为空，则树
T1，T2和T3被称为根节点的子树。 - 叶子节点 ：-没有任何子节点的树的节点称为叶子节点。 叶节点是树的最底部节点。 普通树中可以有任意数量的叶节点。 叶节点也可以称为外部节点。
- 路径 ：-连续边的顺序称为路径。 在上图所示的树中，到节点E的路径为
A→B→E。 - 祖先节点 ：- 节点 的祖先是从根到该节点的路径上的任何前任节点。 根节点没有任何祖先。 在上图所示的树中，节点F具有祖先B和A。
- 程度 ：-节点的程度等于一个节点具有的子代数。 在上图所示的树中，节点B的度为2。叶节点的度始终为0，而在完整的二叉树中，每个节点的度等于2。
- 等级号 ：-树的每个节点被分配一个等级号，使得每个节点都比其父级高一个等级。 树的根节点始终位于级别0。
树的静态表示
#define MAXNODE 500
struct treenode {
int root;
int father;
int son;
int next;
}
树的动态表示
struct treenode
{
int root;
struct treenode *father;
struct treenode *son
struct treenode *next;
}
树的类型
树数据结构可以分为六个不同的类别。
普通树
通用树按层次结构顺序存储元素，其中顶级元素始终作为根元素出现在级别0中。 除根节点外，所有节点都以一定数量的级别存在。 存在于相同级别上的节点称为同级，而存在于不同级别上的节点则表现出它们之间的父子关系。 一个节点可以包含任意数量的子树。 每个节点包含3个子树的树称为三叉树。 每个节点包含N个子树的树称为N叉树。
森林
森林可以定义为一组不相交的树，可以通过删除根节点和将根节点连接到第一级节点的边来获得。
二叉树
二叉树是一种数据结构，其中每个节点最多可以有2个子节点。 最顶层的节点称为根节点。 子节点为0的节点称为叶节点。 二叉树用于表达式评估等应用程序中。 在本教程的后面，我们将详细讨论二叉树。
二叉搜索树
二叉搜索树是有序的二进制树。 左子树中的所有元素均小于根元素，而右子树中的所有元素均大于或等于根节点元素。 二叉搜索树用于计算机科学领域的大多数应用程序中，例如搜索，排序等。
性质：中序遍历之后是升序排列的
表达树
表达式树用于评估简单的算术表达式。 表达式树基本上是一个二叉树，其中内部节点由运算符表示，而叶节点由操作数表示。 表达式树被广泛用于求解诸如\(（a + b）*（ab）\)的代数表达式。 考虑以下示例。
问：使用以下代数表达式构造一个表达式树 。
\(（a + b）/（a * b-c）+ d\)
比赛树
比赛树用于记录两名球员之间每一轮比赛的胜者。 锦标赛树也可以称为选择树或获胜者树。 外部节点代表正在进行比赛的玩家，而内部节点代表进行比赛的获胜者。 在最高级别，锦标赛的获胜者是树的根节点。
例如，如下所示在四个玩家之间进行的国际象棋比赛的树。 但是，左子树的获胜者将与右子树的获胜者对战。
各种常用的树
什么是二叉树（Binary Tree）
二叉树是一种特殊类型的通用树，其中每个节点最多可以有两个孩子。 二叉树通常分为三个不相交的子集。
- 节点的根
- 左子树，它也是二叉树。
- 右二叉子树
二叉树是每个节点最多有两个子节点的树。
二叉树的叶子节点有0个字节点，二叉树的根节点或者内部节点有一个或者两个字节点。
什么是二叉搜索树（Binary Search Tree）
二叉查找树又叫二叉搜索树，
它或者是一棵空树，或者是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉搜索树。
一个印象比较深的二叉搜索树就是问手机号。
假设你遇到一个美女想问他手机号，但是美女一般不告诉你数字。她只回答是否题。
那么你可以问她不超过14个问题就可以知道她手机号了。
假定手机号最大值是1000 0000 0000
是否大于500 0000 0000，开始分叉。
如果大于500 0000 0000，那么是否大于750 0000 0000。。。
如果小于500 0000 0000，那么是否大于250 0000 0000。。。
以此类推，这就是一个典型的二叉搜索树。看起来很神奇，其实源自于一种巧妙的数学。
什么是平衡二叉树（AVL Tree）
AVL树全称G.M. Adelson-Velsky和E.M. Landis，这是两个人的人名。
AVL树定义：
所有节点的左右子树的高度差小于1的二叉树。
如下图
根节点左边高度是3，因为左边最多有3条边；右边高度而2，相差1.
根节点左边的节点50的左边是1条边，高度为1，右边有两条边，高度为2，相差1。
什么是B树（B tree）
B树也叫或B-树、B_树。
B树英文官方定义：
1、Every node has at most m children.
2、Every non-leaf node (except root) has at least [m/2] child nodes.
3、The root has at least two children if it is not a leaf node.
4、A non-leaf node with k children contains k − 1 keys.
5、All leaves appear in the same level.
我理解的B树定义：
1、根结点至少有两个子节点；
2、每个非叶子节点并且非根节点最少有m/2个，即内部节点的字节点个数最少也有m/2个。
3、根节点最少有两个字节点。
4、有k个关键字(关键字按递增次序排列)的非叶结点恰好有k+1个孩子。
5、所有叶子节点在同一层，即所有叶子几点高度一致。
如下图（B树的内部节点可以存放数据，类似ZK的中间节点一样。B树不是每个节点都有足够多的子节点）
什么是B+树（B+ tree）
B+树是从B树衍生而来。
跟B的不同：
1、B+树非叶子节点不存放数据，只存放keys。
2、B+树的叶子节点之间存在指针相连，而且是单链表
如下图（其实B+树上二叉搜索树的扩展，二叉搜索树是每次一分为二，B树是每次一分为多）
现代操作系统中，磁盘的存储结构使用的是B+树机制，mysql的innodb引擎的存储方式也是B+树机制
