12.遍历二叉树与二叉树的建立 - 数据库编程

。因此，我们在每个结点再增设两个标志域ltag和rtag，需要注意的是ltag和rtag只是存放0或1数字的布尔型变量，其占用的内存空间要小于像lchild和rchild的指针变量。结点结构如下：

(2)线索二叉树结构实现

/*二叉树的二叉线索存储结构定义
*    Link==0表示左右孩子指针
*    Thread==1表示指向前驱或后驱的线索
*/
typedef eum {Link,Thread} PointerTag;
typedef struct BiThrNode    /*二叉线索存储结点结构*/
{
    TElemType  data;                            //数据域：结点数据
    struct BiThrNode *lchild,*rchild;    //指针域：左右孩子指针
    PointerTag   LTag;
    PointerTag   RTag;                         //左右标志  
}BiThrNode,*BiThrTree;

3.中序遍历线索化的递归函数(难点) 线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历该二叉树时才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程。中序遍历线索化的递归函数代码如下： BiThrTree pre; //全局变量，始终指向刚刚访问过的结点 /*中序遍历进行中序线索化*/ void InThreading(BitThrTree p) { if(p) { InThreading(p->lchild); //递归左子树线索化 if(!p->lchild) //结点无左孩子 { p->LTag=Thread; //前驱线索：将结点左指针标志置1，说明左指针指向该结点的前驱 p->lchild=pre; //左孩子指针指向前驱 } if(!pre->rchild) //前驱没有右孩子 { pre->RTag=Thread; //后继线索 pre-rchild=p; //前驱右孩子指针指向后继(当前结点p) } pre=p; //保持pre指向p的前驱 InThreading(p->rchild); //递归右子树线索化 } } 源码分析： (1)结点前驱线索化 if(!p->lchild)表示如果某结点的左指针域为空，因为其前驱节点刚刚访问过，赋值给了pre，所以可以将pre赋值给p->lchild，并修改p->LTag=Thread(也就是定义为1)以完成前驱结点的线索化。 (2)结点后驱线索化由于该节点还没有访问到，因此只能对它的前驱结点pre的右指针rchild做判断，if(!pre->rchild)表示如果为空，则p就是pre的后继，于是pre->rchild=p，并且设置pre->RTag=Thread，完成后继结点的线索化。 (3) pre=p语句的作用是完成前驱和后继的判断后，将当前的结点p赋值给pre，以便下一次使用。 4.中序遍历线索二叉树T的非递归算法 二叉树的二叉线索存储表示（以中序为例）：在线索链表上添加一个头结点，并令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点。令二叉树中序串行中的第一个结点的lchild域指针和最后一个结点的rchild域的指针均指向头结点，这样就创建了一个双向线索链表。这样定义的好处是既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。

/*T指向头结点，头结点左键lchild指向根结点，头结点右链rchild指向中序遍历的最后一个结点 * 中序遍历二叉线索链表表示的二叉树T，时间复杂度为O(n)*/ Status InOrderTraverse_Thr(BiThTree T) { BiThrTree p; p=T->lchild; //p指向根结点 while(p != T) //空树或遍历结束时，p==T { while(p->LTag==Link) //当LTag==0时循环到中序序列第一个结点 p=p->lchild; printf("%c",p->data); //显示结点数据，可以更改为其他对结点操作 while(p->RTag == Thread && p->rchild !=T) { p=p->rchild; printf("%c",p->data); } p=p->rchild; //p进至其右子树根 } } 源码分析： (1) p=T->lchild；让p指向根结点开始遍历，如上图编号①所示; (2)while(p!=T)：即循环直到图中的④的出现，此时意味着p指向了头结点，于是与T相等(T是指向头结点的指针)，结束循环，否则一直循环下去去进行遍历操作; (3)while(p->LTag==Link) 循环，就是由A->B->D->H，此时H结点的LTag不是Link(就是不等于0)，所以结束此循环并打印H; (4)while(p->RTag == Thread && p->rchild !=T)，由于结点H的RTag==Thread(就是等于1)，且不是指向头结点。因此打印H的后继D,之后因为D的RTag是Link，因此退出循环; (5)p=p->rchild，即p指向了结点D的右孩子。 .....................不断循环，直到打印出HDIBJEAFCG结束遍历操作。总结：二叉树的线索化有利于节省空间和时间，在实际问题中，如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构是一个非常不错的选择。

12.遍历二叉树与二叉树的建立(二)