1.什么是树？
树解决的是一对多的问题，一般来说什么是一对多的问题呢，分类问题（分类问题某种意义上也概括了从属问题）其实就是一对多问题，经常说的思维导图什么的：
图1
分类有一个很重要的特性：子类互不相交
如果分完类，不同类之间还有重叠的部分，还叫什么分类呢？
比如最近的很火的垃圾分类，把许多垃圾分成不同的垃圾种类，但是在丢垃圾的时候必须只能选一个种类丢，总不可能把垃圾分成两半一个丢不可回收垃圾分类，一个丢有害垃圾分类吧？
诚然，在人们生活中分类总是不完全的，但是对于一个能够被理解和使用的分类必须是能够把事物和事物区分的开的，也就是说，类与类之间不能有相交。
2.树的定义
有关于树的例子就是上面的分类相关的问题。凡是树的每一分支，都代表着一种分类依据。比如图1中，特色功能和特色功能代表着对思维导图功能点的分类依据。
树的定义
要点：
- n=0,为空树; n>0,不为空树;
- 在n>0的情况下：有且仅有一个称为根的结点
- 在n>1的情况下：有m个互不相交的有限集
- 在n>1的情况下：每个有限集都本身是一棵树
归纳以下就是三个特性：1.必须要有根才能长出子叶，而且只能有一个；2.互不相交特性；3.递归特性。
3.结点
结点是组成一棵树的重要部分，它的重要意义是——结点是数据的载体。之所以是载体不是全部，因为它不仅代表了数据元素，也存放了数据元素之间的关系（双亲/孩子关系）。
结点的度（根结点、叶结点）
结点有多少分支，就有多少度。树的度就是最大结点度
“度”解决了啥问题？
- 度可以解决存储树时，存储空间预留多少的问题
- 度可以解决遍历树时，每个结点循环多少次取它的孩子们
结点层次
结点层次这个概念提出来，与“层数”也就是树的深度，功能和度其实差不多，方便确定存储空间的预留和遍历时的复杂度。
结点之间的关系
- 双亲（父）
- 子
- 兄弟
这三种关系和问题的具体分类情况有关，才能确定谁是父结点、子结点
4.树的有序性
将树中的结点从左往右看成是有次序，那么就是一棵有序树，相对的就是无序树。
为什么要引入树的有序性？
实际上树的有序性对于描述问题并没有很大的作用，在对事物分类的过程中，引入顺序是没有太多意义的。
但是！！！！对存储和寻找很有用，只有给了结点顺序，我才能定位到某一个数据元素。
5.树的存储结构
要把一棵树存进计算机（内存）里面，不简单。
之前我们说过在计算机里存储数据结构只有顺序存储和链式存储两种
Tips：但是要注意的是，无论是顺序存储还是链式存储还是顺序存储混合链式存储，都需要结合逻辑结构去设计相应的存储方式。这种存储方式要做到既能够表示问题的逻辑，也要符合计算机存储和寻址的方式
在树这里也是一样的，需要怎么去设计才能够既能满足计算机顺序链式存储的结构，又能表示树里数据元素之间的关系呢？
因此就有了这三种设计思路：
- 双亲表示法
- 孩子表示法
- 孩子兄弟表示法
这些表示法不一定固定用哪一种计算机存储结构，有用数组解决，有用链表解决，更有混合的。但是他们有一个共同点：都是通过--数据元素+数据元素与双亲（孩子/孩子和兄弟）的关系来构成一个结点的！
这个关系怎么表达？是由下面两种方法来解决这个问题：
- 链表指针的形式来指向
- 记录别的结点在数组中下标来指向（当然使用这种方法有一个前提就是必须把所有结点存成数组）
另外，一个节点里面数据元素和关系也可有顺序和链式两种方式表达
存储结构小结：
要点一：树的存储结构解决的问题是，如何才能够既能满足计算机顺序链式存储的结构，又能表示树里数据元素之间的关系
要点二：设计思路有三种，分别描述了结点中存放的“关系”是怎么样一种数据与数据关系
要点三：怎么去描述结点中需要存放的“关系”呢？，是用链表指针还是用数组下标
要点四：一个结点需要存放两个东西：1.数据元素 2.关系（和其它结点的）；因此这两个存放的东西之间的关系又可以用链表或者数组来描述
--数据结构（四）树---树的存储结构里面有详细的描述，可以好好感悟一下
二叉树
二叉树是树的一种，它描述分类问题一般分类依据只有一种，比如：大小、多少、强弱...
是一种二分类问题！因此二叉树的左右结点是有差别的！你想一种情况，当有两棵树，每棵树只有两个元素，一棵树是大的元素就放右边，另一棵是较小的元素放左边，那虽然两个树都只有一个子结点，但是这两棵树并不等价。
提前说一下把原本的一棵树变为二叉树，就是把一棵树里面的结点分成两种类型——是结点的长子&结点的兄弟
这里暗示了一个——问题和问题之间是可以相互转换的，把树问题结点编上号它就变成了线性表
二叉树的作用：
- 解决原本就是二分类的问题
- 二分类问题方便存储进计算机里，也方便遍历
接下来所有的东西目的都是为了把二叉树这种二分类问题放进计算机里操作
1.研究如何存放
-
通过链表存放
这种方式比较简单理解，就是通过指针来表示结点与结点之间关系
二叉链表
啥时候存成链表？如果二叉树不够满的话就存为链表，也就是可以取决于树的稀疏程度
-
顺序存储
- 像对一棵普通的树一样进行描述存储
- 通过完全二叉树：
完全二叉树只是提供了一种思路，对一棵树进行存储。也可以是完全三叉，完全四叉树...它的思想是：按顺序对结点进行编号，编号之后树不就成一个有顺序的线性表了吗？对的，但是这种编号必须是不可缺失的，即使孩子缺失，我也要对空位进行编号，算它有这个孩子。总结来说，完全二叉树是一种赋予树各个结点顺序，然后便于顺序存储的存储思路。
2.研究如何对二叉树操作（遍历、建立）
最复杂的问题就是如何遍历树了，如果所有结点存成顺序存储结构，那么遍历就不是一件难事，但是以链表的形式存二叉树的时候，就不那么简单了，如何对二叉树操作（遍历）呢？
- 递归的方式
树的这种问题本身就是一个递归问题。因此可以考虑递归来遍历。
一个函数里（或者说是递归体）的操作与递归语句的顺序其实可以这么理解，举一个例子：
void InOrderTraverse(BiTree T) {
if(T==NULL) {
return;
}
InOrderTraverse(T->lchild);
printf("%c",T->data);
InOrderTraverse(T->rchild);
}
1.判断左子树是否遍历完
2.是，则执行操作 (输出Data)
3.判断右子树是否遍历完
同样
void InOrderTraverse(BiTree T) {
if(T==NULL) {
return;
}
printf("%c",T->data);
InOrderTraverse(T->lchild);
InOrderTraverse(T->rchild);
}
1.进入函数，执行操作 (输出Data)
2.判断左子树是否遍历完
3.判断右子树是否遍历完
整一个递归其实就是一个判断的过程，操作步骤前的递归语句一定要执行完才能执行操作
因此对于树的递归遍历，无论是前序中序还是后序，要输出Data，就必须要判断前面的递归语句完成没有
如果输出Data，那么意味着输出语句前面递归语句全部执行，也就是说一个前置条件，就和跑程序一样
- 线索化
线索二叉树，把树给线索化，都是为了不用递归就能快速遍历一棵树。
就是在第一次遍历（也就是建立二叉树的时候），每遍历一个结点，就把它的前驱后继给记录/存下来（当然只能记住一种遍历，也就是第一次遍历的那种，例如只能记住中序遍历）。记录下来以后，每次用到中序遍历的时候，就和双链表的使用是一样的了。
实现这个过程有很多个小问题需要解决：- 用哪些地方来存放前驱后继的指针？——利用结点空出来的指针空间；
- 如何知道这个指针指向的不是左子树右子树而是前驱后继？——每个结点加一个域用于存放0和1来表示子树还是前驱后继
- 怎么建立线索化？——第一次递归遍历的时候，左子树为空则存前面结点的地址，并且判断前驱结点的右子树若为空，则存这个结点的地址
- 线索化之后，如何去遍历树？——对于每个结点来说，都是找到以这个结点为根的树的第一个遍历的元素，然后不断的寻找后继，如果找不到后继指针，就把新的结点的树重新找到它第一个遍历的元素。换句话说，当你遇到一个没有后继指向的结点，你需要判断它的实际后继结点是哪一个，然后跳过去，把那个实际的后继节点当成一棵新的树去线索遍历
线索化之后遍历示意图
- 一开始指针指向F结点，那么就要找到以F为根的这棵树的第一个元素，如果线索化的是先序遍历就是找到F
- 然后因为F没有后继指针，那么我就判断实际后继结点是谁，因为这个是先序遍历，因此要往左子树去找，找到结点C。
- 然后将以C为根的这棵树重复上述过程。
- 找到结点A之后，就顺着A的后继指针找到结点D，再顺着后继指针找到B
- B后继找到E，然后E没有后继指针，就找以E为根的树的第一个遍历的元素，找它的左子树....直到全部遍历完成
可以参考博客——https://blog.csdn.net/dongfei2033/article/details/80709975
树、森林、二叉树之间的转换
因为二叉树问题便于理解和操作，所以把树和森林转换为二叉树。
转换过程其实就是对树和森林分类的过程，把一棵树的结点可以用是兄弟还是长子来分类，把森林的结点可以用是根还是子结点来分类，（其实树和森林都差不多）
树的先根遍历=先访问树的根结点再去遍历子树=二叉树的先序遍历
树的后根遍历=先访问每棵子树，再访问根结点=原树的后序遍历=二叉树的中序遍历
森林的前序遍历=先访问根结点，再访问每棵子树=二叉树前序遍历
森林的后序遍历=先访问每棵子树=二叉树的中序遍历
总结
树.png
网友评论