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