荐 数据结构和算法5-非线性-树
数据结构和算法系列共八篇
- 数据结构和算法1-介绍
- 数据结构和算法2-线性-链
- 数据结构和算法3-线性-栈
- 数据结构和算法4-线性-队列
- 数据结构和算法5-非线性-树
- 数据结构和算法6-非线性-图
- 数据结构和算法7-搜索
- 数据结构和算法8-排序
先介绍个工具
1.概念
1-1.什么是树
树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。
没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构。
1-2.度
度(degree)分为
- 节点的度, 含有几个子节点(儿子)
- degree为0的节点，称为叶子节点leaf
- 最上层的曾为根节点root
- degree不为0的节点，除根以外称为内部节点
- 树的度，各节点的最大degree称为树的degree (m叉树)
1-3.深度
深度(depth)又叫层次(level),root为第一层，其子节点为第二层，子的子为第三层…以此类推
1-4.树的分类
顺序分
如果树的节点是有顺序的，那就是有序树，没有顺序的则是无序的
节点分
按树所有node里，某node的子node最多树为m，那就是m叉树 (以最多的为基准，即树的degree)
树的个数分
多棵树组成一个森林，一个树只是特殊的森林。
1-5.节点间关系
直接关系
- 父节点：一个节点直接前节点
- 子节点：一个节点直接后节点
- 兄弟节点：同一父节点的，其他节点
间接关系
- 祖先：从根到该节点所经分支上的所有节点；
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
- 堂兄弟节点：双亲在同一层的节点互为堂兄弟
2.二叉树
二叉树，是m叉树为2的特殊树(即:树的degree小于等于2)。
2-1.二叉树特性
有兴趣的可以看下其证明
2-2.二叉树分类
2-2-1.满二叉树
高度为k并且有个结点的二叉树。
2-2-2.完全二叉树
基于满二叉树，在最下层从最右侧起去掉相邻的若干叶子结点，得到的二叉树称为完全二叉树。
2-3.二叉树的存储结构
- 顺序数组存储
- 链结构存储
2-3-1.顺序数组存储
如果是完全二叉树，用顺序存储很好。但是不是完全二叉树的话，中间会有空留，占用空间。
2-3-2.链结构存储
链表结构比较适合二叉树存储。node节点结构：左子节点、数据、右子节点。
这样的数据结构，只能保证父找到子，不能保证子找父的。(如需子找到父，那还得需要多加个父节点存储)
3.遍历
二叉树遍历根据root的位置分三种
- 前序遍历：根-左-右 DLR
- 中序遍历：左-根-右 LDR
- 后序遍历：左-右-根 LRD
3-1.前序遍历
心法口诀：首先访问根，再先序遍历左子树，最后先序遍历右子树
传统分析
1.找到root-1，然后左边子node-4，右边子node-1。得到
1 4_ 2_
2.再分析左边的node-4，node-4的左子node没有，右子node为node-5。得到1 4 5 2_
3.左边没有，在分析右边node-2，node-2的左子node-3，右子node-6。得到1 4 5 2 3 6 _
4.再分析node-3的，左右子node都没有，是leaf
5.再分析node-6，左子node没有，右子node-7。得到1 4 5 2 3 6 7
个人技巧
注意上面箭头方向。从最左上，每次一层，所得的结果就是前序结果。
用咱的小技巧去试试前面的二叉树吧，看是不是得到一样的结果。
3-2.中序遍历
心法口诀：首先中序遍历左子树，再访问根，最后中序遍历右子树
传统分析
1.找到root-1放中间，然后左边子node-4放左侧，右边子node-1放右侧。得到
_4_ 1 2_(此时下划线是4和2的)
2.再分析左边的node-4，node-4的左子node没有，右子node为node-5。得到4 5 1 _2_(此时下划线是2的)
3.左边没有，在分析右边node-2，node-2的左子node-3放左侧，右子node-6放右测。得到4 5 1 _3_2_6_(此时下划线是3和6的)
4.再分析node-3的，左右子node都没有，是leaf。4 5 1 3 2_6_(3没有左右，那么就将3的左右下划线删去)
5.再分析node-6，左子node没有，右子node-7放右测。得到4 5 1 3 2 6 7
个人技巧
因为根在中间，那不就是跟我们二叉树一样吗!!!(左根右，LDR)，所以直接把二叉树压平到一条线，不就是需要的顺序吗? 是不是so easy