树：二叉树，完全二叉树，满二叉树，平衡二叉树，二叉搜索树，红黑树，的原理及其应用

树

1. 树状图是一种数据结构，它是由 n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因 为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
2. 每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除 了根结点外，每个子结点可以分为多个不相交的子树；
   
   

二叉树的原理精讲

二叉树是一个每个结点最多只能有两个分支的树，左边的分支称之为左子树，右边的分支称之为右子树.

二叉树一般采用链式存储方式：每个结点包含两个指针域，指向两个孩子结点，还包含一个数据域，存储结点信息。

1. 完全二叉树:若设二叉树的高度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层有叶 子节点，并且叶子结点都是从左到右依次排布，这就是完全二叉树（堆就是完全二叉树）。
2. 满二叉树:除了叶结点外每一个结点都有左右子节点且叶子结点都处在最底层的二叉树。
3. 平衡二叉树:又被称为 AVL 树，它是一颗空树或左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都 是一棵平衡二叉树
4. 二叉搜索树:又称二叉查找树、二叉排序树（Binary Sort Tree）。它是一颗空树或是满足下列性质的二叉树： (1）若左子树不空，则左子树上所有节点的值均小于或等于它的根节点的值；(2）若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值； (3）左、右子树也分别为二叉排序树。
5. 红黑树:是每个节点都带有颜色属性（颜色为红色或黑色）的自平衡二叉查找树，满足下列性质： (1）节点是红色或黑色； (2）根节点是黑色； (3）所有叶子节点都是黑色； (4）每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节 点。(5）从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

二叉搜索树插入节点

将要插入的结点 e，与节点 root 节点进行比较，若小于则去到左子树进行比较，若大于则去到右子树进行比较，重复以上 操作直到找到一个空位置用于放置该新节点。

二叉搜索树删除节点

将要删除的节点的值，与节点 root 节点进行比较，若小于则去到左子树进行比较，若大于则去到右子树进行比较，重复以 上操作直到找到一个节点的值等于删除的值，则将此节点删除。删除时有 4 中情况须分别处理：

1. 删除节点不存在左右子节点，即为叶子节点，直接删除
2. 删除节点存在左子节点，不存在右子节点，直接把左子节点替代删除节点
3. 删除节点存在右子节点，不存在左子节点，直接把右子节点替代删除节点
4. 删除节点存在左右子节点，则取左子树上的最大节点或右子树上的最小节点替换删除节点。

二叉树的遍历

二叉树的遍历是指从根结点出发，按照某种次序依次访问所有结点，使得每个结点被当且访问一次。共分为四种方式：

1. 前序遍历 - 先访问根节点，然后前序遍历左子树，再前序遍历右子树
2. 中序遍历 - 先访问根节点的左子树，然后访问根节点，最后遍历右子树
3. 后序遍历 - 从左到右，先叶子后节点的方式遍历访问左右子树，最后访问根节点
4. 层序遍历 - 从根节点从上往下逐层遍历，在同一层，按从左到右的顺序对节点逐个访问

前序遍历示意图:

中序遍历示意图:

后序遍历示意图:

层次遍历示意图: