树和二叉树

(相关资料图)

树和图是典型的非线性数据结构

树：从“根”衍生出许多“枝干”，再从每个“枝干”衍生出许多更小的“枝干”，最后衍生出更多的“叶子”

树(tree)是n(n>=0)个节点的有限集。

当n=0时，称为空树。

在任意一个非空树中，有如下特点：

有且仅有一个特定的，称为根(root)的节点

当n>1时，其余节点可分为m(m>0)个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树

树的最大层级数，称为树的高度或深度。上图树的高度为4

二叉树(binary tree): 这种树的每个节点最多有2个孩子节点

满二叉树：一个二叉树的所有非叶子节点都存在左孩子和右孩子，并且所有叶子节点都在同一层级上

完全二叉树: 对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。

二叉树可以用 链式存储结构 或者 数组 来进行存储

链式存储结构：

二叉树的每一个节点包含3个部分，一是存储数据的data变量，二是指向左孩子的left指针，三是指向右孩子的right指针，一个节点最多可以指向左右两个孩子节点

数组存储结构：

使用数组存储时，会按照层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的左孩子或右孩子空缺，则数组的相应位置也空出来。

假设一个父节点的下标是parent， 那么它的左孩子节点的下标就是2×parent+1；

右孩子节点的下标就是2×parent +2

假设一个左孩子节点的下标是leftChild，那么它的父节点下标就是(leftChild-1) / 2；

右孩子节点的下标是rightChild，那么他的父节点下标就是(rightChild-2) / 2

二叉树主要应用在 查找操作和 维持相对顺序 这两个方面1.查找

二叉查找树(binary search tree): 也叫二叉排序树(binary sort tree)

二叉查找树在二叉树的基础上增加了以下几个条件：

* 如果左子树不为空，则左子树上所有节点的值均小于根节点的值

* 如果右子树不为空，则右子树上所有节点的值均大于根节点的值

* 左子树、右子树也都是二叉查找树

例如查找值为4的节点，步骤如下：

对于一个节点分布相对均衡的二叉查找树来说，如果节点总数是n，那么搜索节点的时间复杂度就是O(logn)，和树的深度是一样的

2. 维持相对顺序

如何解决这个问题呢？这就涉及二叉树的自平衡了；

二叉树自平衡的方式有多种，如红黑树、AVL树、树堆等；

除二叉查找树以外，二叉堆也维持着相对的顺序；

不过二叉堆的条件要宽松一些，只要求父节点的值比它的左右孩子的值都大

二叉树的遍历

遍历是一个线性操作。

二叉树，是典型的非线性数据结构，遍历时需要把非线性关联的节点转化成一个线性的序列

从节点之间位置关系的角度来看，二叉树的遍历方式有4种：

前序遍历

中序遍历

后序遍历

层序遍历

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

深度优先遍历(前序遍历、中序遍历、后序遍历)

广度优先遍历(层序遍历)

深度优先遍历：

1. 前序遍历

二叉树的前序遍历，输出顺序是根节点、左子树、右子树

2. 中序遍历

输出顺序是左子树、根节点、右子树

3. 后序遍历

输出顺序是左子树、右子树、根节点

绝大多数可以用递归解决的问题，其实都可以用另一种数据结构来解决，这种数据结构就是栈

。因为递归和栈都有回溯的特性。

使用栈来完成二叉树的前序遍历：

节点4既没有左孩子，也没有右孩子，我们需要回溯到上一个节点2；

让旧的栈顶元素4出栈，就可以重新访问节点2，得到节点2的右孩子节点5；

此时节点2已经没有利用价值（已经访问过左孩子和右孩子），节点2出栈，节点5入栈；

节点5既没有左孩子，也没有右孩子，我们需要再次回溯，一直回溯到节点1，所以让节点5出栈；

根节点1的右孩子是节点3，节点1出栈，节点3入栈；

节点3的右孩子是节点6，节点3出栈，节点6入栈；

节点6既没有左孩子，也没有右孩子，所以节点6出栈，此时栈为空，遍历结束

广度优先遍历

层序遍历: 二叉树按照从根节点到叶子节点的层次关系，一层一层横向遍历各个节点。

什么是二叉堆

二叉堆本质上是一种完全二叉树，分为最大堆和最小堆。

最大堆的任何一个父节点的值，都大于或等于它左孩子或右孩子节点的值。

最小堆的任何一个父节点的值，都小于或等于它左孩子或右孩子节点的值。

二叉堆的根节点叫作堆顶；

最大堆的堆顶是整个堆中的最大元素；

最小堆的堆顶是整个堆中的最小元素

二叉堆有：1.插入节点 2.删除节点 3.构建二叉堆

堆的自我调整: 把一个不符合堆性质的完全二叉树，调整成一个堆

1. 插入节点

目前的是最小堆；

当在二叉堆中插入节点时，插入位置是完全二叉树的最后一个位置。

2. 删除节点

从二叉堆删除节点的过程和插入节点的过程正好相反，所删除的是处于堆顶的节点；

删除最小堆的堆顶节点1

3. 构建二叉堆

把一个无序的完全二叉树调整为二叉堆，本质就是让所有非叶子节点依次“下沉”。

然后轮到节点1，如果节点1大于它的左孩子、右孩子节点中最小的一个，则节点1“下沉”。事实上，节点1小于它的左孩子、右孩子，所以不用改变。

堆的插入和删除操作，时间复杂度为O(logn);

构建堆的时间复杂度，时间复杂度为O(n)

二叉堆的代码实现

假设父节点的下标是parent，那么它的左孩子的下标就是2×parent+1；

右孩子的下标就是2×parent+2

什么是优先队列

优先队列

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

最小优先队列，无论入队顺序如何，都是当前最小的元素优先出队

优先队列的实现

可以用最大堆来实现最大优先队列

每一次入队操作就是堆的插入操作，每一次出队操作就是删除堆顶节点

入队操作：

出队操作：

二叉堆节点“上浮”和“下沉”的时间复杂度都是O(logn)，所以优先队列入队和出队的时间复杂度也是O(logn)

小结

什么是树？

树是n个节点的有限集，有且仅有一个特定的称为根的节点。当n>1时，其余节点可分为m个互不相交的有限集，每一个集合本身又是一个树，称为根的子树。

什么是二叉树？

二叉树是树的一种特殊形式，每一个节点最多有两个孩子节点。

二叉树包含完全二叉树和满二叉树两种特殊形式。

二叉树的遍历方式有几种？

根据节点之间的位置关系，可以分为前序遍历、中序遍历、后序遍历、层序遍历这4种方式；从更宏观的角度划分，可以划分为深度优先遍历和广度优先遍历两大类。

什么是二叉堆？

二叉堆是一种特殊的完全二叉树，分为最大堆和最小堆。

在最大堆中，任何一个父节点的值，都大于或等于它的左孩子、右孩子节点的值。

在最小堆中，任何一个父节点的值，都小于或等于它的左孩子、右孩子节点的值。

什么是优先队列？

优先队列分为最大优先队列和最小优先队列。

在最大优先队列中，无论入队顺序如何，当前最大的元素都会优先出队，这是基于最大堆实现的。

在最小优先队列中，无论入队顺序如何，当前最小的元素都会优先出队，这是基于最小堆实现的。

关键词：