李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
Java
正文
数据结构和算法学习--树结构的基础部分
Leefs
2020-02-08 PM
2884℃
0条
# 数据结构和算法学习--树结构的基础部分 ### 一、二叉树 #### 1.1 为什么需要树这种数据结构 (1)数组存储方式的分析 优点:通过下标方式访问元素,速度快。对于有序数组,还可使用二分查找提高检索速度。 缺点:如果要检索具体某个值,或者插入值(按一定顺序)会整体移动,效率较低 画出操作示意图: ![27.树结构基础部分01.png][1] (2)链式存储方式的分析 优点:在一定程度上对数组存储方式有优化(比如:插入一个数值节点,只需要将插入节点,链接到链表中即可,删除效率也很好)。 缺点:在进行检索时,效率仍然较低,比如(检索某个值,需要从节点开始遍历) 操作示意图: ![27.树结构基础部分02.png][2] (3)树存储方式的分析 能提高数据存储,读取的效率,比如利用二叉排序树(Binary Sort Tree),即可以保证数据的检索速度,同时也可以保证数据的插入,删除,修改的速度。 案例:【7,3,10,1,5,9,12】 ![27.树结构基础部分03.png][3] #### 1.2 树示意图 ![27.树结构基础部分04.png][4] > 树的常用术语(结合示意图理解): > > 1)节点 > > 2)根节点 > > 3)父节点 > > 4)子节点 > > 5)叶子节点 (没有子节点的节点) > > 6)节点的权(节点值) > > 7)路径(从root节点找到该节点的路线) > > 8)层 > > 9)子树 > > 10)树的高度(最大层数) > > 11)森林 :多颗子树构成森林 #### 1.3 二叉树的概念 (1)树有很多种,每个节点最多只能有两个子节点的一种形式称为二叉树。 (2)二叉树的子节点分为左节点和右节点 ![27.树结构基础部分05.png][5] 二叉树 (3)如果该二叉树的所有叶子节点都在最后一层,并且结点总数=2^n-1,n为层数,则我们称为满二叉树。 ![27.树结构基础部分06.png][6] (4)如果该二叉树的所有叶子节点都在最后一层或者倒数第二层,而且最后一层的叶子节点在左边连接,倒数第二层的叶子节点在右边连接,我们称为完全二叉树。 ![27.树结构基础部分07.png][7] #### 1.4 二叉树遍历的说明 使用**前序,中序和后序**对下面的二叉树进行遍历。 **前序遍历:先输出父节点,再遍历左子树和右子树** **中序遍历:先遍历左子树,再输出父节点,再遍历右子树** **后序遍历:先遍历左子树,再遍历右子树,最后输出父节点** **小结:**看输出父节点的顺序,就确定是前序,中序还是后序 [1]: https://lilinchao.com/usr/uploads/2020/02/356810050.png [2]: https://lilinchao.com/usr/uploads/2020/02/415965835.png [3]: https://lilinchao.com/usr/uploads/2020/02/2491322285.png [4]: https://lilinchao.com/usr/uploads/2020/02/2991437291.png [5]: https://lilinchao.com/usr/uploads/2020/02/1761991904.png [6]: https://lilinchao.com/usr/uploads/2020/02/1448134195.png [7]: https://lilinchao.com/usr/uploads/2020/02/310781006.png
标签:
数据结构和算法
,
二叉树
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:
https://lilinchao.com/archives/574.html
上一篇
数据结构和算法学习--哈希表
下一篇
数据结构和算法学习--二叉树遍历应用实例(前序,中序,后序)
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
31
其它
25
GO
48
NLP
8
标签云
Linux
Hbase
排序
Hadoop
Yarn
Beego
VUE
Spark Streaming
Spark
nginx
Hive
Spark SQL
Java工具类
SpringCloud
Kafka
Nacos
Jquery
线程池
高并发
哈希表
Typora
Redis
数学
稀疏数组
Elastisearch
Git
Quartz
Ubuntu
GET和POST
SpringCloudAlibaba
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