後序遍歷

後序遍歷（LRD）是二叉樹遍歷的一種，也叫做後根遍歷、後序週遊，可記做左右根。後序遍歷有遞歸算法和非遞歸算法兩種。在二叉樹中，先左後右再根，即首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。

基本介紹

• 中文名：後序遍歷
• 外文名：Postorder Traversal (LRD)
• 類型：二叉樹遍歷
• 別名：後根遍歷
• 方式：先依次遍歷左右子樹，最後根結點
• 套用學科：計算機科學

定義

後序遍歷首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後遍歷根結點。即：

若二叉樹為空則結束返回，

否則：（1）後序遍歷左子樹

（2）後序遍歷右子樹

（3）訪問根結點

如右圖所示二叉樹

後序遍歷結果：DEBFCA

已知前序遍歷和中序遍歷，就能確定後序遍歷。

遞歸算法

算法1

/*public class BTNode  //二叉樹節點類型{    public BTNode lchild;    public BTNode rchild;    public char data;}*//*public string btstr                 //全局變數*/public string postOrder(BTNode t){    btstr="";                             postOrder1(r);    return btstr;}public string postOrder1(BTNode t){    if(t!=null)    {                postOrder(t.lchild);        postOrder(t.rchild);        bstr+=t.data.ToString()+" ";    }}

算法2

PROCEDURE POSTRAV(BT)IF BT<>0 THEN{    POSTRAV(L(BT))    POSTRAV(R(BT))    OUTPUT V(BT)}RETURN

算法3

struct btnode {    int d;    struct btnode *lchild;    struct btnode *rchild;};void postrav(struct btnode *bt) {    if(bt!=NULL) {    postrav(bt->lchild);    postrav(bt->rchild);    printf("%d ",bt->d);    }}

算法4

procedure last(bt:tree);begin    if bt<>nil then begin        last (bt^.left);        last (bt^.right);        write(bt^.data);    end;end;

算法5

public class TreeNode{    intval;    TreeNodeleft;    TreeNoderight;    TreeNode(intx){        val = x;    }}public void postOrder(TreeNode biTree){    TreeNode leftTree = biTree.left;    if (leftTree != null) {        postOrder(leftTree);    }    TreeNode rightTree = biTree.right;    if(rightTree != null){        postOrder(rightTree);    }    System.out.printf(biTree.val+"");}

非遞歸算法

核心思想

首先要搞清楚先序、中序、後序的非遞歸算法共同之處：用棧來保存先前走過的路徑，以便可以在訪問完子樹後,可以利用棧中的信息,回退到當前節點的雙親節點,進行下一步操作。

後序遍歷的非遞歸算法是三種順序中最複雜的，原因在於，後序遍歷是先訪問左、右子樹,再訪問根節點，而在非遞歸算法中，利用棧回退到時，並不知道是從左子樹回退到根節點，還是從右子樹回退到根節點，如果從左子樹回退到根節點，此時就應該去訪問右子樹，而如果從右子樹回退到根節點，此時就應該訪問根節點。所以相比前序和後序，必須得在壓棧時添加信息，以便在退棧時可以知道是從左子樹返回，還是從右子樹返回進而決定下一步的操作。

算法1

void postrav1(struct btnode* bt){    struct btnode* p;    struct    {        struct btnode* pt;        int tag;    }st[MaxSize];        int top=-1;    top++;    st[top].pt=bt;    st[top].tag=1;    while(top>-1)/*棧不為空*/    {        if(st[top].tag==1)/*不能直接訪問的情況*/        {            p=st[top].pt;            top--;            if(p!=NULL)            {                top++;/*根結點*/                st[top].pt=p;                st[top].tag=0;                top++;/*右孩子結點*/                st[top].pt=p->p->rchild;                st[top].tag=1;                top++;/*左孩子結點*/                st[top].pt=p->lchild;                st[top].tag=1;            }        }        if(st[top].tag==0)/*直接訪問的情況*/        {            printf("%d",st[top].pt->d);            top--;        }    }    }

算法2

void postrav2(struct btnode* bt){    struct btnode* st[MaxSize],*p;    int flag,top=-1;    if(bt!=NULL) {        do {            while(bt!=NULL) {                top++;                st[top]=bt;                bt=bt->lchild;            }            p=NULL;            flag=1;            while(top!=-1&&flag) {                bt=st[top];                if(bt->rchild==p) {                    printf("%d",bt->d);                    top--;                    p=bt;                } else {                    bt=bt->rchild;                    flag=0;                }            }        }while(top!=-1)        printf("\n");    }}