coursesystems.cpp

用C生成一个课程二叉树,同时先、中、后序遍历该二叉树

# include"basic.h"
# include"const.h"

//*************函数声明
void inorder(BTnodeptr );
void preorder(BTnodeptr );
void backorder(BTnodeptr );
void creat(BTnodeptr &);
void insertnode(TNodeptr &, BTnodeptr &);
void dele(TNodeptr );
void insert(BTnodeptr& );
void display();

//*************全局变量
int i=0;
TNodeptr head;
BTnodeptr Troot;

//*************主程序
int main()
{
	FILE *fp;
	fp = fopen("CourseHierarchy.txt", "r");//读文件

	if(!fp)
	{
		printf("不能打开文件CourseHierarchy.txt！");
		getchar();
		exit(1);
	}

	int pre, sco;
	TNodeptr pt;
	head = (TNodeptr) malloc(sizeof(TNode));

	head->next = NULL;

//课程依次保存在一个倒连中
	
	while(fscanf(fp,"%d%d", &pre, &sco) != EOF )
	{
		i ++;
		pt = (TNodeptr) malloc (sizeof(TNode));

		if(!pt) exit(1);

		pt->data.CouSer = i;	//初始化课程号
		pt->data.CouSco = sco;	//初始化课程学分
		pt->data.PreCou = pre;	//初始化课程先修课
		
		pt->next = head->next;
		head->next = pt;
	}

fclose(fp);//关闭文件

//把倒链转换成二叉树
	Troot = NULL;
	TNodeptr del;

	pt = head->next;
	while(pt)						//寻找根结点
	{
		if(pt->data.PreCou == 0 && Troot == NULL)
		{
			Troot = (BTnodeptr) malloc( sizeof(BTnode));
			Troot->data = pt->data;

			Troot->lchild = NULL;
			Troot->rchild = NULL;
			
			del = pt->next;
			dele(pt);
			pt = del;
			break;
		}
		pt = pt->next;
	}

	creat (Troot);
	display();
	return 0;
}

//**********生成树
void creat(BTnodeptr &p)
{
	if(p != NULL)
	{
		insert(p);
		if(p->lchild != NULL)	creat(p->lchild);
		if(p->rchild != NULL)	creat(p->rchild);
	}
}//creat

//************在课程链表中删除已经加入到树中的结点
void dele(TNodeptr q)
{
	TNodeptr s, p;
	s = head;
	while(s->next != q && s->next != NULL) 	s = s->next;

	p = s->next;
	if(s->next == NULL) return;
	s->next = s->next->next;
	free(p);
}

//************在树中插入新的结点
void insert(BTnodeptr& p)
{
	TNodeptr q ,qt;	

	q = head->next;
	while(q)
	{
		if(q->data.PreCou == p->data.CouSer)//左孩子
		{
			BTnodeptr lchild, frp;
			lchild = (BTnodeptr) malloc( sizeof(BTnode));
			if(!lchild) 
			{
				printf("hello! you are wrong!!\n");
				exit(1);
			}

			lchild->lchild = lchild->rchild = NULL;
			lchild->data = q->data;
			
			if(p->lchild != NULL)//左孩子不空，为左孩子的最右一个孩子
			{
				frp = p->lchild;// frp指向左孩子
				while(frp->rchild) frp = frp->rchild;//找到左孩子的最右一个孩子

				frp->rchild = lchild;//接为右孩子
			}
			else p->lchild = lchild;//接为左孩子

			qt = q->next;
			dele(q);
			q = qt;
		}
		else if(q->data.PreCou == p->data.PreCou)//右孩子
		{
			BTnodeptr rchild;
			BTnodeptr pt;
			rchild = (BTnodeptr) malloc(sizeof(BTnode));
			if(!rchild) 
			{
				printf("hello! you are wrong!!\n");
				exit(1);
			}

			rchild->lchild = rchild->rchild = NULL;
			rchild->data = q->data;
			pt = p;
			
			while(pt->rchild != NULL) pt = pt->rchild;//寻找右子树的最右一个孩子

			pt->rchild = rchild;

			qt = q->next;
			dele(q);
			q = qt;
		}
		else q = q->next;
	}
}//insert

//***********先序遍历二叉树
void preorder(BTnodeptr T)
{
	if(T != NULL)
	{ 
		printf("%-4d", T->data.CouSer);
		if(T->lchild != NULL)
			preorder(T->lchild);
		if(T->rchild != NULL)
			preorder(T->rchild);
	}
}//preorder

//**********中序遍历二叉树
void inorder(BTnodeptr T)
{ 
	if (T != NULL)   
	{  
		if (T->lchild != NULL) 
			inorder(T->lchild);
		printf("%-4d",T->data.CouSer);		
		if (T->rchild != NULL)
			inorder(T->rchild);
   }
}// inorder

//***********后序遍历二叉树
void backorder(BTnodeptr T)
{
	if(T != NULL)
	{
		if(T->lchild != NULL)
			backorder(T->lchild);
		if(T->rchild != NULL)
			backorder(T->rchild);
		printf("%-4d", T->data.CouSer);
	}
}// backorder

//***********先、中、后序遍历二叉树
void display()
{
	printf("以下是对课程二叉树的遍历结果：\n");
	printf("\n先序遍历二叉树：");
	preorder(Troot);

	printf("\n中序遍历二叉树：");
	inorder(Troot);

	printf("\n后序遍历二叉树：");
	backorder(Troot);
	printf("\n");
	fflush(stdin);
	getchar();
}//display