bithrtree.cpp

二叉树的中序线索化

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>

#include "..\header\status.h"
#include "..\header\BiThrTree.h"

BiThrTree pre;		//全局变量 

//构造二叉链表,注意:输入序列是先序序列
Status CreatBinTree(BiThrTree &T) 
{
	char ch;
	scanf("%c",&ch);
	if (ch=='#')
		T = NULL;
	else			//读入非空格
	{
		T=(BiThrTree)malloc(sizeof(BiThrNode));	//生成结点
		T->data=ch;
		T->LTag=Link;
		T->RTag=Link;
		CreatBinTree(T->lchild);					//构造左子树
		CreatBinTree(T->rchild);					//构造右子树
	}

	return OK;
}

Status DestroyBinTree(BiThrTree& T)
{
	if(T == NULL)
		return OK;

	if(!T->LTag)
		DestroyBinTree(T->lchild);

	if(!T->RTag)
		DestroyBinTree(T->rchild);

	free(T);
	T = NULL;

	return OK;
}

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;						//保持pre指向p
		InThreading(p->rchild);			//右子树线索化
	}
}

//中序遍厉二叉树T，并将其中序线索化，Thrt指向头结点
Status 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;
}

Status Visit(BiThrTree e)
{
	printf("%d %c %d\n",e->LTag,e->data,e->RTag);
	return OK;
}

Status InOrderTraverse_Thr(BiThrTree T,Status (*Visit)(BiThrTree e))
//T指向头结点，头结点的左链lchild指向根结点，中序遍厉二叉树
{
	BiThrTree p;
	p=T->lchild;		//p指向根结点
	while(p!=T)			//空树或遍厉结束时，p==T
	{
		while(p->LTag==Link)  
			p=p->lchild;

		if(!Visit(p)) return ERROR;

		while(p->RTag==Thread && p->rchild!=T)
		{
			p=p->rchild;

			if(!Visit(p)) return ERROR;

		}		//访问后继结点
		p=p->rchild;
	}
	return OK;
}