定义
在数据结构中,树的定义如下。
树(tree)是n(n≥0)个节点的有限集。当n=0时,称为空树。在任意一个非空树中,有如下特点。
- 有且仅有一个特定的称为根的节点。
- 当n>1时,其余节点可分为m(m>0)个互不相交的有限集,每一个集合本身又是一个树,并称为根的子树。
树的最大层级数,被称为树的高度或深度。
二叉树
二叉树(binary tree)是树的一种特殊形式。二叉,顾名思义,这种树的每个节点最多有2个孩子节点 。注意,这里是最多有2个,也可能只有1个,或者没有孩子节点。
满二叉树: 一个二叉树的所有非叶子节点都存在左右孩子,并且所有叶子节点都在同一层级上,那么这个树就是满二叉树。
完全二叉树: 对一个有n个节点的二叉树,按层级顺序编号,则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同,则这个二叉树为完全二叉树。
物理存储结构
1.链式存储结构
每一个节点:
- 存储数据的 data 变量
- 指向左孩子的 left 指针
- 指向右孩子的 right指针
2.数组
- 按层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的左孩子或右孩子空缺,则数组的对应位置也空出来。
- 假设一个父节点的下标是parent,那么它的左孩子节点下标就是2×parent + 1 ;右孩子节点下标就是2×parent + 2。
二叉查找树
限定条件:
- 如果左子树不为空,则左子树上所有节点的值均小于根节点的值
- 如果右子树不为空,则右子树上所有节点的值均大于根节点的值
- 左、右子树也都是二叉查找树
对一个节点分布相对均衡的二叉查找树来说,如果节点总数为n,那么搜索节点的时间复杂度就是 O(logn) ,和树的深度是一样的。
遍历
从节点之间位置关系的角度来看,二叉树的遍历分为4种。
- 前序遍历(根、左、右)
- 中序遍历(左、根、右)
- 后序遍历(左、右、根)
- 层序遍历(一层一层遍历)
从更宏观的角度来看,二叉树的遍历归结为两大类。
- 深度优先遍历(前序遍历、中序遍历、后序遍历)(递归、栈)。
- 广度优先遍历(层序遍历)(队列)
二叉堆
二叉堆本质上是一种完全二叉树,它分为两个类型:
- 最大堆
最大堆的任何一个父节点的值,都大于或等于它左、右孩子节点的值。 - 最小堆
最小堆的任何一个父节点的值,都小于或等于它左、右孩子节点的值。
二叉堆的根节点叫做堆顶。
对于二叉堆,有如下几种操作。
- 插入节点。(节点上浮)
- 删除节点。(删除节点后判断然后下浮)
- 构建二叉堆。
这几种操作都基于堆的自我调整。
二叉堆使用数组存储。
假设父节点的下标是parent,那么它的左孩子下标就是 2×parent+1 ;右孩子下标就是2×parent+2。
作用:用于实现优先队列和堆排序。
优先队列
最大(小)优先队列,无论入队顺序如何,都是当前最大(小)的元素优先出队。