极客时间数据结构与算法之美笔记23
2020-03-01 本文已影响0人
草珊瑚_6557
完全二叉树的定义
叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树。
完全二叉树和非完全二叉树
为什么完全二叉树这么定义
因为用数组存储完全二叉树是最节省内存的一种方式。
堆就是一种完全二叉树，最常用的存储方式就是数组。
二叉树的数组的顺序存储法
如果节点 X 存储在数组中下标为 i 的位置，下标为 2 * i 的位置存储的就是左子节点，下标为 2 * i + 1 的位置存储的就是右子节点。
image.png
前序遍历、中序遍历和后序遍历。
前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身
