有了線索的二叉鏈表那么遍歷就方便多了，不需要借助棧也不需要用遞歸了，因為他已經(jīng)把前驅后繼都連起來了，而不像二叉樹那樣，走不動的時候就只能退棧了。 而且遍歷速度快。

　　算法思路：先找到中序下的第一結點，訪問之;若被訪問的結點的右指針為線索指針，直接取其后繼結點訪問;……，直到被訪問結點的右子樹存在，再從相應右子起找中序下的第一結點，……，依次類推，直到整個樹遍歷完畢。

　　算法描述：

　　BTptr Tinorder(BTptr Thrt) //對中序線索二叉樹的遍歷//

　　{

　　BTptr p=T->lchild; //P 指向的是根結點

　　while(p!=Thrt) //循環(huán)鏈表沒有到頭結點

　　{

　　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; // 如果不是后繼結點，那么還得按照中序遍歷的方法求得后繼//

　　}

　　}

　　在中序線索二叉樹中，每一非空的線索均指向其祖先結點。

　　在二叉樹上，對有左右子女的結點，其中序前驅是其左子樹上按中序遍歷的最右邊的結點(該結點的后繼指針指向祖先)，中序后繼是其右子樹上按中序遍歷的最左邊的結點(該結點的前驅指針指向祖先)。

　　非空二叉樹中序遍歷第一個結點無前驅，最后一個結點無后繼，這兩個結點的前驅線索和后繼線索為空指針。

以上是小編為大家整理好的有關考研的資料，希望對大家有所幫助！如有疑問請關注應屆畢業(yè)生網(wǎng)！