05 - 二叉树的认识

树形结构是一对多的关系，而且树的定义是递归的，因为在树的定义中又用到树的定义。

定义：
树是由n(n>=0)个节点组成的有限集合，其中如果n=0，是一颗空树，如果n>0,这n个节点存在且仅存在一个节点作为树的根节点，其余节点可分为m个互不相交的有限集，其中每个子集本身又是一颗符合本定义的树，称为根的子树。
每一个节点可以有零个或多个后继节点，但有且只有一个前驱节点（根节点除外）。

是一种顺序存储结构，在节点中存储节点的值，同时存放指向双亲节点的指针
优点是查找双亲方便

是一种链式存储结构，在节点中存储节点的值，同时存放指向所有包含其所有孩子节点的指针。
指针域的个数就是树的度
优点是查找孩子方便

是一种链式存储结构
有三个域

最大的优点是可以方便的实现树和二叉树的相互转换

先根遍历：

后根遍历：

层次遍历：

二叉树是有限的节点集合，这个集合或者是空，或者是由一个根节点和两颗互不相交的称为左子树和右子树的二叉树构成。

二叉树与度为2的树的差异

在一棵二叉树中，如果所有分支节点都有左孩子节点和右孩子节点，并且叶子节点都集中在二叉树的最下层，这样的二叉树就是满二叉树
满二叉树的高度为h，且有2^h-1个节点的

特点：

若二叉树最多只有最下面两层的节点的度数小于2，并且最下面一层的叶子节点都一次排列在该层最左侧的位置上，这样的二叉树就是完全二叉树

特点：

二叉查找树的节点是有序的，也叫二叉搜索树、有序二叉树、排序二叉树。
若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值，若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值。

特点：

优点： 因为有序所以便于查找

二叉树中任意一个节点的左右子树的高度相差不能大于 1，谓之平衡

特点：

1.平衡二叉树要么是一棵空树
2.要么保证左右子树的高度之差不大于 1
3.子树也必须是一颗平衡二叉树

红黑树是一种自平衡的二叉查找树，它可以进行高效的查找。

它是为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生的，时间复杂度为O(lgn)。

特点：

1.每个节点或者是黑色，或者是红色
2.根节点是黑色
3.每个叶子节点（NIL）是黑色。[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
4.如果一个节点是红色的，则它的子节点必须是黑色的
5.从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。因为需要更加平衡

过程：

示例

转化前：

转化后

将上面的反过来就可以

有两种，顺序存储二叉树和链式存储二叉树，一般使用链式存储结构，如果是完全二叉树可以使用顺序存储结构。

说明：

使用：

特点： 查询快，增删慢

每个节点存储有节点数据、左孩子节点指针、右孩子指针

说明：

特点： 增删快

构造原理：
同一棵树有唯一的先序序列、中序序列、后序序列，但是不同的二叉树可能有相同的先序序列、中序序列、后序序列，
所以如何根据这些序列来构造二叉树呢，需要中序序列加上先序序列（或后序序列），这是因为先序或后序会确定根节点，中序序列会确定左右孩子节点，以此来确定二叉树。

中序序列+先序序列

中序序列+后序序列

案例：
先序序列为：ABC
中序序列为：ACB

说明：

遍历是指访问二叉树中所有节点，并且每个节点只访问一次
根节点可以放在先、中，后三个地方、又因为左右子树的顺序不一样，所以可以分为六种遍历方式，再加上层次遍历，共有七种

下面以先左子树，后右子树的方式来说明

先序遍历
1、先访问根节点
2、先序遍历左子树
3、先序遍历右子树

中序遍历
1、中序遍历左子树
2、访问根节点
3、中序遍历右子树

后序遍历
1、后序遍历左子树
2、后序遍历右子树
3、访问根节点

层次遍历
1、访问根节点
2、依次访问第二层、第三层

案例

先序遍历：1、2、4、5、7、8、3、6
中序遍历：4、2、7、5、8、1、3、6
后序遍历：4、7、8、5、2、6、3、1
层次遍历：1、2、3、4、5、6、7、8