計(jì)算機(jī)等考二級(jí)C語(yǔ)言：二叉樹(shù)的基本操作小結(jié)

　　算法思想：利用棧來(lái)實(shí)現(xiàn)。從根結(jié)點(diǎn)開(kāi)始，只要左子節(jié)點(diǎn)非空，則進(jìn)棧，直到左子節(jié)點(diǎn)為空為止。取出棧頂元素（只是取，并去彈棧），判斷

　　1:取出的棧頂元素是否有右子節(jié)點(diǎn)，或者右子節(jié)點(diǎn)是否被訪問(wèn)過(guò)，若滿足條件（無(wú)右子節(jié)點(diǎn)，或者右子節(jié)點(diǎn)被訪問(wèn)過(guò)），則輸出該結(jié)點(diǎn)，同時(shí)彈棧，并且記錄下該訪問(wèn)的節(jié)點(diǎn)。

　　2:取出的棧頂元素，若有右子節(jié)點(diǎn)，且未被訪問(wèn)過(guò)，則指針繼續(xù)移動(dòng)到右子節(jié)點(diǎn)，重復(fù)一開(kāi)始是否又左子節(jié)點(diǎn)的判斷。

　　*/

　　void Postorder2(BTree* bt)

　　{

　　Stack st;

　　st.top=-1;

　　BTree* t;

　　int flag;

　　do

　　{

　　while (bt!=NULL)

　　{

　　st.top++;

　　st.a[st.top]=bt;

　　bt=bt->left;

　　}

　　t=NULL;

　　flag=1;

　　while (st.top!=-1 && flag)

　　{

　　bt=st.a[st.top];

　　if (bt->right==t)  //t:表示為null，或者右子節(jié)點(diǎn)被訪問(wèn)過(guò)了。

　　{

　　printf("%c ",bt->data);

　　st.top--;

　　t=bt;  //t記錄下剛剛訪問(wèn)的節(jié)點(diǎn)

　　}

　　else

　　{

　　bt=bt->right;

　　flag=0;

　　}

　　}

　　} while (st.top!=-1);

　　}