二叉树先根遍历,中根遍历序列

Question

二叉树先根遍历,中根遍历序列怎样写

Answer 1

这里的“先根”也叫做先序，“中”和“后”也一样。
先序遍历是先访问当前节点，然后再遍历左子树，最后是右子树。
中序遍历是先遍历左子树，再访问当前节点，最后是右子树。
后序遍历是先遍历左子树，再遍历右子树，最后访问当前节点。例：
一棵二叉树的先根遍历为ABCDEFG，中根遍历为CBDEAGF，则其后根遍历为：1、先序遍历的第一个当前节点一定是根节点，所以A是根
2、由于中序遍历是先遍历完左子树再访问当前节点，所以可以看出中序序列在A之前的都是A的左子树中的节点，而在A之后是A的右子树的节点。
3、这样就分成了（cbde）a (GF),三个集合。
4、我们分别再看各个集合。cbde集合中最先在先序序列中出现的是B，这说明b在这个集合中应该是第一个出现的。所以右可以再分

Answer 2

//先根遍历
void PreOrder(BinaryTreeNode* pRoot)  
{  
    if (pRoot!=NULL)  
    {  
        visit(*pRoot);//visit只是代表处理，关键的是结构  
        PreOrder(pRoot->m_pLeft);  
        PreOrder(pRoot->m_pRight);  
    }     
}

//中根遍历
void InOrder(BinaryTreeNode* pRoot)  
{  
    if (pRoot!=NULL)  
    {  
        InOrder(pRoot->m_pLeft);  
        visit(*pRoot); //visit只是代表处理，关键的是结构  
        InOrder(pRoot->m_pRight);  
    }     
}

* 这个是C/C++的递归版本，如果需要非递归或者其他语言版本可以，留言或私信我。