二叉树和堆
声明:图片引用自《极客时间——数据结构与算法之美》二叉树 二叉树:就是最多只能有两个叉的树结构。
![二叉树和堆](https://img.it610.com/image/info9/cfe09170b0944cb6b1c79229a4d11702.jpg)
文章图片
图中1是普通的二叉树,2、3是两种特殊的二叉树。
2是满二叉树
满二叉树:叶子节点全都在最底层,除了叶子节点之外,每个节点都有左右两个子节点
3是完全二叉树
完全二叉树:叶子节点都在最底下两层,最后一层的叶子节点都靠左排列,并且除了最后一层,其他层的节点个数都要达到最大
![二叉树和堆](https://img.it610.com/image/info9/923395169c5143f28679bda34779edff.jpg)
文章图片
不是完全二叉树的例子中:
第1个,不满足叶子节点都在最底下两层
第2个,不满足最后一层的叶子节点都靠左排列
第3个,不满足除了最后一层外,其他层的节点个数要达到最大
二叉树的具体存储表示 链式存储法
![二叉树和堆](https://img.it610.com/image/info9/9ad459b57cd142bca32b40f430d981b4.jpg)
文章图片
每个节点有三个部分,data存储数据,left、right部分是指针,存储节点的指向。类似链表。
代码中,可以想到用对象构建。
顺序存储法
![二叉树和堆](https://img.it610.com/image/info9/3922224d4597444784961a0aff4879c5.jpg)
文章图片
顺序存储法,就是基于数组的存储方式。不需要像链式存储那样,每个节点还要保存left、right指针,占用额外的空间,顺序存储法只浪费一个下标0的存储空间。
当前,前提是这棵树是完全二叉树,所以完全二叉树是最适合用顺序存储法的树结构,这也是为什么完全二叉树要求最后一层子节点都靠左排列的原因。
如果节点 X 存储在数组中下标为 i 的位置,下标为 2 * i 的位置存储的就是左子节点,下标为 2 * i + 1 的位置存储的就是右子节点。反过来,下标为 i/2 的位置存储就是它的父节点。
二叉树的遍历 二叉树的三种遍历方式:
- 前序遍历
对于树中的任意节点来说,先打印这个节点,然后再打印它的左子树,最后打印它的右子树。 - 中序遍历
对于树中的任意节点来说,先打印它的左子树,然后再打印它本身,最后打印它的右子树。 - 后序遍历
对于树中的任意节点来说,先打印它的左子树,然后再打印它的右子树,最后打印这个节点本身。
节点自身什么时候打印,就是那种遍历。
节点自身最先打印,就是前序遍历;
节点自身中间的时候打印,就是中序遍历;
节点自身最后一个打印,就是后续遍历。
二叉树的遍历过程就是一个递归,只是递归的顺序不同,有了三种不同的遍历方式。
![二叉树和堆](https://img.it610.com/image/info9/3f2d32e12048466b944b5c3472df9dae.jpg)
文章图片
遍历二叉树的时间复杂度:
不管是哪种遍历方式,节点最多会被访问两次,所以总的遍历时间只和节点个数n有关,所以时间复杂度是O(n)
堆 堆结构是二叉树结构的一种,它必须满足以下要求:
- 堆是一个完全二叉树
- 每个节点的值必须都大于等于(或小于等于)其左右子节点的值
节点的值小于等于左右子节点的值,这种堆叫做小顶堆,因为它的根节点的值是最小的。
![二叉树和堆](https://img.it610.com/image/info9/bc0853f30f9e4bf1ba5747fe25c41e62.jpg)
文章图片
【二叉树和堆】1、2是大顶堆,3是小顶堆,4不是堆,因为它不是完全二叉树。
推荐阅读
- java|java 中顺序 形参和实参,Java中参数传递机制-形参和实参说明
- Java|Java方法的形参和实参
- Java基础|Java中的形参和实参
- Java数据结构之平衡二叉树的原理与实现
- MySQL|MySQL 创建多对多和一对一关系方法
- 设计模式学习笔记(三)简单工厂、工厂方法和抽象工厂之间的区别
- Python中循环的作用和分类、while循环详细讲解
- 3D 沙盒游戏之避障踩坑和实现之旅
- 【译】绘制一棵漂亮的树
- C++非继承时函数成员访问属性和类继承过程中的访问控制