数据结构和算法系列共八篇
先介绍个工具
树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。
没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构。
度(degree)分为
深度(depth)又叫层次(level),root为第一层，其子节点为第二层，子的子为第三层…以此类推
顺序分
如果树的节点是有顺序的，那就是有序树，没有顺序的则是无序的
节点分
按树所有node里，某node的子node最多树为m，那就是m叉树 (以最多的为基准，即树的degree)
树的个数分
多棵树组成一个森林，一个树只是特殊的森林。
直接关系
间接关系
二叉树，是m叉树为2的特殊树(即:树的degree小于等于2)。
有兴趣的可以看下其证明
高度为k并且有个结点的二叉树。
基于满二叉树，在最下层从最右侧起去掉相邻的若干叶子结点，得到的二叉树称为完全二叉树。
如果是完全二叉树，用顺序存储很好。但是不是完全二叉树的话，中间会有空留，占用空间。
链表结构比较适合二叉树存储。node节点结构：左子节点、数据、右子节点。
这样的数据结构，只能保证父找到子，不能保证子找父的。(如需子找到父，那还得需要多加个父节点存储)
二叉树遍历根据root的位置分三种
心法口诀：首先访问根，再先序遍历左子树，最后先序遍历右子树
传统分析
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
个人技巧
注意上面箭头方向。从最左上，每次一层，所得的结果就是前序结果。
用咱的小技巧去试试前面的二叉树吧，看是不是得到一样的结果。
心法口诀：首先中序遍历左子树，再访问根，最后中序遍历右子树
传统分析
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
您可能感兴趣的文章:
如对本文有疑问， 点击进行留言回复！！
数字与信号处理实验6 有限冲激响应(FIR)数字滤波器的设计
【计算机体系结构 / 并行与分布计算 / 存储系统】 2019年-中国计算机学会推荐国际学术会议和期刊目录（一）
荐 《操作系统导论》学习笔记（七）：内存虚拟化 (机制及策略)
我要评论
网友评论