数据结构基础--二叉树

先序遍历先从二叉树的根开始，然后到左子树，再到右子树。

遍历的结果是：ABDCEF

中序遍历先从左子树开始，然后到根，再到右子树。

遍历的结果是：DBAECF

后序遍历先从左子树开始，然后到右子树，再到根。

遍历的结果是：DBEFCA

打印自己，然后先遍历左节点再遍历右节点

这里的栈用处是为了保存二叉树的结构，以弥补二叉树无法获取父节点的结构特性。

不过需要注意的是后入栈的为左孩子，以保证优先遍历左侧。

第一个栈的处理顺序为，自上而下，自右而左。经过第二个栈的逆序，就变成了自下而上，自左而右。

每次将新节点加入队列时，将nlast更新成新节点。

当当前打印的节点等于last，执行换行并将last更新到下一行nlast。

举个例子(用 ! 分割，用 # 表空):

将序列化字符串转化成数组(比如这里通过 ! 分割)

所以我们需要引入一个变量 setleft 来确定下一次需要构建的节点方向。

每次构建新节点之后，下一次都会尝试构建其左侧节点。

而每次遇到空节点后，都会将顶元素推出，并尝试构建其的右侧节点。

因为他的队列，只负责记录下一次想要处理的节点。

并不需要在意左右与层级倒退，只需要处理节点为空的情况即可。

如下图中第三棵二叉树。

2节点的子树下方，左侧高度为2，右侧高度为0。所以不是一个平衡二叉树。

一旦一侧子节点为空，另一侧若高度大于2，则判定为否

目的都是提高搜索二叉树的效率，调整代价降低。

第一个错误的节点为第一次降序较大的节点

第二个错误的节点为第二次降序较小的节点

第一个错误的节点为此次降序较大的节点

第二个错误的节点为此次降序较小的节点

除最后一层无任何子 节点 外，每一层上的所有结点都有两个子结点二叉树。

从图形形态上看，满二叉树外观上是一个三角形

这种满二叉树的层数为L，节点数为N。

则N = 2^L-1 ,L = log(N+1)

满二叉树的结点要么是叶子结点，度为0，要么是度为2的结点，不存在度为1的结点。

在满二叉树的基础上，最后一层所有的结点都连续集中在最左边，这就是完全二叉树。

先遍历左子树左边界，再遍历右子树左边界。从而判断哪边为满二叉树。

满二叉树侧，N=2^H。非满二叉树侧，递归。

每层只遍历一个节点的子树，总计LogN。

每个子树获取右子树左边界遍，需要经历LogN次计算。

总复杂度O((LogN^2))

如果从下标从1开始存储，则编号为i的结点的主要关系为：

双亲：下取整 （i/2）

左孩子：2i

右孩子：2i+1

如果从下标从0开始存储，则编号为i的结点的主要关系为：

双亲：下取整 （(i-1)/2）

左孩子：2i+1

右孩子：2i+2

2的后序节点为3，2的前驱节点为1

下图中2，1两节点距离为2。3，5节点距离为5

三个情况下最大的结果，就是以head为头节点的整棵树上最远的距离。

Swift 算法实战之路：二叉树

左神牛课网算法课

1 定义

2 前序遍历（根左右）

前序遍历 通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。

图3.13所示二叉树访问如下：

则3.13所示二叉树的前序遍历输出为：

ABDHIEJCFG

3 中序遍历(左根右)

中序遍历 就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。

图3.13所示二叉树中序访问如下：

则3.13所示二叉树的中序遍历输出为：

HDIBJEAFCG

4 后序遍历(左右根)

后序遍历 就是从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问。

图3.13所示二叉树后序访问如下：

则图3.13所示二叉树的后序遍历输出为：

HIDJEBFGCA

1 定义

2 图解实例

选取一个节点为参照根节点，会发现所有的左侧子节点小于等于参照点，右侧大于等于参照点。

比如根节点9， 9所有的 左侧子节点（5、2、7、1、3） 都小于等于9.

比如根节点13，13所有的 左侧子节点（11、10、12） 都大于等于13.

3 查找

查找节点 10：根节点9开始，10>9 右侧，10<13 左侧，10<11 左侧，找到10.

下图是二叉查找树的极端情况

二叉查找树就是为了提高查询效率，而当前这种和我们写了一堆for循环是一样的。

为了应对这种情况：又出现了平衡二叉树--红黑树。后面会提到。

1 定义

红黑树的特性 :

（1）每个节点或者是黑色，或者是红色。

（2）根节点是黑色。

（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]

