树的基本概念与结构：

1、树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。n=0 时称为空树。n>0 时，有限集的元素构成一个具有层次感的数据结构。

区别于线性表一对一的元素关系，树中的节点是一对多的关系。树具有以下特点：

· n>0 时，根节点是唯一的，不可能存在多个根节点。

· 每个节点有零个至多个子节点

· 除了根节点外，每个节点有且仅有一个父节点。根节点没有父节点

如图，A为整个树的根节点。而B，C，D可以看做子树的根节点，在下面分别长出三棵子树，每颗子树有不同的子节点。

树有许多相关的术语与概念，在学习树的结构之前，我们要熟悉这些概念。

· 子树：除了根节点外，每个子节点都可以分为多个不相交的子树。

· 有序树：树中节点各子树之间的次序是重要的，不可以随意交换位置。 

· 无序树：树种节点各子树之间的次序是不重要的。可以随意交换位置。

 

· 叶节点和终端节点：没有子树，度为零的节点，如图中E、F等节点。

· 双亲结点或父节点：如图，C为G的父节点。

· 孩子节点或子节点：如图，G为C的子节点。

 

· 分支节点：除了叶子节点之外的节点，也即是度不为 0 的节点。 

· 内部节点：除了根节点之外的分支节点。

· 兄弟节点：拥有相同父节点的节点称为兄弟节点，如图中E、F等节点。

 

· 树的度：一棵树中最大的节点的度称为树的度。

· 节点的度：一个节点含有的子树的个数，叫做该节点的度。

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

· 树的高度或深度：树中节点的最大层次，如图，高度为3。

 

· 祖先：从跟到该节点所经分支上的所有节点。A是所有节点的祖先。

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

2、树的表示

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

struct  Node

{

    struct  Node  *left; // 指向左子树结点

    struct  Node  *right; // 指向右子树结点

    int  data; // 结点中的数据域

};

二叉树基本概念：

1、二叉树的概念

二叉树（Binary Tree）是由n个结点组成的一个有限集合（节点n≥0），该集合或者为空（n=0），或者是由一个根节点与两棵互不相交的、分别称为左子树和右子树的二叉树组成（n>0）。很明显该定义属于递归定义，所以有关二叉树的操作使用递归往往更容易理解和实现。

2、二叉树的特点

· 每个节点最多有两棵子树，即不存在超过度为2的节点。

· 二叉树的子树有左右之分，且左右不能颠倒。

二叉树的性质：

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

若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1。

任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0＝n2＋1

若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=Log2(n+1)

二叉树的存储：

二叉树的存储有两种，顺序存储与链式存储。

顺序存储：

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费，而现实中使用中只有堆才会使用数组来存储。

为了在存储结构中能得到父子结点之间的映射关系，二叉树中的结点必须按层次遍历的顺序存放。具体是：

完全二叉树: 自根结点起从上往下、从左往右依次存储。

非完全二叉树: 先将它变换为完全二叉树，空缺位置用某个特殊字符代替（比如#），然后仍按完全二叉树的存储方式存储。

假设将一棵二叉树按此方式存储到数组后，左子结点下标=2倍的父结点下标+1，右子节点下标=2倍的父结点下标+2。若数组某个位置处值为#，代表此处对应的结点为空。

因此可以得出结论：顺序存储非常适合存储接近完全二叉树类型的二叉树，对于一般二叉树有很大的空间浪费，所以对于一般二叉树，一般用下面这种链式存储。

注意：空节点的地方在数组中要空出来，不然无法模拟出树的结构。

 

链状存储：

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。

链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，高阶数据结构如红黑树等会用到三叉链。对每个结点，除数据域外再多增加左右两个指针域，分别指向该结点的左孩子和右孩子结点，再用一个头指针指向根结点。

从上面二叉树的递归定义可以看出，二叉树或为空，或为一个根结点加上两棵左右子树，因为两棵左右子树也是二叉树也可以为空，所以二叉树有5种基本形态与3种特殊形态。

基本形态：

特殊形态：

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

 

完全二叉树：完全二叉树是由满二叉树引出的。满二叉树要求每一层的节点数都达到最大值，完全二叉树仅要求除最后一层外的节点数达到最大值，也就是说最后一层可以不满。满二叉树是一种特殊的完全二叉树。

 

斜树：所有节点都只有左子树的二叉树叫做左斜树，所有节点都只有右子树的二叉树叫做右斜树。左斜树和右子树统称为斜树。斜树已经退化成线性结构，二叉树在查找上表现出来优异性能在斜树得不到体现。