threadbitree.h

来自「《数据结构-使用C语言》第三版」· C头文件 代码 · 共 117 行

//中序线索二叉树的设计
typedef struct Node  //节点 
{
	DataType data;
	int leftThread;
	struct Node *leftChild;
	struct Node *rightChild;
	int rightThread;
}ThreadBiNode;

typedef struct  //二叉树 
{
	ThreadBiNode *root;
	ThreadBiNode *current;
	int nextComplete;
}ThreadBiTree;

void InThread(ThreadBiNode *current, ThreadBiNode **pre)
{
	if(current!=NULL)
	{
		InThread(current->leftChild,pre);
		if(current->leftChild==NULL)
		{
			current->leftThread=1;
			current->leftChild=*pre;
		}
		else current->leftThread=0;
		
		if(current->rightChild!=NULL)
		current->rightThread=0;
		else current->rightThread=1;
		
		if((*pre)->rightChild==NULL)
		{
			(*pre)->rightThread=1;
			(*pre)->rightChild=current;
		}
		else current->rightThread=0;
		
		*pre=current;
		InThread(current->rightChild,pre);
	}
}

void CreatInThread(ThreadBiNode **root)
{
	ThreadBiNode *t=*root;
	ThreadBiNode *current, *pre=*root;
	
	*root=(ThreadBiNode *)malloc(sizeof(ThreadBiNode));
	if(t==NULL)
	{
		(*root)->leftThread=0;
		(*root)->rightThread=1;
		(*root)->leftChild=*root;
		(*root)->rightChild=*root;
	}
	else
	{
		current=t;
		(*root)->leftChild=t;
		(*root)->leftThread=0;
		
		InThread(current, &pre);
		
		pre->rightChild=*root;
		pre->rightThread=1;
		(*root)->rightChild=pre;
		(*root)->rightThread=1;
	}
}

void ThreadInitiate(ThreadBiTree *tree, ThreadBiNode *root)
{
	tree->root=root;
	tree->current=root;
	if(root==NULL)
	tree->nextComplete=1;
	else 
	tree->nextComplete=0;
}

void First(ThreadBiTree *tree)
{
	tree->current=tree->root;
	while(tree->current->leftThread==0)
	tree->current=tree->current->leftChild;
	
	if(tree->current==tree->root)tree->nextComplete=1;
	else tree->nextComplete=0;
}

void Next(ThreadBiTree *tree)
{
	ThreadBiNode *p=tree->current->rightChild;
	
	if(tree->nextComplete==1)return ;
	
	if(tree->current->rightThread==0)
	while(p->leftThread==0)p=p->leftChild;
	tree->current=p;
	
	if(tree->current==tree->root)tree->nextComplete=1;
}

int EndOfNext(ThreadBiTree *tree)
{
	return tree->nextComplete;
}