思路:
1、线索化二叉树结点定义与二叉树基本相同,只是在原先的基础上添加了int类型的左右线索标志。
2、定义全局变量pre,用来指向当前结点的前驱结点。
3、构造visit()时,如果访问结点的左孩子为空,需要建立前驱线索并将ltag设为1;如果访问结点的前驱结点不为空且其右孩子为空,需要建立后继线索并将rtag设为1。
4、对二叉树进行中序线索化时,先对其左子树进行中序线索化,再访问根结点,最后对右子树进行中序线索化。
代码:
#include<stdio.h> //线索二叉树结点、 typedef struct ThreadNode{ int data; struct ThreadNode *lchild,*rchild; int ltag,rtag; }ThreadNode,*ThreadTree; ThreadNode *pre=NULL; //全局变量,指向当前结点的前驱结点 void visit(ThreadNode *q){ if(q->lchild==NULL){ q->lchild=pre; //线索化,建立前驱线索 q->ltag=1; } if(pre!=NULL&&pre->rchild==NULL){ pre->rchild=q; //线索化,建立后继线索 pre->rtag=1; } pre=q; } // 中序线索化 void InThread(ThreadTree T){ if(T!=NULL){ InThread(T->lchild); visit(T); InThread(T->rchild); } } int main(){ }
标签:pre,结点,中序,二叉树,NULL,线索 From: https://www.cnblogs.com/zyj3955/p/17705955.html