5.3.2_2二叉树的线索化
知识总览：
用土办法找到中序前驱：
给定一个节点的指针P，如何在中序序列中找到这个节点的前驱
中序遍历一次整个二叉树，当访问一个节点(节点用指针q表示)的时候，用另外一个指针pre指向当前访问节点q的前驱节点，然后每次判断当前节点是否是要找的给定节点，如果是证明pre指向的前驱节点就是要找的指针p的前驱节点
过程如下：
在访问节点的时候添加前驱节点的判断，添加全局变量final即最终前驱节点结果，pre指向当前访问节点前驱，p为给定目标节点
给定p->F节点即p是F节点指针。开始pre==Null，p==F，final==NULL，根据中序遍历顺序一系列从T=A开始等等，最后先访问D节点，T=D节点，T不为空则执行InOrder遍历D的左子树，T->lchild=NULL则执行visit(D)即q->D，判断当前节点q==目标节点p，如果==则final==pre前驱节点，不相等则pre==当前访问节点q，此时pre==q,然后执行T->rchild=G，G的左子树为空，则访问G，即q=G，q!=p则pre==G，G的右子树为空，则回到上一级根节点B，执行访问B，此时q=B，q!=p则pre=B，再执行B的右子树代码即T->rchild=E，E左子树为空访问E，此时q=E，q!=p则pre=E，再回到上一级根节点A上同q=A,q!=p则pre=A,再回到执行A的右子树C，C不为空再执行C的左子树=F不为空，F的左子树为空则访问F，此时q=F=p，则final=pre=A，再去执行F的右子树为空则回到上一级C访问C，此时q==C!=p则pre=C，然后执行C的右子树，C的右子树为空则执行结束，即最终final=A,pre=C【只要访问的当前节点不是目标节点的，都让pre指向当前节点】
中序线索化：
对二叉树的某一个节点线索化，就是把这个节点的左孩子指针指向它的前驱(比它先访问的前一个节点)或者让它的右孩子指针指向它的后继(比它后访问的后一个节点)
线索二叉树节点定义：比普通二叉树节点多了tag标志位表示该节点左右指针是线索指针
过程：定义一个全局节点pre用来指向当前访问节点的前驱，初始值为NULL。过程和上边土方法同。初始化时当前的二叉树上的tag都设为0即ltag=0、rtag=0表示现在左右孩子指针都是指向左右孩子节点即2个指针并没有被线索化，根据中序遍历顺序，第一个被visit的节点是D，第一个被访问的节点是没有前驱的所以让pre==null，D是没有左孩子的，所以让D的左孩子空链域指针线索化，即让D->lchild指向pre即D的前驱节点，并设置D的ltag=1标志位为线索，且让pre指向当前访问的节点q==D，执行执行。。。根据中序遍历顺序可知下一个visit节点是G,T=G，即q=G，G没有左子树让左子树空链域指针线索化，即G->ltag=1,G->lchild=pre=D，此时前驱节点D不为空但是D的右孩子指针指向孩子节点G故前驱节点D不用补后继节点，让pre=G进行下一轮访问，访问B,此时q=B，补B的前驱节点让q->lchild=pre=B，q->ltag=1，然后在前驱节点pre=G不为空且前驱节点pre右孩子指针是空链域的情况下即pre->rchild==Null(G的右孩子是空的)，让前驱节点右孩子指针pre->rchild指向当前节点q，即在访问当前节点的情况下弥补前驱节点的后继节点，即pre->rchild=q=B，pre->rtag=1，剩下的依次类推推推推。。。。。。。直到访问最后一个节点C，访问完后pre==C，但是下一轮再也没有节点被访问，且此时C节点的右孩子指针是空链域按理应该线索化(C节点的左孩子指针如果为空的话已经在访问的时候进行线索化了，即已经指向了上一个被访问的前驱节点pre)，但是没有节点再被访问右孩子指针线索化不了，所以要在最后判断最后一个节点作为前驱节点的右孩子指针是否是空链域(没有右孩子)，是的话让pre->rchild=null，pre->rtag=1即后继节点线索化【看下边图二】
每一次循环的时候都是先把当前访问的节点的左孩子指针线索化(因为左孩子指向的是前驱节点，前一个访问的节点已经被pre指针记录了，直接当前节点q->lchild=pre，q->ltag=1即可)，再把pre前驱节点的右孩子指针线索化(因为前驱节点被pre记录，当前访问的节点就是pre节点的后继节点，即让pre->rchild=q当前节点，pre->rtag=1)
如下第4张图王道书里边pre的定义是局部变量，但是也是用来记录前驱节点，即把当前访问的节点用pre记录用来补充下一个访问节点的前驱节点和下一个节点访问时补充上一个访问节点的后继节点，pre参数用引用类型是为了改变pre在原来方法中的值，另外王道书中的最后一个访问的节点没有判断右孩子指针是否为空链域而是直接将最后一个节点的右孩子指针线索化了，是正确的，根据左根右的顺序，如果当前访问节点还有一个右孩子那么这个最后一个右孩子又会来一轮循环，即根据中序遍历顺序，最后被访问的节点的右孩子一定为空需要线索化
先序线索化：
上同。定义全局变量pre来记录前驱节点。 根据根左右顺序，先访问根节点再对左、右子树线索化
过程：pre初始值也为null。执行执行执行，访问访问访问。。。。即先访问A节点，让当前节点左子树空链域指向前驱节点pre，A的左子树不为空则不用线索化，前驱节点不为空的话，构造前驱节点的的右孩子线索，第一轮pre为空且当前节点的左子树不为空即左右指针都不需要线索化，让pre=当前访问节点A，第二轮根据先序遍历先visit访问B，即q=B，对B补充前驱节点，看B的左孩子指针不是空不用补充，对前驱节点pre补充后继节点，看Pre指向的A右孩子不是空不用补充，让pre=当前访问节点B，第三轮访问D，q=D，对D补充前驱节点，看D的左孩子指针是空补充，即q->lchild=B，q->ltag=1，对前驱节点pre补充后继节点，看Pre指向的B右孩子不是空不用补充，让pre=D,第4轮再访问D的左子树，上一轮已经让D的左孩子指向了B，则此时D的左孩子指针不为空再一次访问B，B的左孩子指针不为空又指向了D，pre=D，q=B，再执行B的左孩子D。。。。变成了一个无限死循环。。。。。。解决办法看图3，在访问节点的左孩子的时候查看左孩子指针是否是线索指针，如果不是才去访问是的话不再访问否则就又去访问上一个前驱节点了(因为当前节点在访问时会补充前驱节点，即让左孩子指针指向前驱节点，而先序遍历是先访问当前节点，再去访问当前节点的左子树节点，这样如果开始左孩子为空，再补充了前驱节点后左孩子又不为空又去访问前驱节点了，比如第一次访问A，再访问A的左孩子B，B没有左孩子但访问B时B的左孩子指向了前驱A，然后再访问B的左孩子时又开始访问A，变成循环)。。。。。。另外需要注意的是最后一个节点访问时判断右孩子指针是否为空链域，为空线索化
每一轮都是对当前节点补充前驱节点，当前节点左孩子为空补充，让q->lchild=pre,q->ltag=1，不为空不补充，对前驱节点pre补充后继节点，pre前驱节点右孩子为空补充
后序线索化：
上同。不会出现先序线索化循环问题，因为在访问时，所有的左、右孩子节点都已经被处理完了，即访问完这个节点之后不会再回过头去访问当前节点的左孩子节点。也别忘了处理最后一个访问节点的右孩子空链域的后继节点问题，如果右孩子为空则让它线索化
知识回顾：
，