如何将线索二叉树的后序线索化改写成长尾？

本文共计1322个文字，预计阅读时间需要6分钟。

将二叉树转化为线性结构的常用方法是通过后序线索化。这种方法通过给每个节点添加线索（指向其前驱和后继节点的指针）来实现。后序线索化二叉树的思路如下：

1.遍历到当前节点，将其左子树的后序遍历结果处理完毕。

2.将当前节点的前驱线索指向其左子树的最后一个节点（即最右节点）。

3.将当前节点的后继线索指向其右子树的根节点。

4.处理当前节点的右子树。

思路

后序线索化二叉树是一种将二叉树转化为一个线性结构的方法，通过给每个结点添加线索（指向前驱结点和后继结点的指针）来实现。后序线索化二叉树的思路如下：

1. 遍历到一个结点时，如果它有左孩子，就递归进入左子树。

2. 如果它有右孩子，就递归进入右子树。

3. 如果它没有左孩子，则将左指针线索化为前驱结点。

4. 如果它没有右孩子，则将右指针线索化为后继结点。

5. 最后一个遍历到的结点，将它的右指针线索化为后继结点（默认为空）。

具体实现时，可以用一个全局变量来保存前驱结点，每遍历一个结点时，将它的左指针指向前驱结点，并将前驱结点的右指针指向它。处理完左子树后，将前驱结点更新为当前结点，再递归进入右子树。处理完右子树后，将当前结点的右指针指向后继结点，再将后继结点更新为当前结点。最后遍历到的结点的右指针指向后继结点（默认为空）。

找第一个结点

从根结点开始，向左走到尽头，若无右子树，则该结点为所求，否则，后序序列第一个结点为右子树后序序列的第一个结点。

BiThrTree First(BiThrTree p) { if(!p) return NULL; while(p->LTag==Link) p=p->lchild; if(p->RTag==Thread) return p; else { p=p->rchild; return First(p); } }

怎么找后继

若P指向根，则无后继；

若*p为其双亲的右孩子，则后继为双亲；

若*p是其双亲的左孩子且双亲没有右子树，则其后继是其双亲；

若*p是其双亲的左孩子且双亲有右子树，则其后继是双亲右子树后序序列的第一个结点。

BiThrTree succ(BiThrTree T,BiThrTree p) { BiThrTree f; if(p==T) return NULL; if(p->RTag==Thread) return p->rchild; f=parent(T,p); if(f->rchild==p) return f; if(f->lchild==p&&f->RTag==Thread) return f; if(f->lchild==p&&f->RTag==Link) return First(f->rchild); }

怎么找前导

若p->LTag为Thread,则前导为p->lchild;

若p->LTag,表明p有左子树。因为后序遍历为左右根，若p没有右子树，则前导为左子树后序序列的最后一个结点，即左子树的根，即*p的左孩子。

若*p有右子树，则前导为右孩子。

代码实现

#include <stdio.h> #include <stdlib.h> typedef char TElemType; typedef enum PointerTag {Link,Thread} PointerTag; typedef struct BiThrNode{ TElemType data; struct BiThrNode *lchild,*rchild; PointerTag LTag,RTag; }BiThrNode,*BiThrTree; BiThrTree pre; void InThreading(BiThrTree); Status CreateBiTree(BiThrTree *T){ char ch; ch=getchar(); if(ch=='#') *T=NULL; else{ *T=(BiThrNode*) malloc (sizeof(BiThrNode)); if(!*T) exit(OVERFLOW); (*T)->data=ch; (*T)->LTag=Link; (*T)->RTag=Link; CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild); } return OK; } Status PostOrderTraverse(BiThrTree T,Status (*visit)(TElemType e)){ if(T){ PostOrderTraverse(T->lchild,visit); PostOrderTraverse(T->rchild,visit); (*visit)(T->data); } else return OK; } Status PrintElement(TElemType e){ putchar(e); return OK; } Status PostThreading(BiThrTree *Thrt,BiThrTree T){ if(!((*Thrt)=(BiThrTree) malloc(sizeof(BiThrNode)))) exit(OVERFLOW); (*Thrt)->LTag=Link; (*Thrt)->RTag=Thread; (*Thrt)->rchild=*Thrt; if(!T) (*Thrt)->lchild=*Thrt; else{ (*Thrt)->lchild=T; pre= (*Thrt); InThreading(T); (*Thrt)->rchild = pre; if(!pre->rchild) { pre->RTag=Thread; pre->rchild=(*Thrt);} } } void InThreading(BiThrTree p){ if(p){ InThreading(p->lchild); InThreading(p->rchild); if(!p->lchild) {p->LTag = Thread; p->lchild=pre;} if(!pre->rchild) {pre->RTag=Thread; pre->rchild=p;} pre=p; } } BiThrTree First(BiThrTree p){ if(p){ while(p->LTag==Link) p=p->lchild; if(p->RTag==Thread) return p; else{ p=p->rchild; First(p); } } } BiThrTree parent(BiThrTree T,BiThrTree p){ BiThrTree Q[100],t; int f=0,r=0; r++; Q[r]=T; while(f!=r){ f++; t=Q[f]; if(t->lchild==p || t->rchild==p) return t; if(t->LTag==Link) {r++;Q[r]=t->lchild;} if(t->RTag==Link) {r++;Q[r]=t->rchild;} } } BiThrTree succ(BiThrTree T,BiThrTree p){ BiThrTree f; if(p==T) return 0; if(p->RTag==Thread) return p->rchild; f=parent(T,p); if(f->rchild==p) return f; if(f->lchild==p && f->RTag==Thread) return f; if(f->lchild==p && f->RTag==Link){ return First(f->rchild); } } main() { BiThrTree T,Th,p,f; char ch; CreateBiTree(&T); PostOrderTraverse(T,PrintElement); PostThreading(&Th,T); putchar('\n'); p=First(T); printf("The First Node is:%c\n",p->data); f=parent(T,p); printf("parent is:%c",f->data); printf("\nsucc is:%c\n",succ(T,p)->data); for(p=First(T);p!=Th&&p;p=succ(T,p)) printf("%c",p->data); putchar('\n'); }