视频课程
小黑屋思过中，禁止观看！
评论并刷新后可见

您需要在视频最下面评论并刷新后，方可查看完整视频

视频课程
立即观看
付费视频

您支付费用，方可查看完整视频

￥{{user.role.value}}
课程视频
开始学习
会员专享

视频合集

最全二叉树详解：二叉树的遍历以及完全二叉树等6种详解

  • 课程笔记
  • 问答交流

树在数据结构中占据了非常重要的位置，尤其是二叉树。经常是在java面试中必问的一个环节，而且二叉树的应用场景真的非常普遍，需要重点掌握好。

但是一直以来，很多同学对于二叉树的掌握都是不太全面。

为了助大家掌握好二叉树，这节课我会重点讲解以下8点：

1.二叉树的遍历方式有哪些？

2.二叉树有哪些种类？

3.满二叉树的实现

4.完全二叉树的实现

5.二叉搜索树的实现

6.平衡二叉树(AVL)的实现

7.左旋与右旋的优缺点

 

二叉树遍历方式

1二叉树的遍历主要有三种：

最全二叉树详解：二叉树的遍历以及完全二叉树等6种详解-mikechen

1）先序遍历（根左右）

2）中序遍历（左根右）

3）后序遍历（左右根）

 

2 先序遍历（根左右）

我先从第一种先序遍历开始谈起，主要的遍历顺序如下：

1）先访问根结点

2）然后先序遍历左子树

3）然后先序遍历右子树

还是举例说明，先序遍历下图

最全二叉树详解：二叉树的遍历以及完全二叉树等6种详解-mikechen

如果按照先序（根左右）遍历，结果将为： ABDFECGHI

3 中序遍历（左根右）

1）先中序遍历左子树

2）然后是根结点

3）然后中序遍历右子树

还是举例说明，中序遍历同一颗二叉树

最全二叉树详解：二叉树的遍历以及完全二叉树等6种详解-mikechen

按照中序遍历（左根右），结果为： DBEFAGHCI

 

4 后序遍历

1）后序遍历左子树

2）后序遍历右子树

3）然后访问根节点

还是举例说明，后序遍历同一颗二叉树

最全二叉树详解：二叉树的遍历以及完全二叉树等6种详解-mikechen

按照后序遍历（左右根）结果为：DEFBHGICA

 

二叉树的种类

最全二叉树详解：二叉树的遍历以及完全二叉树等6种详解-mikechen

基本包含:

  • 满二叉树
  • 完全二叉树
  • 二叉搜索树
  • 平衡AVL树
  • 红黑树也属于AVL树

我先从满二叉树谈起。

1满二叉树

1）满二叉树

一棵树深度为k，2^k-1个节点的树是满二叉树

2）满二叉树的形态

最全二叉树详解：二叉树的遍历以及完全二叉树等6种详解-mikechen

3）满二叉树的特征

所有内部节点都有两个子节点，最底一层是叶子节点。

如果一颗树深度为h，最大层数为k，且深度与最大层数相同，即k=h;

第k层的结点数是：2^(k-1)

总结点数是：2^k-1 (2的k次方减一)

总节点数一定是奇数。

树高：h=log2(n+1)

 

2.完全二叉树

1）完全二叉树

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h 层所有的结点都连续集中在最左边，这就是完全二叉树。

2）完全二叉树的形态

最全二叉树详解：二叉树的遍历以及完全二叉树等6种详解-mikechen

3）完全二叉树的特征

深度为k的完全二叉树，至少有2^(k-1)个节点，至多有2^k-1个节点。

树高h=log2n + 1

满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

 

3.二叉查找/搜索/排序树-BST

1）二叉搜索树

二叉搜索树BST（Binary Search/ Sort Tree），也称为二叉查找树，二叉排序树

最全二叉树详解：二叉树的遍历以及完全二叉树等6种详解-mikechen

备注：下面我就以二叉搜索树来统称，但是你要知道二叉搜索树、二叉查找树、二叉排序树，其实是同一种树。

2）二叉搜索树的特点

最全二叉树详解：二叉树的遍历以及完全二叉树等6种详解-mikechen
  • 左子树上所有结点的值均小于等于它的根结点的值
  • 右子树上所有结点的值均大于等于它的根结点的值

3）二叉搜索树的优缺点

优点：查找速度快，二叉查找树比普通树查找更快

缺点：出现平衡问题

二叉搜索树在经过多次插入与删除后，有可能导致如下右图的结构：

最全二叉树详解：二叉树的遍历以及完全二叉树等6种详解-mikechen

搜索性能已经是线性的了，所以，使用二叉搜索树还要考虑尽可能保持上面左图的结构，和避免上面右图的结构，也就是所谓的“平衡”问题 。

 

4）二叉搜索树的时间复杂度

时间复杂度

二叉查找树比普通树查找更快，查找、插入、删除的时间复杂度为O（logN）。

缺点

二叉查找树有一种极端的情况，就是会变成一种线性链表似的结构，此时时间复杂度就变味了O（N），为了解决这种情况，所以出现了下面我即将谈到的二叉平衡树。

备注：时间复杂度

  • O(1)：最低的时空复杂度，也就是耗时与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标。
  • O(n)：代表数据量增大几倍，耗时也增大几倍。比如常见的遍历算法。
  • O(logn)：当数据增大n倍时，耗时增大logn倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。二分查找就是O(logn)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。

 

4.平衡二叉树(AVL树)

1）平衡二叉树

平衡二叉树全称平衡二叉搜索树，也叫AVL树,是一种自平衡的树，从上面二叉搜索树升级过来的，重点是改进了平衡问题。

2）平衡二叉树的特征

最全二叉树详解：二叉树的遍历以及完全二叉树等6种详解-mikechen
  • AVL树也规定了左结点小于根节点，右结点大于根节点。
  • 并且还规定了左子树和右子树的高度差不得超过1，这样保证了它不会成为线性的链表。

 

3）AVL树怎么解决平衡

主要就是通过左旋和右旋来解决，防止特殊情况下出现下面的线性结构。

最全二叉树详解：二叉树的遍历以及完全二叉树等6种详解-mikechen

所以通过下图的左旋和右旋来解决上面的平衡问题。

最全二叉树详解：二叉树的遍历以及完全二叉树等6种详解-mikechen最全二叉树详解：二叉树的遍历以及完全二叉树等6种详解-mikechen

但也有对应的缺点，由于要维持自身的平衡，所以进行插入和删除结点操作的时候，需要对结点进行频繁的旋转。

评论交流
    说说你的看法
❯
返回顶部