数据结构二叉树遍历顺序练习
树的先根遍历和二叉树的先序遍历？
树的先根遍历和二叉树的先序遍历？
先序遍历也叫做先根遍历、前序遍历，可记做根左右（二叉树父结点向下先左后右）。
首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。
先序遍历(Pre-order)，按照根左右的顺序沿一定路径经过路径上所有的结点。在二叉树中，先根后左再右。巧记：根左右。
二叉树的先序遍历就是先遍历根节点，然后在遍历左节点，最后遍历右节点。
因此，二者的意思，是一致的。
二叉树的先序遍历顺序ABCDEF？
先序遍历二叉树规则：根-左-右
1、访问根结点；
2、先序遍历左子树；
3、先序遍历右子树。
中序遍历二叉树规则：左-根-右
1、先中序遍历左子树；
2、再访问根节点；
3、最后访问中序遍历右子树。
后序遍历二叉树规则：左-右-根
1、后序遍历左子树；
2、后序遍历右子树；
3、访问根结点。
二叉树的后序遍历结构表示法？
1、递归法
直接上代码：
//recursion
class Solution1 {
public:
vectorltintgt postorderTraversal(TreeNode* root) {
vectorltintgt ret
postHelper(ret,root)
return ret
}
private:
void postHelper(vectorltintgtamp ret,TreeNode* root)
{
if(rootNULL)return
postHelper(ret,root-gtleft)
postHelper(ret,root-gtright)
ret.push_back(root-gtval)
}
}
2、迭代法
迭代法使用一个栈来保存当前不需要访问的节点。不过，不同于中序遍历与前序遍历，在后序遍历中每一个节点需要一个标志位，来标识当前节点的左右子树是否被访问。因为在后序遍历中，只有一个节点的左右子树被访问后它才能被访问。因此，压入栈中的数据类型需要是一个pairltTreeNode*,intgt，其中用1来表示当前节点的左右子树正被访问，当再次访问到此节点时可以访问此节点；用0表示当前节点的左右子树未被访问，再次访问到此节点时需要首先访问此节点的左右子树。代码如下：
//iteration
class Solution1 {
public:
vectorltintgt postorderTraversal(TreeNode* root) {
vectorltintgt ret
if(rootNULL)return ret
stackltpairltTreeNode*,intgtgt st
st.push(make_pair(root,0))
while(!st.empty())
{
TreeNode *().first
if(().second1)
{
ret.push_back(curr-gtval)
st.pop()
}
else
{
().second1
if(curr-gtright)st.push(make_pair(curr-gtright,0))
if(curr-gtleft)st.push(make_pair(curr-gtleft,0))
}
}
return ret
}
}
3、迭代法：按照根、右、左的顺序访问然后取反
这种方法就是按照根、右、左的顺序访问，然后将结果取反即可。后序遍历的顺序是左、右、根。这种方法就可以在前序遍历的基础上修改即可。代码如下：
class Solution3 {
public:
vectorltintgt postorderTraversal(TreeNode* root) {
vectorltintgt ret
if(rootNULL)return ret
stackltTreeNode*gt st
st.push(root)
while(!st.empty())
{
TreeNode *()
st.pop()
if(curr-gtleft)st.push(curr-gtleft)
if(curr-gtright)st.push(curr-gtright)
ret.push_back(curr-gtval)
}
reverse((),ret.end())
return ret
}
}
在按照根、右、左的顺序遍历时，每个节点访问一遍，最后将结果取反时，每个节点也访问一遍，因此节点的总访问次数和方法2相同。
4、Morris方法
后序遍历的Morris方法思路比较难。但整体上还是一样的，对原来的二叉树的修改也是一样的，不同的是访问的顺序。而在后序遍历中，访问时比较麻烦。下面是整个算法的工作过程
首先建立一个临时节点dump，令其左儿子是root。并且还需要一个子过程，就是倒序输出某两个节点之间路径上的各个节点。
步骤：
当前节点设置为临时节点dump。
（1）如果当前节点的左儿子为空，则将其右儿子作为当前节点；
（2）如果当前节点的左儿子非空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点；
a) 如果前驱节点的右孩子为空，将它的右儿子设置为当前节点。当前节点更新为当前节点的左儿子；
b) 如果前驱节点的右儿子为当前节点，将它的右孩子重新设为空。倒序输出从当前节点的左儿子到该前驱节点这条路径上的所有节点。当前节点更新为当前节点的右儿子；
（3）重复以上（1）（2）直到当前节点为空。
代码如下：
//morris
class Solution4 {
public:
vectorltintgt postorderTraversal(TreeNode* root) {
vectorltintgt ret
TreeNode *dumpnew TreeNode(0)
dump-gtleftroot
TreeNode *currdump
TreeNode *pre
while(curr)
{
if(curr-gtleftNULL)
{
currcurr-gtright
}
else
{
precurr-gtleft
while(pre-gtrightampamppre-gtright!curr)
prepre-gtright
if(pre-gtrightNULL)
{
pre-gtrightcurr
currcurr-gtleft
}
else
{
reverseAddNodes(curr-gtleft,pre,ret)
pre-gtrightNULL
currcurr-gtright
}
}
}
return ret
}
private:
void reverseAddNodes(TreeNode *begin,TreeNode *end,vectorltintgtamp ret)
{
reverseNodes(begin,end)
TreeNode *currend
while(true)
{
ret.push_back(curr-gtval)
if(currbegin)break
currcurr-gtright
}
reverseNodes(end,begin)
}
void reverseNodes(TreeNode *begin,TreeNode *end)
{
TreeNode *prebegin
TreeNode *currpre-gtright
TreeNode *post
while(pre!end)
{
postcurr-gtright
curr-gtrightpre
precurr
currpost
}
}
}