main.cpp

创建基本有左右结点的二叉树,之后对其线索化,并按中序输出

#include <iostream.h>
#include <stdlib.h>
typedef enum PointerTag {Link,Thread};//Link=0:指针；Thread=1:线索
//二叉线索结构
typedef struct BiThrNode
{
	char data;
	struct BiThrNode * lchild,* rchild;//左右孩子指针
	PointerTag LTag,RTag;//左右标志
}BiThrNode,* BiThrTree;
//声名
BiThrTree  pre;
bool PreCreateBiTree(BiThrTree & T);
bool InOrderThreading(BiThrTree & Thrt,BiThrTree T);
void InThread(BiThrTree p);
//bool InOrderTraverse_Thr(BiThrTree T,bool(* Visit)(char e));
bool InOrderTraverse_Thr(BiThrTree T);
//主程序
void main()
{
	BiThrNode *  tree;
	BiThrNode *  head;
	PreCreateBiTree(tree);//创建
	InOrderThreading(head,tree);//线索化
	 InOrderTraverse_Thr(head);
	 cout<<endl;
	//InOrderTraverse_Thr(tree, (*OutPut)(tree->data));
}
//先序创建二叉树
bool PreCreateBiTree(BiThrTree & T)
{
	char ch;
	cout<<"Please input the data:";
	cin>>ch;
	if(ch=='0')
	{
		T=NULL;
	//T->LTag=Thread;//指示前驱
	//	T->RTag=Thread;//指示后继
	}
	else
	{
		if(!(T=(BiThrNode *)malloc(sizeof(BiThrNode))))
			exit(0);
		T->data=ch;
		T->LTag=Link;
		T->RTag=Link;
		PreCreateBiTree(T->lchild);//指示左孩子
		PreCreateBiTree(T->rchild);//指示右孩子
	}//else
	return true;
}//PreCreateBiTree
//中序线索化
bool InOrderThreading(BiThrTree & Thrt,BiThrTree T)
//Thrt指向头结点
{	
//BiThrTree pre;//前指指针
	if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))
		exit(0);
	Thrt->LTag=Link;//左标志为指针，右标志为线索
	Thrt->RTag=Thread;
	Thrt->rchild=Thrt;//右指针回指
	if(!T) Thrt->lchild=Thrt;//T为空时其前驱为头结点自身
	else
	{
		Thrt->lchild=T;
		pre=Thrt;
		InThread(T);
		pre->rchild=Thrt;
		pre->RTag=Thread;
		Thrt->rchild=pre;
	}//else
	return true;
}//InOrderThreading
//线索化
void InThread(BiThrTree p)
{
	if(p)
	{
		InThread(p->lchild);
		if(!p->lchild)//当前结点左子树空，指示前驱
		{
			p->LTag=Thread;
			p->lchild=pre;
		}
		if(!pre->rchild)//上一结点右子树空
		{
			pre->RTag=Thread;
			pre->rchild=p;
		}
		pre=p;//保持pre指向p的前驱
		InThread(p->rchild);//右子树线索化
	}//if
}//InThread

//中序遍历二叉树
//bool InOrderTraverse_Thr(BiThrTree T,bool(* Visit)(char e))
bool InOrderTraverse_Thr(BiThrTree T)
//T指向头结点，头结点的左链lchild指向根结点
{	
	BiThrTree p=T->lchild;
	while(p!=T)//不为空
	{
		while(p->LTag==Link) p=p->lchild;
	//if(Visit(p->data)) return false;
			cout<<p->data<<"  "; 
		while(p->RTag==Thread&&p->rchild!=T)
		{
			p=p->rchild;
			//Visit(p->data);
			cout<<p->data<<"  "; 
		}//while
		p=p->rchild;
	}//while
	return true;
}//InOrderTraverse_Thr