树在数据结构中占据了非常重要的位置,尤其是二叉树。经常是在java面试中必问的一个环节,而且二叉树的应用场景真的非常普遍,需要重点掌握好。
但是一直以来,很多同学对于二叉树的掌握都是不太全面。今天我就来谈谈二叉树,希望你喜欢这个Java数据结构与算法这个专题,认真看完后你会对二叉树会有一个比较完整的了解。
本文作者:陈睿|mikechen 优知学院创始人
重点会谈到以下几点:
- 二叉树
- 二叉树的遍历方式
- 二叉树有哪些种类
- 满二叉树
- 完全二叉树
- 二叉搜索树
- 平衡二叉树(AVL)
- 左旋与右旋
一.什么是二叉树
二叉树:就是每个节点都只能有两个子节点的树结构,俗称 “大裤衩”,特别形象。
通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。
下图你一看就秒懂了。
二.二叉树遍历方式
2.1二叉树的遍历主要有三种:
1)先序遍历(根左右)
2)中序遍历(左根右)
3)后序遍历(左右根)
2.2 先序遍历(根左右)
我先从第一种先序遍历开始谈起,主要的遍历顺序如下:
1)先访问根结点
2)然后先序遍历左子树
3)然后先序遍历右子树
还是举例说明,先序遍历下图
如果按照先序(根左右)遍历,结果将为: ABDFECGHI
2.3 中序遍历(左根右)
1)先中序遍历左子树
2)然后是根结点
3)然后中序遍历右子树
还是举例说明,中序遍历同一颗二叉树
按照中序遍历(左根右),结果为: DBEFAGHCI
2.4 后序遍历
1)后序遍历左子树
2)后序遍历右子树
3)然后访问根节点
还是举例说明,后序遍历同一颗二叉树
按照后序遍历(左右根)结果为:DEFBHGICA
三.二叉树的种类
基本包含:
- 满二叉树
- 完全二叉树
- 二叉搜索树
- 平衡AVL树
- 红黑树也属于AVL树
我先从满二叉树谈起。
3.1满二叉树
1)满二叉树
一棵树深度为k,2^k-1个节点的树是满二叉树
2)满二叉树的形态
3)满二叉树的特征
所有内部节点都有两个子节点,最底一层是叶子节点。
如果一颗树深度为h,最大层数为k,且深度与最大层数相同,即k=h;
第k层的结点数是:2^(k-1)
总结点数是:2^k-1 (2的k次方减一)
总节点数一定是奇数。
树高:h=log2(n 1)
3.2.完全二叉树
1)完全二叉树
若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h 层所有的结点都连续集中在最左边,这就是完全二叉树。
2)完全二叉树的形态
3)完全二叉树的特征
深度为k的完全二叉树,至少有2^(k-1)个节点,至多有2^k-1个节点。
树高h=log2n 1
满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树
3.3.二叉查找/搜索/排序树-BST
1)二叉搜索树
二叉搜索树BST(Binary Search/ Sort Tree),也称为二叉查找树,二叉排序树
备注:下面我就以二叉搜索树来统称,但是你要知道二叉搜索树、二叉查找树、二叉排序树,其实是同一种树。
2)二叉搜索树的特点
- 左子树上所有结点的值均小于等于它的根结点的值
- 右子树上所有结点的值均大于等于它的根结点的值
3)二叉搜索树的优缺点
优点:查找速度快,二叉查找树比普通树查找更快
缺点:出现平衡问题
二叉搜索树在经过多次插入与删除后,有可能导致如下右图的结构:
搜索性能已经是线性的了,所以,使用二叉搜索树还要考虑尽可能保持上面左图的结构,和避免上面右图的结构,也就是所谓的“平衡”问题 。
4)二叉搜索树的时间复杂度
时间复杂度
二叉查找树比普通树查找更快,查找、插入、删除的时间复杂度为O(logN)。
缺点
二叉查找树有一种极端的情况,就是会变成一种线性链表似的结构,此时时间复杂度就变味了O(N),为了解决这种情况,所以出现了下面我即将谈到的二叉平衡树。
备注:时间复杂度
- O(1):最低的时空复杂度,也就是耗时与输入数据大小无关,无论输入数据增大多少倍,耗时/耗空间都不变。哈希算法就是典型的O(1)时间复杂度,无论数据规模多大,都可以在一次计算后找到目标。
- O(n):代表数据量增大几倍,耗时也增大几倍。比如常见的遍历算法。
- O(logn):当数据增大n倍时,耗时增大logn倍(这里的log是以2为底的,比如,当数据增大256倍时,耗时只增大8倍,是比线性还要低的时间复杂度)。二分查找就是O(logn)的算法,每找一次排除一半的可能,256个数据中查找只要找8次就可以找到目标。
3.4.平衡二叉树(AVL树)
1)平衡二叉树
平衡二叉树全称平衡二叉搜索树,也叫AVL树,是一种自平衡的树,从上面二叉搜索树升级过来的,重点是改进了平衡问题。
2)平衡二叉树的特征
- AVL树也规定了左结点小于根节点,右结点大于根节点。
- 并且还规定了左子树和右子树的高度差不得超过1,这样保证了它不会成为线性的链表。
3)AVL树怎么解决平衡
主要就是通过左旋和右旋来解决,防止特殊情况下出现下面的线性结构。
所以通过下图的左旋和右旋来解决上面的平衡问题。
但也有对应的缺点,由于要维持自身的平衡,所以进行插入和删除结点操作的时候,需要对结点进行频繁的旋转。
4.结语
通过上述的介绍,已经对于二叉树有了初步的认识。本篇文章介绍的基础知识希望读者能够牢牢掌握,并且能够在脑海中建立一棵二叉树的模型,为后续学习数据结构与算法打好基础。
如果喜欢点个赞,后续我会持续写这个数据结构与算法专题。
作者简介
陈睿|mikechen,10年+大厂架构经验,BAT资深面试官,就职于阿里巴巴、淘宝、百度等一线互联网大厂。
关注作者「mikechen」公众号,获取更多技术干货!
后台回复【架构】,即可获取《阿里架构师进阶专题全部合集》,后台回复【面试】即可获取《史上最全阿里Java面试题总结》