2 回答

TA貢獻1820條經(jīng)驗 獲得超10個贊
獲取頂部標簽的作用??梢缘玫揭粋€bool返回值,一般用于樹結構中。
T是要遍歷樹的根指針,后序遍歷要求在遍歷完左右子樹后,再訪問根。需要判斷根結點的左右子樹是否均遍歷過。
可采用標記法,結點入棧時,配一個標志tag一同入棧(0:遍歷左子樹前的現(xiàn)場保護,1:遍歷右子樹前的現(xiàn)場保護)。
首先將T和tag(為0)入棧,遍歷左子樹;返回后,修改棧頂tag為1,遍歷右子樹;最后訪問根結點。
typedef struct stackElement{
Bitree data;
char tag;
}stackElemType;
【算法】
void PostOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 流程圖如右,當型循環(huán)
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T,0);
T = T->lchild;
}
while ( !StackEmpty(S) && GetTopTag(S)==1){
Pop(S, T);
Visit(T->data);
}
if ( !StackEmpty(S) ){
SetTopTag(S, 1); // 設置棧頂標記
T = GetTopPointer(S); // 取棧頂保存的指針
T = T->rchild;
}else break;
}
}
- 2 回答
- 0 關注
- 943 瀏覽
添加回答
舉報