递归（recursion）
递归的定义：
递归是一种解决问题的有效方法，在递归过程中，函数将自身作为子例程调用。
递归的思想是把一个大型复杂问题层层转化为一个与原问题规模更小的问题，问题被拆解成子问题后，递归调用继续进行，直到子问题无需进一步递归就可以解决的地步为止。
使用条件：
为了保障函数正常运行，必须避免出现死循环！所以函数中必须包括如下属性
- 必须有一个明确的中止条件
- 该函数处理的数据规模必须递减
- 可将所有其他情况拆分到基本案例
特点和应用
- 代码量相较其他解法来说少，而且容易理解。可以用有限的语句描述对象的无限集合
- 递归调用程序需要维护调用栈，而栈具有后进先出的特征，因此递归程序适合满足取反类需求，比如字符串取反，链表取反等相关有趣的算法问题。
- 具有递推关系的问题基本都可以通过递归求解。比如杨辉三角，阶乘计算等
栈和队列是线性结构的具体实现，是一种特殊的线性结构
内存是线性一维的，但现实中的事物是复杂的，所以要研究数据结构即如何将现实中的复杂数据高效的用线性一维的计算机存储空间进行存储。
树
树定义
- 有且只有一个称为根的节点
- 有若干个互不相交的子树，子树本身也是一棵树
专业术语：
- 非终端节点：实际就是非叶子节点
- 度：子节点的个数称为度
- 深度：树的层数
树分类
一般树：任意一个节点的子节点的个数不受限制
二叉树：任意一个节点的子节点的个数最多两个，且子节点位置不能更改
- 一般二叉树：
- 满二叉树：在不增加树的层数的前提下，无法再多添加一个节点的二叉树就是满二叉树，即每一层节点都是最大节点树
- 完全二叉树：如果只是删除了满二叉树最底层最右边的连续的若干节点，这样形成的二叉树就是完全二叉树
森林：n个互不相交的树的集合
树的存储
计算中硬件的存储方式是线性一维的就像一条梯子里一个一个格子一样，而现实中的问题往往是复杂多变多维的。
如何用内存保存现实中的事物？用人为定义的一种规则将其转化到计算机中保存并能还原。
非线性的树转化为一维线性的硬件去存储，按照前中后的规则存储
为什么要把树转化成完全二叉树存储？
因为不能只存有效节点，如果只存有效节点的话，根据一维的有效节点的顺序无法推算出树本来的样子。
存垃圾节点很浪费空间为啥还要用完全二叉树存储？
- 已知任何一个节点，可以知道它的父节点、子节点、有没有子节点【查找某个节点的父、子节点的速度很快】
- 知道节点的个数就能知道在第几层
有三种不同规则（前序，中序，后序）可以将树转化成一维的结构。
一般树转化为满二叉树，在把垃圾节点删掉就是完全二叉树，在存储中一般用完全二叉树存储，完全二叉树是重点。
二叉树的存储：
连续存储【完全二叉树】：
优点：查找某个节点的父节点和子节点快，查找效率高
缺点：耗内存高
链式存储【链表实现】：
一般树的存储：
- 双亲表示法：每个节点的指针域存储父节点的地址【找父节点简单，找子节点难】
- 孩子表示法：每个节点的指针域依次存储该节点的所有子节点【找子节点方便，找父节点难】
- 双亲孩子表示法：指针域分两个一个存父节点的位置，一个存所有子节点的位置【求父求子都方便】
- 二叉树表示法：保证满足任意一个节点的左指针域指向第一个孩子，右指针域指向兄弟【把普通树转化为二叉树】
森林的存储：
类似把一般树转化为二叉树，把森林转化为二叉树
树的操作
树的遍历【递归】
先序遍历【最先访问根节点】
先遍历根节点，再访问左子树，最后右子树；
中序遍历【中间访问根节点】
先遍历左子树，再访问根节点，最后右子树；
后序遍历【最后访问根节点】
先遍历左子树，再访问右子树，最后根节点；
已知两种遍历序列求原始二叉树
通过先序、中序或中序、后序能还原出原始二叉树，但是通过先序、后序是无法还原出原始二叉树的。
例子：
先序ABDGHCEFI、中序GDHBAECIF。求后序得：GHDBEIFCA
中序BDCEAFHG、后序DECBHGFA。求先序得：ABCDEFGH
- 【知先与中，用先确定”根“，中确定左右子树】
- 【知中与后，用后确定“根”，中确定左右子树】
- 【先与后都是确定“根”的，所以知道先后无法求中】
树的应用
- 树是数据库中数据组织的一种重要形式；
- 操作系统子父进程的关系本身就是一颗树；
- 面向对象语言中类的继承关系本身就是一棵树
- 哈夫曼树
二叉树代码实现：
#include<stdio.h>
#include<malloc.h>
struct BTNode
{
int data;
struct BTNode * pLchild;//p为指针，L是左，R是右；
struct BTNode * pRchild;
};
struct BTNode * CreateBTree(void)
{
struct BTNode * pA = (struct BTNode *)malloc(sizeof(struct BTNode));
struct BTNode * pB = (struct BTNode *)malloc(sizeof(struct BTNode));
struct BTNode * pC = (struct BTNode *)malloc(sizeof(struct BTNode));
pA->data = 'A';
pB->data = 'B';
pC->data = 'C';
pA->pLchild = pB;
pA->pRchild = pC;
pB->pLchild = pB->pRchild = NULL;
pC->pLchild = pC->pRchild = NULL;
return pA;
}
void PreTraverseBTree(struct BTNode * pT)
{
if(pT)//NULL可以当false用或者pT！=NULL；
{
printf("%c\n",pT->data);
if(NULL != pT->pLchild)
{
PreTraverseBTree(pT->pLchild);
}
if(NULL != pT->pRchild)
{
PreTraverseBTree(pT->pRchild);
}
}
}
void INTraverseBTree(struct BTNode *pT)
{
if(pT)//NULL可以当false用或者pT！=NULL；
{
if(NULL != pT->pLchild)
{
INTraverseBTree(pT->pLchild);
}
printf("%c\n",pT->data);
if(NULL != pT->pRchild)
{
INTraverseBTree(pT->pRchild);
}
}
}
void PostTraverseBTree(struct BTNode *pT)
{
if(pT)//NULL可以当false用或者pT！=NULL；
{
if(NULL != pT->pLchild)
{
INTraverseBTree(pT->pLchild);
}
if(NULL != pT->pRchild)
{
INTraverseBTree(pT->pRchild);
}
printf("%c\n",pT->data);
}
}
int main(void)
{
BTNode * pT = CreateBTree();//创建树
PreTraverseBTree(pT);//先序
printf("-------\n");
INTraverseBTree(pT);//中序
printf("-------\n");
PostTraverseBTree(pT);//后序
system("pause");
return 0;
}树的理论解释
什么是树？
在实际场景中，数据除了线性结构以外还存在非线性结构，树就是典型的非线性结构，比如人的家谱，书的目录等它们就像树的枝干和根一样。
在数据结构中，树的定义如下。 树（tree）是n（n≥0）个节点的有限集。当n=0时，称为空树。在任意一 个非空树中，有如下特点。
- 有且仅有一个特定的称为根的节点。
- 当n>1时，其余节点可分为m（m>0）个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。
二叉树：
二叉树（binary tree）是树的一种特殊形式。二叉，顾名思义，这种树 的每个节点最多有2个孩子节点 。注意，这里是最多有2个，也可能只 有1个，或者没有孩子节点。
二叉树节点的两个孩子节点，一个被称为左孩子（left child） ，一个被 称为右孩子（right child） 。这两个孩子节点的顺序是固定的，就像人 的左手就是左手，右手就是右手，不能够颠倒或混淆。 此外，二叉树还有两种特殊形式，一个叫作满二叉树 ，另一个叫作完 全二叉树 。 什么是满二叉树呢？ 一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在 同一层级上，那么这个树就是满二叉树。
简单点说，满二叉树的每一个分支都是满的。 什么又是完全二叉树呢？完全二叉树的定义很有意思。 对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1 到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。
数据结构可以划分为物理结构和逻辑结构。二叉树属于逻辑结构，它可以通过多种物 理结构来表达。 二叉树可以用哪些物理存储结构来表达呢？
链式存储结构。
链表是一对一的存储方式，每一个链表节点拥有data 变量和一个指向下一节点的next指针。 而二叉树稍微复杂一些，一个节点最多可以指向左右两个孩子节点，所以二叉树的每一个节点包含3部分。
存储数据的data变量
指向左孩子的left指针
指向右孩子的right指针
数组。
按照层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的左孩子或右孩子空缺，则数组的相应位置也空出来。
为什么空出相应的位置呢？
因为这样可以更方便地在数组中定位二叉树的孩子节点和父节点。 假设一个父节点的下标是parent，那么它的左孩子节点下标就 是2×parent + 1 ；右孩子节点下标就是2×parent + 2 。 反过来，假设一个左孩子节点的下标是leftChild，那么它的父节点下标就是（leftChild-1）/ 2 。假如节点4在数组中的下标是3，节点4是节点2的左孩子，节点2的下标可以直接通过计算得出。 节点2的下标 = (3-1)/2 = 1 显然，对于一个稀疏的二叉树来说，用数组表示法是非常浪费空间的。
什么样的二叉树最适合用数组表示呢？ 二叉堆一种特殊的完全二叉树，就是用数组来存储的
二叉树都有哪些遍历方式呢？
从节点之间位置关系的角度来看，二叉树的遍历分为4种。
- 前序遍历。
- 中序遍历。
- 后序遍历。
- 层序遍历。
从更宏观的角度来看，二叉树的遍历归结为两大类。
深度优先遍历 （前序遍历、中序遍历、后序遍历）。
广度优先遍历 （层序遍历）。
补充：树的层序遍历
层序遍历，顾名思义，就是二叉树按照从根节点到叶子节点的层次关系，一层一层横向遍历各个节点。由于二叉树同一层次的节点之间是没有直接关联的，所以需要借助队列这种数据结构来辅助工作。
/**
* 二叉树层序遍历
* @param root 二叉树根节点
*/
public static void levelOrderTraversal(TreeNode root){
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node = queue.poll();
System.out.println(node.data);
if(node.leftChild != null){
queue.offer(node.leftChild);
}
if(node.rightChild != null){
queue.offer(node.rightChild);
}
}
}
