数据结构和算法学习汇总

重点学习：

1、二叉树的认识
2、二叉树的遍历和构造
3、二叉树与森林的转换

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

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

1、树的基本概念

• 度
  • 节点的度：某个节点的子树的个数称为该节点的度
  • 树的度：所有节点中最大的度就是树的度，通常将度为m的树称为m次树。
• 分支节点和叶子节点
  • 分支节点：度不为0的节点为分支节点
  • 叶子节点：度为0的节点为叶子节点
• 路径与路径长度
  • 对于任意两个节点a和d,如果树中存在一个节点序列abcd，使得序列中除了a外的任一节点都是其在序列中的前一节点的后继节点，这个节点序列就是a到d的一条路径
  • 路径长度就是这个路径所有节点数-1，也就是路径上分支数目
• 孩子节点、双亲节点、兄弟节点
  • 每个节点的后继节点叫做孩子节点
  • 每个节点的前驱节点叫做双亲节点
  • 具有同一双亲节点的孩子节点互为兄弟节点
• 节点的层次和树的高度
  • 树中的每一个节点都处在一定的层次上
  • 根节点在第一层，它的孩子节点在第二层，以此类推
  • 最大层次称为树的高度，也叫深度
• 有序树和无序树
  • 若树中各节点的子树是按照一定的次序从左向右安排的，且相对次序不能随意变换，则称为有序树，否则为无序树
• 森林
  • n个互不相交的树的集合称为森林

2、树的简单认识

2.1 存储结构

2.1.1 双亲存储结构

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

2.1.2 孩子链存储结构

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

2.1.3 孩子兄弟链存储结构

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

• 一个数据元素域
• 一个指向该节点的第一个孩子节点的指针域
• 一个指向该节点的下一个兄弟节点的指针域

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

基本运算

先根遍历：

• 先访问根节点，再从左到右遍历根节点的每一颗子树
• 子树的遍历也采用先根遍历
• 根节点-左孩子-右孩子

后根遍历：

• 先从左到右的次序遍历根节点的每一颗子树
• 再遍历根节点
• 左孩子-根节点-右孩子

层次遍历：

• 从根节点开始，从上到下，从左到右遍历树中的每一个节点

二叉树的认识

定义

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

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

• 度为2的树至少有一个节点的度为2，二叉树可以没有
• 度为2的树不区分左右子树，二叉树严格区分左右子树

二叉树的类型

满二叉树

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

满二叉树.png

特点：

• 叶子节点都在最下一层
• 只有度为0和度为2的节点

完全二叉树

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

完全二叉树.png

特点：

• 叶子节点只可能出现在层次最大的两层上
• 最大层次的叶子节点，都依次排列在该层最左侧的位置上
• 如果有度为1的节点，只可能有1个，而且只有左孩子没有右孩子
• 按层序编号后，一旦出现某节点（编号为i)为叶子节点或只有做孩子，则大于i的节点均为叶子节点
• 当节点总数n为奇数时，没有度为1的节点，当为偶数是，有度为1的节点

二叉查找树

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

二叉查找树.png

特点：

• 任意节点的左、右子树也分别为二叉查找树
• 没有键值相等的节点

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

平衡二叉树

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

特点：

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

红黑树（R-B Tree)

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

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

红黑树.png

特点：

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

二叉树的性质

• 非空二叉树上叶子节点数等于双分支节点数+1
• 第i层至多有2^(i-1)个节点
• 高度为h的二叉树最多有(2^h)-1个节点

二叉树与树、森林之间的转换

树、森林转换为二叉树

过程：

1. 第一个颗树的根节点作为二叉树的根节点
2. 一棵树中的一个分支节点的最左边孩子节点作为左孩子节点
3. 一个节点的兄弟节点都作为自己的右孩子节点
   1. 如果有多个兄弟，就把下一个兄弟节点作为自己的右孩子节点
   2. 下一个兄弟节点再把自己的下个兄弟节点作为自己的右孩子节点
4. 下一棵树的根节点作为上一棵树的根节点的右孩子节点

示例

转化前：

转化前森林.png

转化后

转化后二叉树.png

二叉树转换为森林、树

将上面的反过来就可以

1. 把一棵树的根节点的所有左孩子节点作为一棵树
   1. 将左节点作为自己的左孩子节点，将左孩子节点的右孩子节点作为其兄弟节点
   2. 将左节点的左孩子节点作为自己的左孩子节点
2. 将根节点的右孩子节点作为一棵树的根节点
   1. 也同样的方式查找自己的左右孩子节点

存储结构

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

顺序存储二叉树

顺序存储结构.png

说明：

• 存储的位置需要反应出节点间的逻辑关系，这里用到了层次排序方式
• 这里也可以看到，如果某个节点不存在，数组中的相应位置也填空

使用：

• 对于完全二叉树来说，是十分合适的，因为他可以充分利用存储空间
• 但是对于一般的二叉树来说，会造成空间的浪费

特点： 查询快，增删慢

链式存储二叉树

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

节点结构.png 链式存储结构.png

说明：

• 节点的逻辑关系通过指针来体现

特点： 增删快

二叉树的构造

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

中序序列+先序序列

• 任何n(n>=0)个不同节点的二叉树，都可由它的中序序列和先序序列唯一确定
• 先序序列可以确定一颗二叉树的根节点
• 中序序列用来确定左、右子树的中序序列

中序序列+后序序列

• 左右孩子的确定也是通过中序序列
• 只不过他的后序序列确认根节点的方式与先序的不一样

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

说明：

• 通过先序序列得知ABC中的根节点为A
• 通过中序序列得知CB为右子树
• 通过先序序列得知CB的根节点为B
• 再通过中序序列得知C是左子树

案例.png

二叉树的遍历

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

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

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

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

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

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

案例

二叉树的遍历.png

先序遍历：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