初识二叉树,领悟树的概念 | 带你学《Java语言高级特性》之三十八-阿里云开发者社区

开发者社区> Java开发者> 正文

初识二叉树,领悟树的概念 | 带你学《Java语言高级特性》之三十八

简介: 在之前的学习中我们接触过链表数据结构的相关内容,其查询操作的时间复杂度为O(n),这对大量数据来说显然是很损耗性能的。本节将为读者介绍一种新的数据结构:二叉树。

上一篇:Comparator帮你补救比较缺陷 | 带你学《Java语言高级特性》之三十七
在之前的学习中我们接触过链表数据结构的相关内容,其查询操作的时间复杂度为O(n),这对大量数据来说显然是很损耗性能的。本节将为读者介绍一种新的数据结构:二叉树。

【本节目标】
通过阅读本节内容,你将初步接触树的结构,了解其结构特性和数据排布方式,并能够实现简单的二叉树,理解其执行查询时的基本逻辑,认识其常用的遍历方法。

二叉树结构

在进行链表结构开发的过程之中会发现所有的数据按照首尾相连的状态进行保存,那么当要进行某一个数据查询的时候(判断该数据是否存在),这种情况下它所面对的时间复杂度是“O(n)”,如果说它的数据量小(不超过30个)情况下,那么性能上是不会有太大差别的,而一旦保存的数据量很大,这个时候时间复杂度就会严重损耗程序的运行性能,那么现在对于数据的存储结构就必须发生改变,应该可以尽可能的减少检索次数为出发点进行设计。对于现在的数据结构而言,最好的性能就是“O(logn)”,所以要想实现它,就可以利用二叉树的结构来完成。

如果要实现一棵树结构的定义,那么需要去考虑数据的存储形式,在二叉树的实现之中,其基本的实现原理如下:取第一个数据为保存的根节点,小于等于根节点的数据放在节点的左子树,而大于节点的数据要放在该节点的右子树。

image.png
二叉树

如果要进行数据检索的话,此时就需要进行每个节点的判断,但是它的判断是区分左右的,所以不会是整个结构都进行判断处理,那么它的时间复杂度就是“O(logn)”。

而对于二叉树而言,在进行数据获取的时候也有三种形式:前序遍历(根-左-右)、中序遍历(左-根-右)、后序遍历(左-右-根),那么现在只是以中序遍历为主,则以上的数据进行中序遍历的时候最终的结果:10、20、25、30、38、50、80、100;

想学习更多的Java的课程吗?从小白到大神,从入门到精通,更多精彩不容错过!免费为您提供更多的学习资源。
本内容视频来源于阿里云大学

下一篇:手把手教你实现二叉树数据添加 | 带你学《Java语言高级特性》之三十九
更多Java面向对象编程文章查看此处

版权声明:本文中所有内容均属于阿里云开发者社区所有,任何媒体、网站或个人未经阿里云开发者社区协议授权不得转载、链接、转贴或以其他方式复制发布/发表。申请授权请邮件developerteam@list.alibaba-inc.com,已获得阿里云开发者社区协议授权的媒体、网站,在转载使用时必须注明"稿件来源:阿里云开发者社区,原文作者姓名",违者本社区将依法追究责任。 如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
+ 订阅

Java开发者成长课堂

官方博客
官网链接