bitree.h

线索化二叉排序树操作：具有线索化节点结构的二叉排序树。基于学生分数统计的应用背景

//二叉树操作
#pragma once

#include "StdAfx.h"
#include "TreeStruct.h"

bool ShowStuInfo(TStuData Stu)
{
	if (FLAG_ShowStuInfo)
	{
		cout<<Stu.StuNumber.c_str()<<" "<<Stu.StuName.c_str()<<" "<<Stu.StuScore<<" "<<Segment2String(GetSegment(Stu.StuScore)).c_str()<<endl;
		return true;
	}
	else return false;
}
bool ShowNode(TreeNode *p)
{
	if (FLAG_ShowNode)
	{
		cout<<Segment2String(p->data.segment).c_str()<<"["<<p->data.amount<<"]";
		if (FLAG_ShowStuInfo)
		{
			cout<<endl;
			for (int i=0;i<p->data.amount;i++)
			{
				ShowStuInfo(p->data.stu[i]);
			}
		}
		return true;
	}
	else return false;
	
}
bool SearchNode(TreeNode *T, TreeNode *last, TreeNode *&ptr,int seg)
{
	if (!T) {ptr=last;return false;}
	else
	{
		if (seg==T->data.segment) {ptr=T;return true;}
		else if(seg<T->data.segment)
		{	
			if (T->LTag==Link) return SearchNode(T->lchild,T,ptr,seg);
			else return SearchNode(NULL,T,ptr,seg);
		}
		else if(seg>T->data.segment)
		{	
			if (T->RTag==Link) return SearchNode(T->rchild,T,ptr,seg);
			else return SearchNode(NULL,T,ptr,seg);
		}
	}
	return false;
}
int SearchNode_StuNumber(TreeNode *T, TreeNode *&ptr, string Num)
{
	int count=0;
	if (!T) return 0;
	else
	{
		for (int i=0;i<T->data.amount;i++)
			if (!strcmp(T->data.stu[i].StuNumber.c_str(),Num.c_str()))
			{
				count++;
				ptr = T;
				ShowStuInfo(T->data.stu[i]);
			}
	}
	if (T->LTag==Link) count+=SearchNode_StuNumber(T->lchild,ptr,Num);
	if (T->RTag==Link) count+=SearchNode_StuNumber(T->rchild,ptr,Num);
	return count;
}
int SearchNode_StuName(TreeNode *T, string Name)
{
	int count=0;
	if (!T) return 0;
	else
	{
		for (int i=0;i<T->data.amount;i++)
			if (!strcmp(T->data.stu[i].StuName.c_str(),Name.c_str()))
			{
				count++;
				ShowStuInfo(T->data.stu[i]);
			}
	}
	if (T->LTag==Link) count+=SearchNode_StuName(T->lchild,Name);
	if (T->RTag==Link) count+=SearchNode_StuName(T->rchild,Name);
	return count;
}
int SearchNode_StuScore(TreeNode *T, int Score)
{
	int count=0;
	if (!T) return 0;
	else
	{
		for (int i=0;i<T->data.amount;i++)
			if (T->data.stu[i].StuScore==Score)
			{
				count++;
				ShowStuInfo(T->data.stu[i]);
			}
	}
	if (T->LTag==Link) count+=SearchNode_StuScore(T->lchild,Score);
	if (T->RTag==Link) count+=SearchNode_StuScore(T->rchild,Score);
	return count;
}
bool InsertNode(TreeNode *&T,TreeNode *newn)
{
	
	TreeNode *p = NULL;

	if(!SearchNode(T,NULL,p,newn->data.segment))
	{

		if (!p) T=newn;
		else
		{
			if (newn->data.segment>p->data.segment)
			{
				p->rchild=newn;
				p->RTag=Link;
			}
			else
			{
				p->lchild=newn;
				p->LTag=Link;
			}
		}
	}
	return true;
}
bool InsertNode(TreeNode *&T,TStuData &Stu)
{
	int seg;
	seg = GetSegment(Stu.StuScore);

	TreeNode *p = NULL;
	if(SearchNode(T,NULL,p,seg))
	{	
		p->data.stu[p->data.amount]=Stu;
		p->data.amount++;
		PopSort(p->data.stu,p->data.amount);
	}
	else
	{
		TreeNode *np = new TreeNode;
		np->data.amount=1;
		np->data.segment=seg;
		np->data.stu[0]=Stu;
		np->lchild=NULL;
		np->rchild=NULL;
		np->LTag=Link;
		np->RTag=Link;
		if (!p) T=np;
		else
		{
			if (seg>p->data.segment)
			{
				p->rchild=np;
				p->RTag=Link;
			}
			else
			{
				p->lchild=np;
				p->LTag=Link;
			}
		}
	}
	return true;
}
bool DeleteNode(TreeNode *&T,TreeNode *&p)
{
	TreeNode *s,*q;

	if ((p->LTag==Link)&&(!p->lchild))
	{
		q = p;
		if (p->RTag==Link) p = p->rchild;
		else p=NULL;
		delete(q);
	}
	else if ((p->RTag==Link)&&(!p->rchild))
	{
		q = p;
		if (p->LTag==Link) p = p->lchild;
		else p=NULL;
		delete(q);
	}
	else if ((p->LTag==Link)&&(p->RTag==Link))
	{
		q = p;
		s = p->lchild;
		while ((s->RTag==Link)&&(s->rchild))
		{
			q = s;
			s = s->rchild;
		}
		p->data = s->data;
		if (q!=p) 
		{
			if (s->LTag==Link) q->rchild = s->lchild;
			else q->rchild=NULL;
			q->RTag = Link;
		}
		else 
		{
			if (s->LTag==Link) q->lchild = s->lchild;
			else q->lchild=NULL;
			q->LTag = Link;
		}
		delete(s);
	}
	return true;
}
bool DeleteNode(TreeNode *&T,int seg)
{
	TreeNode *p=NULL;
	if (SearchNode(T,NULL,p,seg))
	{
		DeleteNode(T,p);
	}
	else return false;
	return true;
}
bool DeleteNode(TreeNode *&T,string StuNum)
{
	TreeNode *p=NULL;

	if (SearchNode_StuNumber(T,p,StuNum))
	{
		if (p->data.amount==1)
		{
			DeleteNode(T,p);
		}
		else
		{
			int i;
			for (i=0;i<p->data.amount;i++)
				if (p->data.stu[i].StuNumber.c_str()==StuNum.c_str()) break;
			p->data.amount--;
			for (int j=i;j<p->data.amount;j++) p->data.stu[j]=p->data.stu[j+1];
		}
	}
	else return false;
	return true;
}
bool LayerTraverse(TreeNode *T)
{
	if (!T) return false;
	typedef struct {
		TreeNode * ptr;
		int layer;
		int order;
	} NodeMark;
	NodeMark queue[11];
	int head=0,rear=0;

	NodeMark m;
	int maxl=0,o=0;

	queue[0].ptr=T;
	queue[0].layer=0;
	queue[0].order=1;

	while (head<=rear)
	{
		m = queue[head];
		if ((m.ptr->LTag==Link)&&(m.ptr->lchild))
		{
			rear++;
			queue[rear].ptr = m.ptr->lchild;
			queue[rear].layer = m.layer + 1;
			queue[rear].order = 2*(m.order)-1;			
		}
		if ((m.ptr->RTag==Link)&&(m.ptr->rchild))
		{
			rear++;
			queue[rear].ptr = m.ptr->rchild;
			queue[rear].layer = m.layer + 1;
			queue[rear].order = 2*(m.order);			
		}
		head++;
	}
	maxl = queue[rear].layer;

	//Output
	FLAG_ShowNode = true;
	FLAG_ShowStuInfo = false;
	ShowNode(queue[0].ptr);
	cout<<endl;
	int t = 1;
	for (int l=1;l<=maxl;l++)
	{
		o=0;
		while (queue[t].layer==l)
		{
			for (int j=1;j<=queue[t].order-o-1;j++) cout<<"() ";
			ShowNode(queue[t].ptr);
			cout<<" ";
			o = queue[t].order;
			t++;
		}
		cout<<endl;
	}

	return true;
}
bool InThreading(TreeNode *&p, TreeNode *&pre)
{
	if (p)
	{
		if (p->LTag==Link) InThreading(p->lchild,pre);
		if ((p->LTag==Link)&&(!p->lchild))
		{
			p->LTag = Thread;
			p->lchild = pre;
		}
		if ((p->RTag==Link)&&(!pre->rchild))
		{
			pre->RTag = Thread;
			pre->rchild = p;
		}
		pre = p;
		if (p->RTag==Link) InThreading(p->rchild,pre);
	}
	return true;
}
bool InOrderThreading(TreeNode *&T, TreeNode *&Thrt)
{
	TreeNode *pre = NULL;

	Thrt = new TreeNode;
	Thrt->LTag = Link;
	Thrt->RTag = Thread;
	Thrt->rchild = Thrt;
	if (!T) Thrt->lchild = Thrt;
	else
	{
		Thrt->lchild = T;
		pre = Thrt;
		InThreading(T,pre);
		pre->rchild = Thrt;
		pre->RTag = Thread;
		Thrt->rchild = pre;
	}
	return true;
}
bool InOrderTraverse(TreeNode *&T,TreeNode *&Thrt,bool (* visit)(TreeNode* e))
{
	TreeNode *p;
	InOrderThreading(T,Thrt);
	p = Thrt->lchild;
	while (p!=Thrt)
	{
		while (p->LTag==Link) p = p->lchild;
		visit(p);
		while (p->RTag == Thread && p->rchild != Thrt)
		{
			p = p->rchild;
			visit(p);
		}
		p = p->rchild;
	}
	return true;
}
inline SaveNode(TreeNode *p, ofstream &fout)
{
	fout<<p->data.segment<<" "<<p->data.amount<<endl;
	for (int i=0;i<p->data.amount;i++)
	{
		fout<<p->data.stu[i].StuNumber.c_str()<<endl;
		fout<<p->data.stu[i].StuName.c_str()<<endl;
		fout<<p->data.stu[i].StuScore<<endl;
	}
}
bool SaveTree(TreeNode *&T,TreeNode *&Thrt,string filename)
{
	ofstream fout;  
	
	typedef struct {
		TreeNode * ptr;
		int layer;
		int order;
	} NodeMark;
	NodeMark queue[11];
	int head=0,rear=0;
	
	NodeMark m;
	int maxl=0,o=0;
		
	
	if (!T) return false;

	queue[0].ptr=T;
	queue[0].layer=0;
	queue[0].order=1;
	
	while (head<=rear)
	{
		m = queue[head];
		if ((m.ptr->LTag==Link)&&(m.ptr->lchild))
		{
			rear++;
			queue[rear].ptr = m.ptr->lchild;
			queue[rear].layer = m.layer + 1;
			queue[rear].order = 2*(m.order)-1;			
		}
		if ((m.ptr->RTag==Link)&&(m.ptr->rchild))
		{
			rear++;
			queue[rear].ptr = m.ptr->rchild;
			queue[rear].layer = m.layer + 1;
			queue[rear].order = 2*(m.order);			
		}
		head++;
	}
	maxl = queue[rear].layer;



	fout.open(filename.c_str());
	if (fout.fail()) return false;

	int t=0;
	for (int l=0;l<=maxl;l++)
	{
		while (queue[t].layer==l)
		{
			SaveNode(queue[t].ptr,fout);
			t++;
		}
	}

	fout.close();
	return true;
}
bool RebuildTree(TreeNode *&T, TreeNode *&Thrt, string filename)
{
	ifstream fin;
	TreeNode *p= new TreeNode;;
	char cc[100];

	fin.open(filename.c_str());
	if (fin.fail()) return false;
	T=NULL;
	Thrt=NULL;
	while (!fin.eof())
	{
		fin>>p->data.segment>>p->data.amount;
		for (int i=0;i<p->data.amount;i++)
		{
			fin>>cc;
			p->data.stu[i].StuNumber=cc;
			fin>>cc;
			p->data.stu[i].StuName=cc;
			fin>>p->data.stu[i].StuScore;
			InsertNode(T,p->data.stu[i]);
		}
	}
	fin.close();
	InOrderThreading(T,Thrt);
	return true;
}