本文共 3999 字，大约阅读时间需要 13 分钟。
相比之前的帖子，对其进行了增添和完善。
ps：本颜色的字体是后续添加内容
——————————————————
参考链接：
大话数据结构.pdf
http://www.cnblogs.com/yc_sunniwell/archive/2010/06/27/1766233.html
1.什么是树？
是一种数据结构，可以用来表示层次关系，因表示的样子很像一颗倒立的树而得名。
在数据结构中的特点，是一对多（链表是一对一，图是多对多）
最上面；树根
中间：树枝
最下：树叶
2.树的定义。
如图：
树定义（无根树）：
①一个无根树是一个二元组(V,E); //V是顶点集（非空集合），E是边集（V中元素构成的无序二元组的集合）
（注：个人理解，就是有至少1个点，可以有很多个，这些点的集合，就是V，称为顶点集，我觉得可以理解为结点的集合；
然后这些结点，将会连城一些线段，并且每条线段都没有方向(这里的方向，我认为可以理解为从一个点连向另外一个点，至于为什么说没有方向，我觉得是因为没有起点和终点，线段只是将两个点连起来而已，所以称为没有方向)，而这些线段的结合，就是E，称为边集）
在离散数学中，无根树指无环连通无向图。
所谓的 无向图，就是一个图中若每条边都是没有方向的，则称为无向图。
参考链接：http://baike.baidu.com/view/93110.htm
无向图中的边，均是顶点的无序对，无序对通常用圆括号表示。
（注：据我理解，所谓的无序对，就是拿出某个图中的两个点，例如v1和v2，然后(v1,v2)表示的边，和(v2,v1)表示的边是一样的。而像(v1,v2)这样表示，就是指的是无序对，正是因为边没有方向，所以两种表示方法表示的线段才是一样的）
无根树要求每个顶点之间都是直接或者间接相连，且图中没有环（即只有简单路径）。
（注：因为不能有环，所以任意两个点之间，只有一条路径能走的通，假如有两条路径能走得通，就形成了一个环了）
由于树是图的子集（图是什么？推测指的是数据结构？），这一类图具有树的特征，但不具备数的形式，没有特定的根结点，故称为无根树。
（注：这说明，无根树和有根树几乎是一样的，除了有根树有根结点，而根结点又是指定的，即给一个无根树，然后指定一个结点为根，那么这个无根树就成为了有根树）
树是n（n≥0）个结点的有限集。n=0时称为空树，在任意一棵非空树中：
（1）有且仅有一个特定的称为根（root）的结点；
（2）当n＞1时，其余结点可分为m（m>0）个互不相交的有限集T1、T2、T3......、Tm，其中每个集合本身又是一棵树，并且称为根的子树。
用上图举例子的话，就是A为根时，是一棵树，然后这棵树从根部分离出以B、C、D三个结点为根的子树，其中B子树有2个结点，C子树有7个结点，D有1个结点。
注：
①当n>0时，即至少有一个结点时，那么树必然有一个根结点，且只有一个根结点；
②子树之间必然是互不相交的（否则就会出现多个上级结点指向同一个下级结点，或者是同级结点之间互相连接）
有根树：
①树根：在无根树中，可取树中任意一个结点为根r，使树变为一颗有根树。
②父子关系：（1）对于任意非根结点v，v到树根r的路径上的第一个结点p，定义为v的父结点，而v是p的子结点。
（2）一个结点可以有多个子结点（也可以是0个，例如这个树中，只有一条线连接着这个结点）；
（3）非根结点只能有一个父结点（如果是根出来的第一个结点，那么这个结点就是自己的父结点么？）
（4）树根没有父结点。
数据结构中的树一般是有根树。
有根树：
①有根树的递归定义：
（1）没有结点是一棵树（可称为空结点）；
（2）单独的一个结点是一颗树；
（3）如果t0、t1、t2、……、tk-1是一颗树，t是一个结点，则将t0、t1、t2、……、tk-1作为t的子结点后，组成的树t，也是一棵树，树根为t。（注意：一般有根树使用根结点来标识）
——我猜测，从t0到tk-1之间应该也可以将其分别视为一个结点，然后进行连接（以树的形式，即任意两个结点之间只有一条路径），就形成了一个有根树（树根为t）
树的深度和高度：
树的高度和树的深度似乎不一样，貌似说法有几种（比如某些大学教科书）：
有的说高度和深度一样；
有的说高度比深度少一；
有的说根结点从0开始计算；
有的说根结点从1开始计算。
根据我个人理解，如图那样，有5层，根直接相连的，其深度则为1，高度为3；最下层的，其深度为4，高度为0。
推测，深度就是指从根开始的距离（即从根开始计算，假如根为第0个结点，那么连接他和根的线段中，他是第几个结点，深度就是几）；
而高度就是指，一个结点，和最底层距离有多远，假如最多是5层，这个结点和根的距离只有1（即位于第4层），那么他的高度就是4。
3.二叉树
二叉树是树的一种。
二叉树的特征是，除了叶以外的结点，都有两个子。（叶就是在它和根的路径上，没有比他更远的结点了，也可以理解为，只有一个结点和它相连，并且它不是根，那么他就是叶）
简单来说，就是在有根树的基础上，一个结点，往更深的地方延伸时，最多只能延伸出来零个，或者两个结点（只能是0个或者2个，不能是1个。如果是0个就是叶，否则就是结点），那么他就是二叉树。
例如：图中延伸出0个结点（叶）有：E，G,H,I,J,K
而延伸出2个结点的有：A,B,C,D,F
4.树的遍历
所谓树的遍历，是指对树中所有结点的信息的访问。
其重点有2个：
①对所有结点进行访问（假如有结点没有被访问，肯定算不上遍历了）
②对每个结点只访问一次；
说起遍历，那么前提是树必须有顺序。
假如A结点是根结点，B和C是他的子（二叉树）。那么如何遍历呢？
先访问A再访问B最后C？还是A->C->B？又或者是先访问B或者C？
这些都是不一样的。
只有有了顺序，才能决定怎么访问。同样以A、B、C三个结点为例，A是根结点，B左C右，或者是B右C左，其并非是同一个树。
根据我个人所知推断，假如有这样一个树，他最终是要存储到硬盘里的，如果B在A左边，C在A右边，其必然是有一定原因和规律的。例如，三个数都是int值，B=10，A=20，C=30。那么以数组形式存储，其为{B,A,C}。比A小的放A左边，比A大的放A右边，数组以增序排列。假如值不变，形式为{C,A,B}，那么数组就变为以减序排列了。增序和减序，显然是不一样的。
因此，树的左右顺序是不能颠倒的。
疑问：我找的资料上说的是二叉树其左右是不能颠倒的，那么三叉树，或者其他树可以颠倒么？我推测应该也是不能的吧，至于为什么，需要查查资料。
二叉树的遍历方法主要有三种：
①前序遍历；（先访问根结点，再访问子结点）
②后序遍历；（先访问子结点，再访问根结点）
③中序遍历（只适用于二叉树）
前序遍历：
顺序：访问根结点——》访问左子树——》访问右子树
在访问子树，依然按该顺序进行访问。
以上图中的二叉树为例，前序遍历的顺序是
其逻辑是：
（1）先访问根；
（2）当前如果是根，且无子结点，则结束；如果是根，有子结点，第二次返回根的时候结束；（在编程时如何做到这一点？）
（3）查看有没有没有访问过的子结点（问题，如何判断是不是访问过的）：
（3.1）如果有，则访问子结点的左边部分，重复（2）；
（3.2）如果没有，则判断当前结点是不是子结点的左结点：
（3.2.1）如果是，则访问右结点，重复（2）；
（3.2.2）如果不是，返回父结点，重复（2）
后序遍历：
顺序：访问根结点——》访问右子树——》访问左子树
顺序正好和前序遍历相反。
所以，具体的就省略了。
中序遍历：
所谓的中序遍历，就是指，先访问左子树，再访问根，再访问右子树。
具体到每一个子树时，也是如此。
与前序遍历和后序遍历不同的是，中序遍历在访问子树的过程中，并不直接访问路径上的，而是先要确定该子树还有没有子结点，如果没有了，才访问它，如果有，则继续访问子树的子树。
例如：
以图为例，由于B是A的子，D是B的子，H是D的子，而H没有子了。因此，先访问H。
然后访问H的父（D），访问D。
然后D的右子是I，因此访问I。
I没有子了，返回D；D的子树访问完了，因此返回D的父（B），访问B；
B的右子，因此访问E；
E没有子了，因此返回B，而B的子树也访问完了，因此返回A，访问A；
A的右子树是C，而C有子（F），F有子（J），J无子，因此访问J；
返回J的父F，访问F；
F的右子是K，访问K；
K无子，返回F，F的子树访问完了，返回C，C的右子是G，G无子，访问G。
树的遍历结束。其顺序是：H-D-I-B-E-A-J-F-K-C-G。
形象的说，就是先访问左子树，假如左子树没有子，则访问结点，并返回，访问父，再访问父的右子树。然后重复即可。——左-父-右的顺序
树的结点：
包括一个数据元素，和从这个元素，指向其各个子树的分支（但不包括指向其父树的分支）。
结点拥有的子树数，称为结点的度（Degree），度为0的结点，称为叶结点（Leaf）或终端节点；
度不为0的结点，称为非终端结点或分支结点。
除根结点外，分支结点也称为内部结点。
树的度为树内各节点的度的最大值。
简单来说，树的每个结点都有度，看他往下连向几个结点（只考虑下一层，不考虑更深部分），其度就是几，没有就是0。
没有继续往下连接的（叶），就是叶结点；
不是根也不是叶的，就是内部结点；
每个结点都有度，所有结点中，度最大的结点的度，就是树的度。
树的顺序：
之前说过，二叉树的结点的左右子树是不能交换的，也就是说，有顺序的。
假如一个树，其结点的子树之间的左右顺序，是有次序的，不能互相交换，那么就说这个树是有序树，否则就是无序树。