有了線索的二叉鏈表那么遍歷就方便多了，不需要借助棧也不需要用遞歸了，因?yàn)樗呀?jīng)把前驅(qū)后繼都連起來(lái)了，而不像二叉樹(shù)那樣，走不動(dòng)的時(shí)候就只能退棧了。 而且遍歷速度快。
算法思路：先找到中序下的第一結(jié)點(diǎn)，訪問(wèn)之;若被訪問(wèn)的結(jié)點(diǎn)的右指針為線索指針，直接取其后繼結(jié)點(diǎn)訪問(wèn);……，直到被訪問(wèn)結(jié)點(diǎn)的右子樹(shù)存在，再?gòu)南鄳?yīng)右子起找中序下的第一結(jié)點(diǎn)，……，依次類(lèi)推，直到整個(gè)樹(shù)遍歷完畢。
算法描述：
BTptr Tinorder(BTptr Thrt) //對(duì)中序線索二叉樹(shù)的遍歷//
{
BTptr p=T->lchild; //P 指向的是根結(jié)點(diǎn)
while(p!=Thrt) //循環(huán)鏈表沒(méi)有到頭結(jié)點(diǎn)
{
while(p->Ltag==Link) p=p->Lchild; //找到中序下的第一結(jié)點(diǎn)//
visit(p);
while(p->Rtag==Thread&&p->Rchild!=Thrt)//如果右指針指向的是后繼結(jié)點(diǎn)
{ p=p->Rchild; //那么就大膽的訪問(wèn)吧，取p后繼結(jié)點(diǎn),訪問(wèn)之//
visit(p);
}
p=p->Rchild; // 如果不是后繼結(jié)點(diǎn)，那么還得按照中序遍歷的方法求得后繼//
}
}
在中序線索二叉樹(shù)中，每一非空的線索均指向其祖先結(jié)點(diǎn)。
在二叉樹(shù)上，對(duì)有左右子女的結(jié)點(diǎn)，其中序前驅(qū)是其左子樹(shù)上按中序遍歷的最右邊的結(jié)點(diǎn)(該結(jié)點(diǎn)的后繼指針指向祖先)，中序后繼是其右子樹(shù)上按中序遍歷的最左邊的結(jié)點(diǎn)(該結(jié)點(diǎn)的前驅(qū)指針指向祖先)。
非空二叉樹(shù)中序遍歷第一個(gè)結(jié)點(diǎn)無(wú)前驅(qū)，最后一個(gè)結(jié)點(diǎn)無(wú)后繼，這兩個(gè)結(jié)點(diǎn)的前驅(qū)線索和后繼線索為空指針。
以上是小編為大家整理好的有關(guān)考研的資料，希望對(duì)大家有所幫助！如有疑問(wèn)請(qǐng)關(guān)注應(yīng)屆畢業(yè)生網(wǎng)！