定义

在数据结构中,树的定义如下。
树(tree)是n(n≥0)个节点的有限集。当n=0时,称为空树。在任意一个非空树中,有如下特点。

  1. 有且仅有一个特定的称为根的节点。
  2. 当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种。

  1. 前序遍历(根、左、右)
  2. 中序遍历(左、根、右)
  3. 后序遍历(左、右、根)
  4. 层序遍历(一层一层遍历)

从更宏观的角度来看,二叉树的遍历归结为两大类。

  1. 深度优先遍历(前序遍历、中序遍历、后序遍历)(递归、栈)。
  2. 广度优先遍历(层序遍历)(队列)

二叉堆

二叉堆本质上是一种完全二叉树,它分为两个类型:

  1. 最大堆
    最大堆的任何一个父节点的值,都大于或等于它左、右孩子节点的值。
  2. 最小堆
    最小堆的任何一个父节点的值,都小于或等于它左、右孩子节点的值。

二叉堆的根节点叫做堆顶。

对于二叉堆,有如下几种操作。

  1. 插入节点。(节点上浮)
  2. 删除节点。(删除节点后判断然后下浮)
  3. 构建二叉堆。

这几种操作都基于堆的自我调整。

二叉堆使用数组存储。
假设父节点的下标是parent,那么它的左孩子下标就是 2×parent+1 ;右孩子下标就是2×parent+2。

作用:用于实现优先队列和堆排序。

优先队列

最大(小)优先队列,无论入队顺序如何,都是当前最大(小)的元素优先出队。