（4）如果一个节点是红色的，则它的子节点必须是黑色的。也就是不能有连在一起的红色节点，但是可以有连在一起的黑色节点

（5）满足所有的二叉查找树的性质

红黑树示意图如下：

2 变换规则

左旋又分为两种情况，

（1）我们操作的结点E是整棵树的根节点，那么左旋实现为下面步骤

（2）我们操作的结点E有父结点，那么左旋实现为下面步骤

3）右旋

右旋同样分为两种情况，与左旋情况类似，故实际操作参考左旋。

3 插入

注意 ：上述描述中一个很重要的点是，在插入元素时，是将元素作为叶子结点插入的，插入到原红黑树的外部结点。

插入结点染色情况

插入结点后调整和平衡过程

1.变颜色的情况： 当前结点的父亲是红色，且它的祖父结点的另一个结点（也就是叔叔结点）也是红色：

2.左旋：当前父结点是红色，叔叔结点是黑色的时候，且当前的结点时右子树，则进行左旋。左旋过程不需要进行颜色变换。

3.右旋：当前父结点时红色，叔叔结点是黑色的时候，且当前的结点是左子树，则进行右旋。右旋过程中需要进行颜色变换，具体右旋过程如下。

实例讲解

参考视频：

https://www.bilibili.com/video/BV1tE411f7tP?p=4&spm_id_from=pageDriver

    名词解释

        节点: 每个元素

        父子关系: 用来连线相邻节点之间的关系

        父节点: A节点就是B节点的父节点

        子节点:  B节点就是A节点的子节点

        兄弟节点: B、C、D这三个节点的父节点是同一个节点

        根结点: 没有父节点的节点

        叶子结点: 没有子节点的节点

        节点的高度: 节点到叶子结点到最长路径(边数)  (计数起点为0, 从下往上)

        节点的深度: 根节点到这个节点经历过的边个数  (计数起点为0, 从上往下)

        节点的层数:     节点到深度 + 1  (计数起点为1)

        树的高度: 根节点的高度

    特点

        最常用的树数据结构

        每个节点最多有两个子节点(左子节点、右子节点)

         满二叉树: 叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点

         完全二叉树:  叶子节点都在最底下两层，最后一层的叶子节点都 靠左排列 ，并且除了最后一层，其他层的节点个数都要达到最大

        二叉树存储方式

            数组顺序存储法

                通过数组下标来顺序存储数据 (i表示当前节点深度,从0开始)

                根节点: i = 1，左节点:2 * i，右节点: 2 * i + 1，父节点: i / 2

                完全二叉树采用此方式节省内存空间

            链式存储法

                每个节点需要存储三分数据:当前节点数据、左节点指针、右节点指针,比较占用空间                

            遍历

                常用方式

                前序遍历: 树任意节点，先打印当前节点，再打印它的左子树，最后打印它的右子树

                中序遍历: 树任意节点，先打印它的左子树，再打印当前节点，最后打印它的右子树

                后序遍历: 树任意节点，先打印它的左子树，再打印它的右子树，最后打印当前节点

                二叉树的前、中、后序遍历就是一个递归的过程

                时间复杂度是O(n)

                    每个节点最多被访问两次，遍历操作的时间复杂度跟节点的个数n成正比

