线索二叉树

找到某个结点的前驱或后继朴素思路从根节点出发重新进行一次中序遍历指针q记录当前访问的结点指针pre记录上一个被访问的结点①当qp时pre为前驱②当prep时q为后继构造先序中序后序线索二叉树lchild指向前驱rchild指向后继前驱线索后继线索二叉树结点typedefstructBiTNode{ElemType data;structBiNode*lchild,*rchild;}BiTNode,*BiTree;线索二叉树又称线索链表结点typedefstructThreadNode{ElemType data;strut ThreadNode*lchild,*rchild;//tag0,表示指针指向孩子tag1,表示指针只想“线索”intltag,rtag;//左右线索标志}ThreadNode,*ThreadTree;举例 土办法找中序前驱这是之前中序遍历的代码voidInOrder(BiTree T){if(T!NULL){InOrder(T-lchild);visit(T)InOrder(T-rchild);}}我们给visit做一些手脚找中序前驱结点voidvisit(BiTNode*q){if(qp)//当前访问的正好是目标结点finalpre;//找到p的前驱elsepreq;//pre指向当前访问结点}//辅助全局变量BiTNode*p;//p指向目标结点BiTNode*preNULL;//当前访问结点的前驱结点BiTNode*finalNULL;//用于记录最终结果中序线索化#定义中序线索二叉树//线索二叉树结点typedefstructThreadNode{ElemType data;structThreadNode*lchild,*rchild;intltag,rtag;//左、右线索标志}ThreadNode,*ThreadTree;#遍历中序线索二叉树//中序遍历二叉树一边遍历一边线索化voidInThread(ThreadTree T){if(T!NULL){InThread(T-lchild);//中序遍历左子树visit(T);//访问根节点InThread(T-rchild);//中序遍历右子树}}#更牛逼的visit,一边遍历一边线索化voidvisit(ThreadNode*q){if(q-lchildNULL){//左子树为空建立前驱线索q-lchildpre;q-ltag1;}if(pre!NULLpre-rchildNULL){pre-rchildq;//建立前驱结点的后继线索pre-rtag1;}preq;}//全局变量 pre 指向当前访问结点的前驱ThreadNode*preNULL;#中序线索化总代码//中序线索化二叉树TvoidCreateInThread(ThreadTree T){preNULL;//pre初始为NULLif(T!NULL){//非空二叉树才能线索化InThread(T);//中序线索化二叉树if(pre-rchildNULL)pre-rtag1;//处理遍历的最后一个结点}}#避免 先序线索化 无限循环//先序遍历二叉树一边遍历一边线索化voidPreThread(ThreadTree T){if(T!NULL){visit(T);//先处理根节点if(T-ltag0)//lchild不是前驱线索PreThread(T-lchild);PreThread(T-rchild);}}#后序线索化//后序线索化voidPostThread(ThreadTree p,ThreadTreepre){if(p!NULL){PostThread(p-lchild,pre);//递归线索化左子树PostThread(p-rchild,pre);//递归线索化右子树if(p-lchildNULL){//左子树为空建立前驱线索p-lchildpre;p-ltag1;}if(pre!NULLpre-rchildNULL){pre-rchildp;//建立前驱结点的后继线索pre-rtag1;}prep;//标记当前结点成为刚刚访问过的结点}//if(p!NULL)}