开发者学堂课程【Java 高级编程:二叉树结构简介】学习笔记,与课程紧密联系,让用户快速学习知识。
课程地址:https://developer.aliyun.com/learning/course/20/detail/363
二叉树结构简介
内容介绍:
1. 二叉树相关知识简介
2. 构造二叉树的原理
3. 二叉树的遍历
一、有关二叉树的介绍
在进行链表结构开发的过程之中会发现所有的数据按照收尾相连的状态进行保存,那么当要进行某一个数据查询的时候(判断该数据是否存在),这种情况下它所面对的时间复杂度是“O(n)"。
如果说现在它的数据量小(不超过三十个)的情况下,那么性能上是不会有太大差别的,而一旦保存的数据量很大,这个时候时间复杂度就会严重损耗程序的运行性能,那么对于数据的存储结构就必须发生改变,应该可以尽可能的减少检索次数为出发点进行设计,对于现在的数据结构而言,最好的性能就是“O(logn),所以现在要想实现它就可以利用二叉树的结构来完成。
二、构造二叉树的原理
如果想要实现一颗树结构的定义,那么就需要去考虑数据的存储形式。
在二叉树的实现之中其基本的实现原理如下:取一个数据为保存的根节点,小于根节点的数据要放在节点的左子树,而大于节点的数据要放在该节点的右子树。
如果要进行数据检索的话,此时就需要进行每个节点的判断,但判断是区分左右的,所以不会整个结构都进行判断处理,那么它的时间复杂度就是 O(logn)。
三、二叉树的遍历
而对于二叉树而言,在进行数据获取的时候也有三种形式:
(1) 前序遍历(根-左-右)
(2)中序遍历(左-根-右)
(3) 后序遍历(左-右-根),