二叉树的四种遍历方法详解：递归与迭代实现

二叉树的四种遍历方法详解：递归与迭代实现

二叉树的遍历是数据结构和算法中的基础内容，掌握二叉树的遍历方法对于理解更复杂的算法和数据结构至关重要。本文将详细介绍二叉树的四种遍历方法：前序遍历、中序遍历、后序遍历和层序遍历，并分别给出递归和迭代两种实现方式。

一、前序遍历

前序遍历的顺序是：根节点-左子树-右子树。

1. 递归遍历

void preorder(BinTree *T)
{
    if(T==NULL)
        return;
    cout << T->data;
    preorder(T->left);
    preorder(T->right);
}

2. 迭代遍历（用栈实现）

void preorder2(BinTree *T)
{
    if(T==NULL)
        return;
    stack<BinTree*>s;
    BinTree *pcur; 
    pcur = T;
    while (pcur || !s.empty())
    {
        if (pcur)
        {
            cout << pcur->data;
            s.push(pcur);
            pcur = pcur->left;
        }
        else
        {
            pcur = s.top();
            s.pop();
            pcur = pcur->right;
        }
    }
}

二、中序遍历

中序遍历的顺序是：左子树-根节点-右子树。

1. 递归遍历

void inorder(BinTree *T)
{
    if(T == NULL)
        return;
    inorder(T->left);
    cout << T->data;
    inorder(T->right);
}

2. 迭代遍历（用栈实现）

void inorder2(BinTree *T)
{
    if(T == NULL)
        return;
    stack<BinTree*>s;
    BinTree *pcur;
    pcur = T;
    while (pcur || !s.empty())
    {
        if (pcur)
        {
            s.push(pcur);
            pcur = pcur->left;
        }
        else
        {
            pcur = s.top();
            s.pop();
            cout << pcur->data;
            pcur = pcur->right; 
        }
    }
}

三、后序遍历

后序遍历的顺序是：左子树-右子树-根节点。

1. 递归遍历

void postorder(BinTree *T)
{
    if (T==NULL)
        return;
    postorder(T->left);
    postorder(T->right);
    cout << T->data;
}

2. 迭代遍历（用栈实现）

void postorder2(BinTree *T)
{
    if(T == NULL)
        return;
    stack<BinTree*>s;
    s.push(T);
    BinTree *pcur;
    pcur = NULL;
    while (!s.empty())
    {
        pcur = s.top();
        if (pcur->left == NULL && pcur->right == NULL)
        {
            cout << pcur->data;
            s.pop();
        }
        else
        {
            if(pcur->right)
            {
                s.push(pcur->right);
                pcur->right = NULL;
            }
            if (pcur->left)
            {
                s.push(pcur->left);
                pcur->left = NULL;
            } 
        }
    }
}

四、层序遍历

层序遍历是图的广度优先搜索的应用，常用队列结构实现。

1. 迭代遍历

void leveltraversal(BinTree *T)
{
    queue<BinTree*> s;
    s.push(T);
    BinTree* pcur;
    while (!s.empty())
    {
        pcur=s.front();
        cout<<pcur->data;
        s.pop();
        if (pcur->left)
        {
            s.push(pcur->left);
        }
        if (pcur->right)
        {
            s.push(pcur->right);
        }
    } 
}

2. 分层遍历二叉树

分层遍历二叉树，即从上到下按层次访问该树，每一层单独输出一行。

last等于节点1,1入队列，打印1并弹出1，将1的左右孩子放入队列，2入队列，并让nlast等于节点2,3入队列并让nlast等于节点3，此时发现last与之前出队列的1节点相等，换行，并将nlast赋给last（等于节点3）。
接下来，节点2出栈，打印节点2，并让结点2的孩子进入队列，节点4进入队列并让nlast等于节点4，节点3出队列并打印节点3，让节点3的孩子进入队列，节点5进入队列并让nlast等于节点5，节点6进入队列并让nlast等于节点6，此时发现last与上次出队列的节点3相等，于是换行，并将nlast赋给last（等于节点6），接下来类此。

void leveltraversal3(BinTree *T)
{
    if(T == NULL)
        return;
    queue<BinTree*>s;
    s.push(T);
    BinTree *pcur,*last,*nlast;
    last = T;
    nlast = NULL;
    while (!s.empty())
    {
        pcur = s.front();
        cout << pcur->data;
        s.pop(); 
        if (pcur->left)
        {
            s.push(pcur->left);
            nlast = pcur->left;
        }
        if (pcur->right)
        {
            s.push(pcur->right);
            nlast = pcur->right;
        }
        if (last == pcur)
        {
            cout << endl;
            last = nlast;
        } 
    }
}