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

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

　　算法描述：

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

　　{

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

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

　　{

　　while(p->Ltag==Link) p=p->Lchild; //找到中序下的第一結(jié)點//

　　visit(p);

　　while(p->Rtag==Thread&&p->Rchild!=Thrt)//如果右指針指向的是后繼結(jié)點

　　{ p=p->Rchild; //那么就大膽的訪問吧，取p后繼結(jié)點,訪問之//

　　visit(p);

　　}

　　p=p->Rchild; // 如果不是后繼結(jié)點，那么還得按照中序遍歷的方法求得后繼//

　　}

　　}

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

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

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

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