3 树

3.1 树和二叉树

3.1.1 树

在树的结构中，树的定义如下。
树（tree）是n（n>=0）个节点的有限集，当n=0时，称为空树。在任意一个非空树中，有如下特点：

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

【相关节点】

  • 根节点(root)
  • 叶子节点(leaf):没有孩子的节点
  • 父节点
  • 孩子节点
  • 兄弟节点

树的最大层级树，被称为树的高度或深度。

3.1.2 二叉树

树的每个节点最多有2个孩子节点。
树的一种特殊形式。树的每个节点最多有2个孩子节点。

二叉树的两个孩子节点，一个被称为左孩子，一个被称为右孩子。这两个孩子节点的顺序是固定的。

二叉树有两种特殊形式：满二叉树、完全二叉树。

满二叉树：一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层接上。简言之，满二叉树的每一个分支都是满的。

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

一棵树，若为满二叉树，那么一定是完全二叉树。反之，不一定。

在内存中存储：

  • 链式存储结构：一个节点含数据data，指向左孩子的left指针，指向右孩子的right指针。
  • 数组：按照层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的孩子为空，则数组的相应位置也空出来。

为什么这么设计？可以更方便的定位孩子节点、父节点。
若父节点的下标是parent，那么左孩子节点下标是2parent+1，右孩子节点下标是2parent+2。
反之，若左孩子节点下标是leftChild,那么父节点下标是(leftChild - 1)/2。
稀疏二叉树，用数组表示会很浪费空间。

3.1.3 二叉树的应用

二叉树的应用：查找操作、维持相对顺序。

  • 查找：二叉查找树。左子树上所有节点都小于根节点，右子树上所有节点都大于根节点。左右子树也都是二叉查找树。
  • 维持相对顺序：二叉排序树

1、查找

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

如果左子树不为空，则左子树上所有节点的值均小于根节点的值；
如果右子树不为空，则右子树上所有节点的值均大于根节点的值；
左、右子树也都是二叉查找树。

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

2、维持相对顺序（插入）

二叉查找树的特性保证了二叉树的有序性，因此还有另外一个名字：二叉排序树。

插入的过程中，可能会出现需要二叉树进行自平衡，例如下图的情况：

如图所示，不只是树的外观看起来怪异，查询节点的时间复杂度也退化成了O(n)。

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

3.2 二叉树的遍历

二叉树的遍历：
从节点之间位置关系的角度：
* 前序遍历：输出顺序：根节点、左子树、右子树
* 中序遍历：输出顺序：左子树、根节点、右子树
* 后序遍历：输出顺序：左子树、右子树、根节点
* 层序遍历：按照从根节点到叶子节点的层级关系，一层一层横向遍历各个节点。

从更宏观的角度:
* 深度优先遍历(前、中、后序遍历，前中后是相对根节点)
* 广度优先遍历(层序遍历)

3.3 二叉堆

二叉堆：本质上是一种完全二叉树。
二叉堆本质上是一种完全二叉树，分为2个类型：

最大堆：任何一个父节点的值，都大于或等于它左、右孩子节点的值；
最小堆：任何一个父节点的值，都小于或等于它左、右孩子节点的值。
二叉堆的根节点，叫作堆顶。最大堆的堆顶是整个堆中最大元素，最小堆的堆顶是整个堆中最小元素。
二叉堆虽然是一个完全二叉树，但它的存储方式并不是链式存储，而是顺序存储，如下图所示：

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

二叉堆的3种操作（假设是最小堆）：
1、插入节点：时间复杂度O(logn)
插入节点是通过“上浮”操作完成的：当二叉堆插入节点时，插入位置是完全二叉树的最后一个位置，将该节点与它的父节点进行比较，如果该节点小于它的父节点，那么该与它的父节点交换位置，直到比较到堆顶位置。
2、删除节点：时间复杂度O(logn)
删除节点是通过“下沉”操作完成的：将要删除的节点看作是堆顶，只看该节点及它下面的部分。因为堆顶元素要进行删除，将最后一个节点元素替换堆顶元素，将替换后的元素与它的左、右子树进行比较，如果左、右孩子节点中最小的一个比该节点小，那么该节点“下沉”，直到叶子节点。
3、构建二叉堆：时间复杂度O(n)
构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质就是让所有非叶子节点一次“下沉”。

  • 二叉堆虽然是一个完全二叉树，但是它的存储方式并不是链式存储，而是顺序存储。
  • 二叉堆是实现堆排序及优先队列的基础。

3.4 优先队列

优先队列不再遵循先入先出的原则，而是分为两种情况：

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

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

参考

https://blog.csdn.net/qq_28958301/article/details/91590545

赏

喜爱一切可爱的事物～