數(shù)據(jù)結(jié)構(gòu)教程第二十四課遍歷二叉樹

教學(xué)目的： 掌握二叉樹遍歷的三種方法
    教學(xué)重點(diǎn)： 二叉樹的遍歷算法
    教學(xué)難點(diǎn)： 中序與后序遍歷的非遞歸算法
    授課內(nèi)容：
    一、復(fù)習(xí)二叉樹的定義
    二叉樹由三個(gè)基本單元組成：根結(jié)點(diǎn)、左子樹、右子樹
    問題：如何不重復(fù)地訪問二叉樹中每一個(gè)結(jié)點(diǎn)？
    二、遍歷二叉樹的三種方法：
    先序 1 訪問根結(jié)點(diǎn)
    2 先序訪問左子樹
    3 先序訪問右子樹
    中序 1 中序訪問左子樹
    2 中序訪問根結(jié)點(diǎn)
    3 中序訪問右子樹
    后序 1 后序訪問左子樹
    2 后序訪問右子樹
    3 訪問根結(jié)點(diǎn)
    三、遞歸法遍歷二叉樹
    先序：
    Status(PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){
    if(T){
    if(Visit(T->data))
    if(PreOrderTraverse(t->lchild,Visit))
    if(PreOrderTraverse(T->rchild,Visit)) return OK;
    return ERROR;
    }else return OK;
    }四、非遞歸法遍歷二叉樹
    中序一：
    Status InorderTraverse(BiTree T,Status(*Visit)(TElemType e)){
    InitStack(S);Push(S,T);
    while(!StackEmpty(S)){
    while(GetTop(S,p)&&p)Push(S,p->lchild);
    Pop(S,p);
    if(!StackEmpty(S)){
    Pop(S,p); if(!Visit(p->data)) return ERROR;
    Push(S,p->rchild);
    }
    }
    return OK;
    }
    中序二：
    Status InorderTraverse(BiTree T,Status(*Visit)(TElemType e)){
    InitStack(S);p=T;
    while(p||!StackEmpty(S)){
    if(p){Push(S,p);p=p->lchild;}
    else{
    Pop(S,p); if(!Visit(p->data)) return ERROR;
    p=p->rchild);
    }//else
    }//while
    return OK;
    }
    五、總結(jié)
    二叉樹遍歷的意義