|
二叉树的线索化 线索化和线索化实质 将二叉树变为线索二叉树的过程称为 线索化 按某种次序将二叉树线索化的实质是按该次序遍历二叉树在遍历过程中用线索取代空指针 具体过程可 二叉树的中序线索化 ()分析 算法与中序遍历算法类似只需要将遍历算法中访问结点的操作具体化为建立正在访问的结点与其非空中序前趋结点间线索 该算法应附设一个指针pre始终指向刚刚访问过的结点(pre的初值应为NULL)而指针p指示当前正在访问的结点结点*pre是 结点*p的前趋而*p是*pre的后继 ()将二叉树按中序线索化的算法 typedef enum { LinkThread} PointerTag; //枚举值Link和Thread分别为 typedef struct node{ DataType data; PointerTag ltagrtag; //左右标志 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)?LinkThread; //左指针非空时左标志为Link //(即)否则为Thread(即) p>rtag=(p>rchild)?LinkThread; *(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 ()算法分析 和中序遍历算法一样递归过程中对每结点仅做一次访问因此对于n个结点的二叉树算法的时间复杂度亦为O(n) 二叉树的前序线索化和后序线索化 前序线索化和后序线索化算法与二叉树的中序线索化类似具体可【参见参考书】 |
