数据结构 二叉树的线索存储

      #include <stdio.h>
      #include <stdlib.h>
      #include <iostream.h>
      #define OK 1
      #define ERROR 0
      #define OVERFLOW -2
      typedef char TElemType;
      typedef enum {Link,Thread} PointerTag;
      typedef struct BiThrNode
      {
      	TElemType data;
     	struct BiThrNode *lchild,*rchild;
      	PointerTag LTag;
      	PointerTag RTag;
      }BiThrNode, *BiThrTree;
      BiThrTree pre;
      void Create_BiThrTree(BiThrTree &T)
      {
      	TElemType ch;
     	cin >> ch;
     	if (ch == '#')
      	{
      		T = NULL;
      	}
     	else
      	{
      		T = (BiThrTree)malloc(sizeof(BiThrNode));
     		if (!T)
      		{
     			exit(OVERFLOW);
      		}
      		T->data = ch;
      		Create_BiThrTree(T->lchild);
     		if (T->lchild)
      		{
      			T->LTag = Link;
      		}
      		Create_BiThrTree(T->rchild);
     		if (T->rchild)
      		{
      			T->RTag = Link;
      		}
      	}
      }
      void InThreading(BiThrTree p)
      {
     	if (p)
      	{
      		InThreading(p->lchild);
     		if (!p->lchild)
      		{
      			p->LTag = Thread;
      			p->lchild = pre;
      		}
     		if (!pre->rchild)
      		{
      			pre->RTag = Thread;
      			pre->rchild = p;
      		}
      		pre = p;
      		InThreading(p->rchild);
      	}
      }
      int InOrderThreading(BiThrTree &Thrt, BiThrTree T)
      {
     	if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode))))
      	{
     		exit(OVERFLOW);
      	}
      	Thrt->LTag = Link;
      	Thrt->RTag = Thread;
      	Thrt->rchild = Thrt;
     	if (!T)
      	{
      		Thrt->lchild = Thrt;
      	}
     	else
      	{
      		Thrt->lchild = T;
      		pre = Thrt;
      		InThreading(T);
      		pre->rchild = Thrt;
      		pre->RTag = Thread;
      		Thrt->rchild = pre;
      	}
     	return OK;
      }
      int InOrderTraverse_Thr(BiThrTree T)
      {
      	BiThrTree p;
      	p = T->lchild;
     	while (p != T)
      	{
     		while (p->LTag == Link)
      		{
      			p = p->lchild;
      		}
     		printf("%c",p->data);
     		while (p->RTag == Thread && p->rchild != T)
      		{
      			p = p->rchild;
     			printf("%c",p->data);
      		}
      		p = p->rchild ;
      	}
     	return OK;
      }
      int main()
      {
      	BiThrTree T,H;
      	Create_BiThrTree(T);
      	InOrderThreading(H,T);
      	InOrderTraverse_Thr(T);
     	printf("\n");
     	return 0;
      }
  
 

文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq523176585/article/details/17249281