-
後序遍歷
鎖定
後序遍歷定義
後序遍歷首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後遍歷根結點。即：
若二叉樹為空則結束返回，
圖1
（2）後序遍歷右子樹
（3）訪問根結點
如圖1所示二叉樹
後序遍歷結果：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+"");
}
後序遍歷非遞歸算法
後序遍歷核心思想
首先要搞清楚先序、中序、後序的非遞歸算法共同之處：用棧來保存先前走過的路徑，以便可以在訪問完子樹後,可以利用棧中的信息,回退到當前節點的雙親節點,進行下一步操作。
後序遍歷的非遞歸算法是三種順序中最複雜的，原因在於，後序遍歷是先訪問左、右子樹,再訪問根節點，而在非遞歸算法中，利用棧回退到時，並不知道是從左子樹回退到根節點，還是從右子樹回退到根節點，如果從左子樹回退到根節點，此時就應該去訪問右子樹，而如果從右子樹回退到根節點，此時就應該訪問根節點。所以相比前序和後序，必須得在壓棧時添加信息，以便在退棧時可以知道是從左子樹返回，還是從右子樹返回進而決定下一步的操作。
[2]
後序遍歷算法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");
}
}
