以中序线索链表为存储结构的中序遍历 void In Traverse Thr( BiThrTree T, void (Visit)(Elem Type e)) {∥T指向中序线索链表中的头结点,头结点的左指针 Lchild指向二叉树的根结点,头结 点的右线索 Child指向中序遍历访问的最后一个结点。本算法对此二叉树进行中序遍历,对 树中每个元素调用函数vsit进行访问操作 p=T->Lchild; ∥p指向二叉树的根结点 while(p]=T) ∥空树或遍历结束时,p= Thead while(p->LTag==Link)p=p->lchild; Visit(p->data); ∥访问其左子树为空的结点 while(p->RTag==Thread & p->Rchild!=T p=p> rchild; visit(p->data);∥访问“右线索”所指后继结点 p= p->Rchild; ∥Pp进至其右子树根 ·p=T-> Lchild; ∥p指向二叉树的根结点 while(!=T) ∥空树或遗历结束时,p= Thead while(p->LTag==Link)p=p->Lchild ∥访问其左子树为空的结点 while(p->RTag==Thread & p->Rchild =T) p=p> rchild;vsi(p→>data);∥访问“右线索所指后继结点 p= p->Rchild ∥p进至其右子树根 线索链表的生成 .void In Threading(biThrTree p, BiThrTree& pre) ∥对p指向根结点的二叉树进行中序遍历,遍历过程中进行“中序线索化”。若p所指结 点的左指针为空,则将它改为“左线索”,若pe所指结点的右指针为空,则将它改为“右线索 指针pre在遍历过程中紧随其后,即始终指向p所指结点在中序序列中的前驱 if (p)i Threading(> Lchild4me)∥对左子树进行线索化 if (p->Lchild) {p>LIag= Thread;p-> Lchild=pre;}∥建前驱线索 if (pre->Rchild) pre>RIag= Thread;pre-> Rchild=p;}∥建后继线索 pre- p; 保持pre指向p的前驱 n Threading(mp-> Rchild, pre)∥对右子树进行线索化 .void InOrderThreading( bithrTree &Th, BiThrTree Br ∥BT为指向二叉树根结点的指针,由此二叉链表建立二叉树的中序线索链表, Thead指 向线索链表中的头结点以中序线索链表为存储结构的中序遍历 •void InOrderTraverse_Thr(BiThrTree T ,void (*Visit)(ElemType e)) {// T 指向中序线索链表中的头结点，头结点的左指针 Lchild 指向二叉树的根结点，头结 点的右线索 Rchild 指向中序遍历访问的最后一个结点。本算法对此二叉树进行中序遍历，对 树中每个元素调用函数 Visit 进行访问操作 p = T->Lchild; // p 指向二叉树的根结点 while (p!= T) { // 空树或遍历结束时，p==Thead while (p->LTag==Link) p = p->Lchild; Visit(p->data); // 访问其左子树为空的结点 while (p->RTag==Thread && p->Rchild!=T) { p = p->rchild; Visit(p->data); // 访问“右线索”所指后继结点 } p = p->Rchild; // p 进至其右子树根 } } •p = T->Lchild; // p 指向二叉树的根结点 while (p!= T) •{ // 空树或遍历结束时，p==Thead while (p->LTag==Link) p = p->Lchild; Visit(p->data); // 访问其左子树为空的结点 while (p->RTag==Thread && p->Rchild!=T) • { p = p->rchild; Visit(p->data); // 访问“右线索”所指后继结点 } p = p->Rchild; // p 进至其右子树根 } 6-5-1.swf 线索链表的生成 •void InThreading(BiThrTree p，BiThrTree& pre) { // 对 p 指向根结点的二叉树进行中序遍历，遍历过程中进行“中序线索化”。若 p 所指结 点的左指针为空，则将它改为“左线索”，若 pre 所指结点的右指针为空，则将它改为“右线索”。 指针 pre 在遍历过程中紧随其后，即始终指向 p 所指结点在中序序列中的前驱。 if (p) { InThreading(p->Lchild, pre); // 对左子树进行线索化 if (!p->Lchild) { p->LTag = Thread; p->Lchild = pre; } // 建前驱线索 if (!pre->Rchild) { pre->RTag = Thread; pre->Rchild = p; } // 建后继线索 pre = p; // 保持 pre 指向 p 的前驱 InThreading(p->Rchild, pre); // 对右子树进行线索化 } } •void InOrderThreading(BiThrTree &Th, BiThrTree BT) { // BT 为指向二叉树根结点的指针，由此二叉链表建立二叉树的中序线索链表，Thead 指 向线索链表中的头结点