“ 递归背后栈的内部机制。”
之前所说过的数据结构都是一对一，即一个位于该数据结构中的数据它有一个前驱和一个后继（或者没有）。而在树中一个节点只有一个前驱，但是却有多个后继。树虽然是非线性的逻辑结构但是它依然可以用线性结构来存储。
树
树（英语：tree）是一种抽象数据类型或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，根朝上，而叶朝下的。它具有以下的特点：
①每个节点有零个或多个子节点； ②没有父节点的节点称为根节点； ③每一个非根节点有且只有一个父节点； ④除了根节点外，每个子节点可以分为多个不相交的子树；
明）。
树的一系列术语：度，叶子节点，根节点，父节点，子节点，深度，高度。
二叉树
每个节点最多含有两个子树的树称为二叉树。（我们一般在书中试题中见到的树是二叉树，但并不意味着所有的树都是二叉树。）
在二叉树的概念下又衍生出满二叉树和完全二叉树的概念
满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值，所有叶子结点必须在同一层上
在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。（最后一层缺子树）
满二叉树一定是完全二叉树，但反过来不一定成立。
二叉树性质：
在二叉树的第i层上最多有2i-1个节点 （i>=1）
二叉树中如果深度为k,那么最多有2k-1个节点。(k>=1）
n0=n2+1，其中n0表示度数为0的节点数，n2表示度数为2的节点数。
在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]是向下取整
若对含 n个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为i的结点有如下特性：
若i=1，则该结点是二叉树的根，无双亲, 否则，编号为[i/2]的结点为其双亲结点;
若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；
若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1的结点为其右孩子结点
二叉树储存
二叉树的顺序存储结构就是使用一维数组存储二叉树中的结点，并且结点的存储位置，就是数组的下标索引。
当二叉树为完全二叉树时，结点数刚好填满数组。当二叉树不为完全二叉树时，采用顺序存储形式出现了空间浪费的情况。对于这种右斜树极端情况，采用顺序存储的方式是十分浪费空间的。因此，顺序存储一般适用于完全二叉树。
采用链式存储存储二叉树，这种链表称为二叉链表。由二叉树定义可知，二叉树的每个结点最多有两个孩子。因此，可以将结点数据结构定义为一个数据和两个指针域。
二叉树遍历
先序遍历：先根节点->遍历左子树->遍历右子树。从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左再向右的方向访问。
中序遍历：遍历左子树->根节点->遍历右子树。从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左再向右的方向访问。
后序遍历：遍历左子树->遍历右子树->根节点。从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左再向右的方向访问。
二叉树遍历应用
经过遍历把非线性结构变成线性结构
1 输出二叉树中的节点
2 输出二叉树的叶子节点
3 统计叶子结点数目
4 建立二叉链表方式存储的二叉树
5 求二叉树高度
6 按树形状打印的二叉树
逆中序便利实现横向树状打印
void PrintTree(TreeNode Boot,int nLayer) { if(Boot == NULL) RETURN; PrintTree(Boot->RClild,nLayer+1); // 访问根结点的操作 for(int i = 0;i<nLayer;i++) printf(" " ); printf("%c/n",Boot->ch); PrintTree(Boot->LChild,nLayer+1);// 递归调用遍历左子树，层次值和打印位置有关 }
思考题：可用何种便利实现二叉树的左右子树交换？
先序后序都可以，中序不行，根结点在中间，是一种对称性的遍历，左子树遍历结束之后已经交换，再遍历右子树（此时右子树是原来的左子树）会回到原结果
递归遍历和消除是最重要的两部分
基于栈的递归消除
递归转到非递归的原因：
递归执行效率很低
运行环境没有递归机制
递归转化的两种方法：
直接尾递归：可化为直线型，用循环替代递归
复杂情况：递归问题无法直接转换成循环，采用工作栈消除递归
将递归中系统隐含的栈-》用户自己操纵的栈（工作栈提供一种控制结构）
递归进层：
1 保留本层参数，返回地址
2 给下层参数赋值，传递参数，分配局部数据空间
3 控制转向入口，新层开始
递归退层：
1 恢复上层
2 传递结果
3 转断点执行
while遍历左子树，两个大循环相套
p当前结点q直接前驱，控制L访问完之后该去右子树，如果没有右子树访问根