特点

    二叉查找树为实现快速查找而生，支持快速查找一个数据、快速插入、快速删除一个数据

    特殊结构: 其左子树每个节点的值 <树的任意一个节点的值 <其右子树每个节点的值

            先取根节点，如果它等于要查找的数据，那就返回。

            如果要查找的数据比根节点的值小，那就在左子树中递归查找；

            如果要查找的数据比根节点的值大，那就在右子树中递归查找

            一般插入的数据在叶子节点上，从根节点开始依次比较要插入的数据和节点的大小关系

            如果插入数据比节点的数值大，并且节点的右子树为空，将新数据插到右子节点位置；

            如果不为空，就再递归遍历右子树，查找插入位置。

            如果插入数据比节点的数值小，并且节点的左子树为空，将新数据插到左子节点位置；

            如果不为空，就再递归遍历左子树，查找插入位置。

        针对要删除节点的子节点个数的不同，需分三种情况来处理

        1.如果要删除的节点没有子节点，步骤如下: (如图中的删除节点55)

            只需将父节点中指向要删除节点的指针置为null

        2.如果要删除的节点只有一个子节点，步骤如下: (如图中删除节点13)

            只需将父节点中指向要删除节点的指针，让它指向要删除节点的子节点即可

        3.如果要删除的节点有两个子节点，步骤如下: (如图中的删除节点18)

            首先，需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上；

            然后，再删除掉这个最小节点，因为最小节点肯定没有左子节点        

            删除操作，有个优化方案: 就是单纯将要删除的节点标记为“已删除”，

            这种方案删除操作就变简单很多，但是比较浪费内存空间

        支持快速地查找最大节点和最小节点、前驱节点和后继节点

        另外一种重要特性: 

            中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度为O(n)

            因此，二叉查找树也叫作二叉排序树

        以上几种操作都默认树中节点存储的都是数字，而且都是不存在键值相同的情况

        实际应用场景中采用对象的某个字段作为键值来构建二叉查找树，其他字段称为卫星数据

        如果存储的两个对象键值相同，两种解决方案

        1.把值相同的数据都存储在同一个节点(采用链表或支持动态扩容的数组等数据结构)   

        2.每个节点只存储一个数据，把这个新插入的数据当作大于这个节点的值来处理，如下图:

        查找操作

            当查找数据时遇到值相同的节点，继续在右子树中查找，直到遇到叶子节点才停止。

            这样就把键值等于要查找值的所有节点都查找出来        

            删除操作

                先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除

        对于同一组数据可构造不同二叉查找树。查找、插入、删除操作的执行效率都不一样

        图最左边树，根节点的左右子树极度不平衡，退化成链表，查找时间复杂度为O(n)

        最理想的情况，二叉查找树是一棵完全二叉树（或满二叉树）

        时间复杂度都跟树的高度成正比，也就是O(height)

        树的高度就等于最大层数减一，为了方便计算，我们转换成层来表示

        满二叉树: 下一层节点个数是上一层的2倍，第K层包含节点个数就是2^(K-1)

        完全二叉树: 假设最大层数是L，总的节点个数n，它包含的节点个数在1个到2^(L-1)个之间

            L的范围是[ , +1]，完全二叉树的高度小于等于

            极度不平衡的二叉查找树，它的查找性能肯定不能满足我们的需求

        平衡二叉查找树: 树的高度接近logn，时间复杂度较稳定为O(logn)

    1.排序对比

        散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序

        二叉查找树只需要中序遍历，就可以在O(n)的时间复杂度内，输出有序的数据序列

    2.性能稳定性对比

        散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定

        最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在O(logn)

    3.时间复杂度对比

        散列表查找等操作时间复杂度是常量级，因存在哈希冲突，这个常量不一定比logn小

        另外加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高

    4.结构设计对比

        散列表构造比较复杂，需要考虑:散列函数设计、冲突解决办法、扩容、缩容等

        平衡二叉查找树只需要考虑平衡性，而且目前这个的解决方案较成熟、固定

    5.空间复杂度

        散列表: 避免过多散列冲突，装载因子不能太大，特别基于开放寻址法，否则浪费太多空间

            

        

---