数据结构里"树"和"森林"的定义是什么?

树是一种特殊的图,这种图是连通的,并且边数恰好比顶点数少一

即 树集= { G=(V,E) :|V|=0 或 G连通且|E|=|V|-1}

森林是很多棵树组成的图

严格定义 森林集 = { G=(V,E) :存在V的划分(V1,V2,,Vn),使 对于任意i!=j,u属于Vi且v属于Vj,有(u,v)不属于E 且 G1=(V1,E1)、G2=(V2,E2)、Gn=(Vn,En)都属于树集(Ei={(u,v) :u,v属于Vi 且 (u,v)属于E}) }

链表是一种存储结构（也叫做物理结构），使用除了本身的数据域以外的附加数据域表示数据元素的逻辑关系，一般用指针实现

树是一种逻辑结构，一般数据元素逻辑上只有一个前驱（唯一的根没有前驱），有多个后继

栈是一种特殊的线性表，其插入删除点都限制在了线性表的某一端，该端点通称栈顶，另一个端点则称为栈底，栈的特性是先进后出（也叫做后进先出）

满二叉树：

除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。

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

节点：

就是一个图中的0、1、2~~14，这些就叫节点。

叶子节点：

就是没有子节点的节点，比如图中的7、8、9~~14这些，0、1、2、3这些就不是叶子节点。

拓展：二叉树相关术语

树的结点（node）：包含一个数据元素及若干指向子树的分支；

孩子结点（child node）：结点的子树的根称为该结点的孩子；

双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；

兄弟结点：同一双亲的孩子结点； 堂兄结点：同一层上结点；

祖先结点: 从根到该结点的所经分支上的所有结点子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙

结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；

树的深度：树中最大的结点层

结点的度：结点子树的个数

树的度： 树中最大的结点度。

叶子结点：也叫终端结点，是度为 0 的结点；

分枝结点：度不为0的结点；

有序树：子树有序的树，如：家族树；

无序树：不考虑子树的顺序；

1、一棵树中，最大的节点的度称为树的度。

2、树由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。

3、单个结点是一棵树，树根就是该结点本身。

4、设T1,T2,,Tk是树，它们的根结点分别为n1,n2,,nk。用一个新结点n作为n1,n2,,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,,nk为一组兄弟结点，它们都是结点n的子结点。我们还称T1,T2,,Tk为结点n的子树。

5、空集合也是树，称为空树。空树中没有结点。

数据结构有：1数组；2栈；3队列；4链表（单链表、双向链表、循环链表）；5数；6散列表；7堆；8图。数据结构是计算机存储知识数据的方式，数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

1、数组

数组是可以再内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。

2、栈

栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。栈的结构就像一个集装箱，越先放进去的东西越晚才能拿出来，所以，栈常应用于实现递归功能方面的场景，例如斐波那契数列。

3、队列

队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队。

4、链表

链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。

5、树

树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个节点有零个或多个子节点；

没有父节点的节点称为根节点；

每一个非根节点有且只有一个父节点；

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

6、散列表

散列表，也叫哈希表，是根据关键码和值 (key和value) 直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。

7、堆

堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质：

堆中某个节点的值总是不大于或不小于其父节点的值；

堆总是一棵完全二叉树。

8、图

图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

一、 树的定义：

树(tree)是n(n>0)个节点的有限集，在任意一棵树中，(1)有且仅有一个特定的称为根(root)的节点，(2)当n>1时，其余节点可分为m(m>0)个互不相交的有限集，而每个集合本身又是一棵树，称为根的子树(subtree)。

从上面树的定义中可以看到，这是一个递归的定义，即树的定义中又用到了树的概念。

树具有下面两个特点：

(1) 树的根结点没有前驱结点，除根结点外的其他结点有且只有一个前驱结点

(2) 树中所有结点可以有0个或多个后继结点

根据这两个特点，可以看出下图表示的都不是树。

森林(forest)是m(m≥0)棵互不相交的树的集合。任何一棵树，删除了根结点就变成了森林。

二、 树的存储结构

1、 双亲表示法

树中每个结点都有唯一一个双亲结点，根据这一特性，可以用一组连续的存储空间（一维数组）存储树中的各个结点，数组中每个元素都表示树中的一个结点，数组元素为结构体类型，这个结构体类型由结点本身的数据和结点的双亲在数组中的序号组成。

树的双亲表示法对于寻找双亲和根的操作很方便，但是要求某结点的孩子结点，就需要遍历整个数组，而且也不能反映各兄弟之间的关系，因此找到某结点的兄弟也很困难。

2、 孩子表示法

按如下图所示的形式存储。主体是一个与结点个数一样大小的一维数组，数组的每个元素有两个域，一个域用于存放结点数据，另一个用于存放指针，该指针指向由该结点孩子组成的单链表的首位置。单链表的结构也由两个域组成，一个存放孩子结点在一维数组中的序号，另一个为指针域，指向下一个孩子。

孩子表示法中查找双亲很困难，适用于查找孩子的操作。

3、 双亲孩子表示法

双亲孩子表示法是将双亲表示法和孩子表示法结合起来的方法。如下图所示，将各节点的孩子结点组成单链表，用一维数组顺序存储树的结点，数组元素包括结点本身的数据，该结点的孩子结点链表的头指针，存储该结点的双亲在数组中的序号。

4、 孩子兄弟表示法

这种方法的结构体包含：每个结点的数据，指向该结点的第一个孩子结点的指针和指向下一个兄弟结点的指针。

三、 树转换为二叉树

第一步：在树中所有兄弟结点间加一条连线

第四步：调整位置

五、 二叉树转换为树、森林

七、 森林的遍历

森林的遍历分为两种：前序遍历和中序遍历

1、 前序遍历

A 访问森林中第一棵树的根节点

B 前序遍历第一棵树的根节点的子树

C 前序遍历去掉第一棵树后剩余的森林

上图按照前序遍历，结果为：A B C D E F G H J I K

2、 中序遍历

A 中序遍历第一棵树的根节点的子树

B 访问森林中第一棵树的根结点

C 中序遍历去掉第一棵树剩余的森林

上图按照中序遍历，结果为：B A D E F C J H K I G

基础类：二叉搜索（排序）树，线索二叉树，哈夫曼树（最优二叉树），二叉堆

平衡树类：AVL，红黑树，2-3树，2-3-4树，B树，B+树，B-树，treap，SBT。

优先队列类：左高树（左偏树，可并堆，斜堆），双端堆，斐波那契堆

集合类：并查集

区间树类：线段树，划分树，归并树，树状数组

字母树类：字典树，后缀树。AC自动机算法

动态树类：伸展树

计算几何类：KD-tree （块状树），4叉树

RMQ转LCA：笛卡尔树

图论相关：最小生成树，无根树

其它：败者树，博弈树