二叉树线索化 C语言实现

#ifndef_BINARYTREE_H_#includestdio.h#includestdlib.htypedefstructBitNode{chardata;BitNode*lchild,*rchild;intltag,rtag;intdwCount;}BitNode,*BitTree,ElemType;//树的结构体定义typedefstructnode{ElemTypestack;structnode*next;}linkstack;//栈的结构体定义intgettop(linkstack*s,ElemType*e);//取栈顶元素intemptystack(linkstack*s);//判断栈是否为空，为空返回1，不为空返回0intpop(linkstack*s,ElemType*e);//出栈，把出栈的数据放到e中intpush(linkstack*s,ElemType*x);//压栈，把e中元素压到栈顶intinitstack(linkstack**s);//初始化一个栈BitTreeCreateBiTree();//创建一个树，返回概树的根结点voidPreOrderBiTree(BitTreeT);//二叉树先序非递归遍历voidInOrderBiTree(BitTreeT);//二叉树中序非递归遍历BitTreeCreateBiTree();//创建一个树，返回概树的根结点BitTreePreOrderThreading(BitTreeT);//二叉树先序线索化voidPreThreading(BitTreep);//二叉树先序线索化过程voidPreThreadrear(BitTreeThrt);//二叉树先序线索化后继遍历voidPreThreadfront(BitTreeThrt);BitTreeInOrderThreading(BitTreeT);//二叉树中序线索化voidInThreading(BitTreep);//二叉树中序线索化过程voidInOrderThreadrear(BitTreeThrt);//二叉树中序线索化后继遍历voidInOrderThreadfront(BitTreeThrt);//二叉树中序线索化前驱遍历voidPostOrderBiTree(BitTreeT);//二叉树后序非递归遍历voidPostOrderBiTree2(BitTreeT);//二叉树后序非递归遍历#endif//////////////////////////此上代码为头文件。///////////////////////#includeBinaryTree.hBitTreepre;BitTreeCreateBiTree(){BitTreebt;charx;x=getchar();if(x=='#')bt=NULL;else{bt=(BitTree)malloc(sizeof(BitNode));bt-data=x;bt-dwCount=0;bt-lchild=NULL;bt-rchild=NULL;bt-ltag=0;bt-rtag=0;bt-lchild=CreateBiTree();bt-rchild=CreateBiTree();}returnbt;}////////////////////////////////////////////////////////////////////////////Comment:非递归先序遍历二叉树//Algorithm:沿着左指针访问沿途经过的根节点，同时将右指针进栈，以便在递归访//问左子树完成后能得到右子树的根节点的地址，如此重复进行，直到栈空。//////////////////////////////////////////////////////////////////////////voidPreOrderBiTree(BitTreeT){linkstack*S;BitTreep,q;q=(BitTree)malloc(sizeof(BitNode));initstack(&S);p=T;while(p||!emptystack(S)){while(p){printf(%c,p-data);push(S,p);p=p-lchild;}if(pop(S,q))p=q-rchild;}}////////////////////////////////////////////////////////////////////////////Comment:非递归中序遍历二叉树//Algorithm:先沿着左指针走到二叉树中最左下的结点，即左指针为空的结点，将沿//途经过的根节点，指针进栈。当左指针为空时，从栈中取出根节点访问，然后再跳//到右子树上。//////////////////////////////////////////////////////////////////////////voidInOrderBiTree(BitTreeT){linkstack*S;BitTreep,q;q=(BitTree)malloc(sizeof(BitNode));initstack(&S);p=T;while(p||!emptystack(S)){while(p){push(S,p);p=p-lchild;}pop(S,q);printf(%c,q-data);p=q-rchild;}}////////////////////////////////////////////////////////////////////////////Comment:非递归后续遍历二叉树//Algorithm:先沿着左指针走到二叉树中最左下的结点，将沿途经过的根节点指针进//栈，若右子树为空，则弹栈并访问根节点，否则，跳到右子树上。//////////////////////////////////////////////////////////////////////////voidPostOrderBiTree(BitTreeT){linkstack*S;BitTreep,q;charflag;//标记访问过的节点initstack(&S);//p=(BitTree)malloc(sizeof(BitTree));q=(BitTree)malloc(sizeof(BitNode));p=T;while(p||!emptystack(S)){if(p!=q){while(p){push(S,p);if(p-lchild)p=p-lchild;elsep=p-rchild;}}if(emptystack(S))break;gettop(S,q);if(q-rchild==p){p=(BitTree)malloc(sizeof(BitNode));pop(S,p);printf(%c,p-data);p=q;flag=p-data;//mark}else{p=q-rchild;if(flag==p-data)//如果根节点的右子树刚刚访问完成，那么打印根节点。{p=(BitTree)malloc(sizeof(BitNode));pop(S,p);printf(%c,p-data);p=q;flag=p-data;}}}}voidPostOrderBiTree2(BitTreeT){linkstack*S;BitTreep,q;initstack(&S);q=(BitTree)malloc(sizeof(BitNode));p=T;while(p||!emptystack(S)){while(p){p-dwCount++;push(S,p);p=p-lchild;}pop(S,q);if(q-dwCount==2)printf(%c,q-data);else{q-dwCount++;p=q-rchild;push(S,q);}}}////////////////////////////////////////////////////////////////////////////Comment:先序线索化二叉树//Algorithm:先判断根节点是否为空，为空则令Thrt结点左指针回指，Thrt右指针//初始化时默认为指向其自身，之后判断根节点的左子树是否为空，不为空则//置ltag为0，为空则指向pre前驱结点，后判断右子树是否为空，如此反复//////////////////////////////////////////////////////////////////////////BitTreePreOrderThreading(BitTreeT){BitTreeThrt;Thrt=(BitTree)malloc(sizeof(BitNode));Thrt-ltag=0;Thrt-rtag=1;Thrt-rchild=Thrt;if(!T)Thrt-lchild=Thrt;else{Thrt-lchild=T;pre=Thrt;PreThreading(T);pre-rchild=Thrt;pre-rtag=1;Thrt-rchild=pre;}returnThrt;}voidPreThreading(BitTreep){if(p){if(!p-lchild){p-ltag=1;p-lchild=pre;}elsep-ltag=0;if(!pre-rchild){pre-rtag=1;pre-rchild=p;}elsepre-rtag=0;pre=p;if(p-ltag==0)PreThreading(p-lchild);PreThreading(p-rchild);}}////////////////////////////////////////////////////////////////////////////Comment:先序二叉树线索后继遍历//Algorithm:Thrt头结点开始其ltag==0则访问该左子树，如此反复直到最左下子树//后指针移向右子树如此反复直至遍历完整颗二叉树//////////////////////////////////////////////////////////////////////////voidPreThreadrear(BitTreeThrt){BitTreep=Thrt-lchild;while(p!=Thrt){while(p-ltag==0&&p-rchild!=Thrt){printf(%c,p-data);p=p-lchild;}printf(%c,p-data);p=p-rchild;}}////////////////////////////////////////////////////////////////////////////Comment:先序二叉树线索前驱遍历//Algorithm:Thrt头结点开始其ltag==0则访问该左子树，如此反复直到最左下子树//后指针移向右子树如此反复直至遍历完整颗二叉树//////////////////////////////////////////////////////////////////////////voidPreThreadfront(BitTreeThrt){BitTreep=Thrt-rchild;while(p!=Thrt-lchild){while(p-ltag==1&&p-lchild!=Thrt){printf(%c,p-data);p=p-lchild;}printf(%c,p-data);p=p-lchild;}}////////////////////////////////////////////////////////////////////