南京中索祥电子科技有限公司

(1)分析

算法根据二叉树遍历的方式而定。只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索。

该算法应附设一个指针pre始终指向刚刚访问过的结点(pre的初值应为NULL)，而指针p指示当前正在访问的结点。结点*pre是结点*p的前趋，而*p是*pre的后继。

(2)将二叉树按中序线索化的算法

typedef enum { Link，Thread} PointerTag; //枚举值Link和Thread分别为0，1

typedef struct node{

DataType data;

PointerTag ltag，rtag; //左右标志

Struct node *lchild，*rchild;

} BinThrNode;\\线索二叉树的结点类型

typedef BinThrNode *BinThrTree;

BinThrNode *pre=NULL; //全局量

void lnorderThreading(BinThrTree p)

{//将二叉树p中序线索化

if(p){ //p非空时，当前访问结点是*p

InorderThreading(p->lchild); //左子树线索化

//以下直至右子树线索化之前相当于遍历算法中访问结点的操作

p->ltag=(p->lchild)?Link:Thread; //左指针非空时左标志为Link

//(即0)，否则为Thread(即1)

p->rtag=(p->rchild)?Link:Thread;

*(pre){ //若*p的前趋*pre存在

if(pre->rtag==Thread) //若*p的前趋右标志为线索

pre->rchild=p; //令*pre的右线索指向中序后继

if(p->ltag==Thread) //*p的左标志为线索

p->lchild=pre; //令*p的左线索指向中序前趋

} // 完成处理*pre的线索

pre=p; //令pre是下一访问结点的中序前趋

InorderThreeding(p->rehild); //右子树线索化

}//endif

} //InorderThreading

(3)算法分析

递归过程中对每结点仅做一次访问，因此对于n个结点的二叉树，算法的时间复杂度亦为O(n)。