线索树.cpp

杭州电子科技大学ACM题

#include<iostream>
using namespace std;
#include<stdlib.h>
#include<malloc.h>
#define null 0

typedef enum PointerTag{Link,Thread};
typedef struct BitThrNode
{
	char data;
	struct BitThrNode  *lchild,*rchild;
	PointerTag LTag,RTag;
}*BitTree1,BitNode1;

BitTree1 Pre;

void InThreading(BitTree1 p)
{
    if(p)
	{
		InThreading(p->lchild);
		if(!p->lchild) 
		{
		  p->LTag=Thread;
		  p->lchild=Pre;
		}
		if(!Pre->rchild)
		{
			Pre->RTag=Thread;
			Pre->rchild=p;
		}
		if(p->LTag!=Thread)
			p->LTag=Link;
		if(p->RTag!=Thread)
			p->RTag=Link;
		Pre=p;
		
		InThreading(p->rchild);
	}
}

BitTree1 InorderThreading(BitTree1 Thrt,BitTree1 root)
{
	Thrt=(BitTree1)malloc(sizeof(BitNode1));
	Thrt->LTag=Link;
	Thrt->RTag=Thread;
	Thrt->rchild=Thrt;
	if(!root) Thrt->lchild=Thrt;
	else 
	{
		Thrt->lchild=root;
		Pre=Thrt;
		InThreading(root);
		Pre->rchild=Thrt;
		Pre->RTag=Thread;
		Thrt->rchild=Pre;
	}
	return Thrt;
}

void travel(BitTree1 root)
{
	if(root!=null)
	{
		travel(root->lchild);
		cout<<root->data<<"  ";
		travel(root->rchild);
	}
}

BitTree1 createtree(BitTree1 root)
{
	char ch;
	cin>>ch;
	if(ch=='0')
	{
		root=null;
	}
	else 
	{
		root=(BitTree1) malloc(sizeof(BitNode1));
		root->data=ch;
		root->lchild=createtree(root->lchild);
		root->rchild=createtree(root->rchild);
	}
	return root;
}
void InOrderTravel(BitTree1 Thrt)
{
	BitTree1 p=Thrt->lchild;
	while(p!=Thrt)
	{
		while(p->LTag==Link)
			p=p->lchild;
		cout<<p->data<<"  ";
		while(p->RTag==Thread&&p->rchild!=Thrt)
		{
			p=p->rchild;
			cout<<p->data<<"  ";
		}
		p=p->rchild;
	}
}

int main()
{
	BitTree1 Thrt=null,root1=null;
	root1=createtree(root1);
	travel(root1);
	cout<<endl;
	Thrt=InorderThreading(Thrt,root1);
	InOrderTravel(Thrt);
	cout<<endl;
}