二叉树是一种存在左节点和右节点的数据结构。存在四种遍历方式，分别 为前序遍历、中序遍历、后序遍历、层次遍历。
- 前序遍历：中左右
- 中序遍历：左中右
- 后续遍历：左右中
- 层次遍历：只需要按照层次遍历即可
这里需要强调的是，所谓的次序是相对于当前节点被使用的顺序来说的
基于以上的强调，可以得出结论，可以通过前序遍历和中序遍历的结果重新 构造出原来的树，反之，任何和后序遍历的组合都不能根据遍历结果还原出 树。
通过前序遍历和中序遍历还原树的原理是，我们设前序遍历的结果为A，中 序遍历的结果为B，那么在B中寻找A[0]的下标i，那么B[0,i-1]为A[0]的左 子树节点的集合，B[i+1, len-1]为A[0]的右子树的节点的集合。同样A[1,i] 是A[0]左子树的节点集合，A[i+1,len-1]为A[0]右子树节点集合。然后，我们 通过递归分治的方法将树构建即可。
**** 遍历的递归实现和基于栈的迭代实现
- 递归实现：非常直观，不需要过多赘述
- 迭代方法
迭代实现中序遍历，取出栈顶节点，操作节点，存入节点的右节点，存入节点 的左节点，进入下一个循环。
迭代实现前序遍历，准备操作是将根节点的一直遍历当前节点的左节点，存入栈 中，直到当前节点不存在左节点。进入循环，取出栈顶节点，操作节点，存入节点 的右节点，将节点的右节点一直遍历当前节点的左节点，存入栈栈中，直到当前 节点不存在左节点。进入下一个循环。
迭代实现后序遍历。同前序遍历，不同在于将一直遍历左节点改为一直遍历右节点 存入栈中。
递归遍历和迭代遍历的代码实现。
线索二叉树是一种在基于普通二叉树的基础上在每个节点增加基于特定遍历方式的 前驱和后驱指针的数据结构。它的作用是可以用来寻找某一个节点的后驱，或者是 可以用一种线性遍历方式取代原来的递归遍历或者是基于栈的迭代遍历。一个典型 的使用例子是cpp中的map的有序遍历，我的猜测map在红黑树的基础上，每个节点 添加了前驱和后驱指针，然后通过中序遍历的方式建立线性表。关于节点插入和删除 对与前驱、后驱的影响这里先不要讨论。