二叉树的三种遍历（先序中序后序）——递归非递归算法_实现二叉树的先序遍历、中序遍历和后序遍历的递归算法

回忆

在上一个关于树的博客提到了二叉树的三种遍历方式，还有一个单独的层次遍历。
先序、中序、后序本质山就是根、左、右的顺序问题
先序：根左右
中序：左根右
后序：左右根

递归算法

因为二叉树的定义（其实应该说树的定义）里面有递归的影子：每一个子树也要符合上述条件
（具体参见上一篇博客）
所以递归算法应该是最先想到的，而且因为递归的性质，函数形式也是最简单的。

先序：

void PreOrder(btree* bt)
{
   
    btree *p=bt;
    if(p)
    {
   
        cout <<p->data<< " ";
        PreOrder(p->lchild);
        PreOrder(p->rchild);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

中序：

void InOrder(btree* bt)
{
   
    btree *p=bt;
    if(p)
    {
   
        InOrder(p->lchild);
        cout << p->data<< " ";
        InOrder(p->rchild);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

后序：

void PostOrder(btree *bt)
{
   
    btree *p=bt;
    if(p)
    {
   
        PostOrder(p->lchild);
        PostOrder(p->rchild)
1
2
3
4
5
6
7
8