什么是前序, 中序, 后序

首先先介紹一下三種遍歷二叉樹(shù)的方法:

1. 前序：先根結(jié)點(diǎn)后左孩子最后右孩子
2. 中序：先左孩子后根結(jié)點(diǎn)最后右孩子
3. 后序：先左孩子后右孩子最后根結(jié)點(diǎn)
   
   二叉樹(shù)例子
   
   例如上圖中的二叉樹(shù)我們的遍歷輸出分別為:
   前序: GDAFEMHZ
   中序: ADEFGHMZ
   后序: AEFDHZMG

代碼部分

#include<cstdio>
#include<iostream>
#include<stack>//這是關(guān)于C++隊(duì)列以及棧的庫(kù)模板調(diào)用
#include<queue>//我的博客中有一篇關(guān)于這些庫(kù)函數(shù)的使用
#include<iomanip>
#include<cstdlib>
#define MAXSIZE 100

using namespace std;

int flag[MAXSIZE];

typedef struct BiTNode
{
    char data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;//定義二叉樹(shù)的結(jié)構(gòu)體

void CreateBiTree(BiTree &T)
{
    char ch;
    cin>>ch;
    if(ch == '#') T = NULL;
    else
    {
        T = new BiTNode;
        T->data = ch;
        CreateBiTree(T -> lchild);//輸入左子樹(shù)
        CreateBiTree(T -> rchild);//輸入右子樹(shù)
    }
}//采用先序遞歸的形式創(chuàng)建二叉樹(shù), 當(dāng)用戶輸入"#"時(shí),為空作用域
//例如我們上面的例子,輸入上面的圖片中二叉樹(shù)時(shí)這個(gè)函數(shù)的輸入格式為:
//GDA##FE###MH##Z###

void show_DLR(BiTree &T)//先序遍歷
{
    BiTree p, l, k;
    p = T;
    l = new BiTNode;
    k = new BiTNode;
    stack<BiTree>m;//這個(gè)遍歷我采用棧壓入元素, 隊(duì)列彈出元素的
                   //格式
    queue<BiTree>n;
    while(p || !n.empty())
    {
        if(p)//遍歷左子樹(shù)
        {
            m.push(p);//分別將二叉樹(shù)的結(jié)點(diǎn)壓入棧和隊(duì)列中
            n.push(p);
            p = p->lchild;
        }
        else
        {
            k = n.front();
            n.pop();//注意此時(shí)彈出的為隊(duì)列中的第一個(gè)元素
            cout<<setw(4)<<k->data;
            l = m.top();
            m.pop();
            p = l->rchild;
        }
    }
    cout<<endl;
}

void show_LDR(BiTree &T)//中序遍歷
{
    BiTree p, q;
    stack<BiTree>s;//和上面的先序遍歷很像
                   //只不過(guò)在中序遍歷中我們只用一個(gè)棧就可以完成
    p = T;
    q = new BiTNode;
    while(p || !s.empty() )
    {
        if(p)
        {
            s.push(p);
            p = p->lchild;
        }
        else
        {
            q = s.top();
            s.pop();
            cout<<setw(4)<<q->data;
            p = q->rchild;
        }
    }
    cout<<endl;
}

void show_LRD(BiTree &T)//后序遍歷是最為頭疼的
{//這里我設(shè)置了一個(gè)全局?jǐn)?shù)組為flag
    BiTree p, m, n;
    stack<BiTree>s;
    int i = 0;
    p = T;
    while(p)
    {//將當(dāng)前左子樹(shù)全部壓入堆棧中
        s.push(p);
        flag[s.size()] = 0;//棧中的庫(kù)函數(shù)s.size()返回當(dāng)前棧中
                           //元素的個(gè)數(shù)
                           //其目的主要是設(shè)置一個(gè)標(biāo)志位看看
                           //當(dāng)前節(jié)點(diǎn)是否被訪問(wèn)過(guò)
        p = p->lchild;
    }
    while(!s.empty())
    {
        p = s.top();
        if(!p->rchild || flag[s.size()])
        {//沒(méi)有右子樹(shù)或者當(dāng)前的結(jié)點(diǎn)的右子樹(shù)被訪問(wèn)過(guò)就輸出
            m = s.top();
            s.pop();
            cout<<setw(4)<<m->data;
        }
        else
        {
            flag[s.size()] = 1;//已訪問(wèn)
            m = p->rchild;
            while(m)
            {//因?yàn)闉楹笮虮闅v,將當(dāng)前結(jié)點(diǎn)的左子樹(shù)分別再壓入堆棧
                s.push(m);
                flag[s.size()] = 0;
                m = m->lchild;
            }
        }
    }
}

int main()
{
    BiTree L;
    CreateBiTree(L);
    show_DLR(L);
    show_LDR(L);
    show_LRD(L);
    return 0;
}