文章列表的开头遍历1 .递归实现2 .辅助堆栈的使用3.Morris遍历(二叉树的开头遍历)二叉树的中序遍历)二叉树的后序遍历)二叉树的三种遍历的对比和图像说明
二叉树的3种扫描方式中，每种扫描方式都有3种实现方式。
节点定义：
struct TreeNode{ int val； TreeNode *left，*right； treenode(intval ) { this-val=val； this -left=this-right=NULL； }； 顺序遍历
以上图为例。 谈谈树的三种扫描方法吧。
第一个遍历：访问根节点，然后访问左边的孩子，最后访问右边的孩子。
因此，上述扫描的结果为GEDACHS。
接下来，我们来看看具体的代码实现
1 .递归实现1.voidpreorder(treenode*root ) if ) root==空) return； coutroot-valendl； reorder (根左)； reorder(root-right )； } 2.使用辅助栈实现思路：1.将根节点放入栈中
2 .从堆栈的最上面一个一个地弹出节点，访问该节点
3 .将当前节点右边的孩子放入堆栈
4 .将当前节点左边的孩子放入堆栈
具体实施：
voidpreorder2(treenode*root ) if ) root==null ) return； stackTreeNode* stk； //堆栈空间STK.push(root )； while (！ stk.empty () { TreeNode* pNode=stk.pop )； coutpNode-val； if(pnode-right！=NULL ) STK.push(pnode-right )； 密码左！=NULL ) STK.push(pnode-left )； }} 3.Morris遍历Morris遍历，常数空间可在o(n )时间内完成二叉树遍历。
o )1)空间遍历困难的是，在遍历的子节点时如何返回父节点？
Morris遍历算法通过修改叶节点左右空指针指向其前驱节点或后继节点来实现。
其本质：作为线索的二叉树利用叶节点的空right指针指向中顺序扫描的后续节点，从而避免对堆栈的依赖。
具体实施：
voidpreorder(treenode*root ) if ) root==null ) return； TreeNode* pNode=root； wile(pnode！=null(if ) pnode-left==null ) { coutpNode-valendl； pNode=pNode-right； } else{ TreeNode* pPre=pNode-left； while(ppre-right！=空ppre-right！=pnode(ppre=ppre-right； }if(ppre-right==null ) ({ /* code */pPre-right=pNode； coutpNode-valendl； pNode=pNode-left； } else{ pPre-right=NULL； pNode=pNode-right； } }附：二叉树的先序遍历二叉树的先序遍历
附：二叉树的中序遍历二叉树的中序遍历
附：二叉树的后序遍历二叉树的后序遍历
附：二叉树三种遍历对比和图片说明二叉树三种遍历对比和图片说明