线索二叉数.cpp

有很多数据结构的课设

// 线索二叉数.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"

struct node
{
	char dara;
	int ltag;
	int rtag;
	node * lchild;
	node * rchild;
};

struct thread
{
	node * front;
	node * * next;
};
thread thr;

char b[20];
int i=0;

int createbitree(node * &T)//按先序法构建一个二叉树
{
	char data1;
    data1=getchar();
	if(data1==' ')
		T=NULL;
	else
	{
		T=new node;
		T->dara=data1;
		T->ltag=T->rtag=0;
		createbitree(T->lchild);
		
		createbitree(T->rchild);
	}
	return 1;
}

int inordertraverse(node *T)//对二叉树进行中序遍历
{
	if(T)
	{
		if(inordertraverse(T->lchild))
		{
			cout<<T->dara<<"    ";
			if(inordertraverse(T->rchild))
				return 1;
		}
		return 0;
	}
	else return 1;
}

int search1(node *T)//将二叉树按中序读入一个数组中
{
	if(T)
	{
		if(search1(T->lchild))
		{
			b[i]=T->dara;
			i++;
			if(search1(T->rchild))
				return 1;
		}
		return 0;
	}
	else return 1;
}

node * search(node *T,char a)//对二叉树进行中序chazhao
{
	if(T)
	{
		if(T->dara==a)
			return T;
		if(inordertraverse(T->lchild))
			if(inordertraverse(T->rchild))
				return NULL;
		return NULL;
	}
	else return NULL;
}
node * search2(node *T,char a)//对二叉树进行中序chazhao,返回节点的父母节点指针
{
	if(T)
	{
		if(T->lchild)
		{
			if(T->lchild->dara==a)
				return T;
		}
		else if(T->rchild)
			if(T->rchild->dara==a)
				return T;

		if(inordertraverse(T->lchild))
			if(inordertraverse(T->rchild))
				return NULL;
		return NULL;
	}
	else return NULL;
}


//shenehuoweiyuan 1#308
void inthreading(node *p);
node *pre;
int threadbitree(node * T,node *& thrt)//对一个二叉树进行中序线索化
{
	thrt=new node;
	thrt->ltag=0;
	thrt->rtag=1;
	thrt->rchild=thrt;
	if(!T)
		thrt->lchild=thrt;
	else
	{
		thrt->lchild=T;
		pre=thrt;
		inthreading(T);
		pre->rchild=thrt;
		pre->rtag=1;
		thrt->rchild=pre;
	}
	return 1;
}

void inthreading(node *p)
{
	if(p)
	{
		inthreading(p->lchild);
		if(!p->lchild)
		{
			p->ltag=1;
			p->lchild=pre;
		}
		if(!pre->rchild)
		{
			pre->rtag=1;
			pre->rchild=p;
		}
		pre=p;
		inthreading(p->rchild);
	}
}


int _tmain(int argc, _TCHAR* argv[])
{
	node * T=NULL;
	cout<<"请先按先序法输入一个二叉树，请输入："<<endl;
	createbitree(T);
	cout<<endl<<"二叉树已经构建成功"<<endl;
	
	thr.front=NULL;
	thr.next=NULL;
	node * thrt;
A:
	system("cls");
    cout<<endl<<"请选择你要进行的操作："<<endl;
	cout<<endl<<"1，中序遍历输出   2，中序线索化   3，求指定节点的前驱、后继"<<endl;
	cout<<"4，插入一个节点   5，删除一个节点   6，退出"<<endl;
	int opinion;
	cin>>opinion;

	if(opinion==1)
		inordertraverse(T);//中序遍历
    else if(opinion==2)
	{
		threadbitree(T,thrt);//中序线索化
		cout<<endl<<"线索化完毕！"<<endl;
	}
	else if(opinion==3)
	{
		cout<<endl<<"请选择：   1，求前驱       2，求后继       3，返回  "<<endl;
		int opinion1;
		cin>>opinion1;
		search1(T);
		if(opinion1==1)
		{
			cout<<endl<<"你要求哪个节点的前驱，请输入：     ";
			char ch1;
			cin>>ch1;
			
			for(int i=0;i<20;i++)
			{
				if(ch1==b[i])
				{
					if(i==0)
					{
						cout<<endl<<"此节点没有前驱"<<endl;
						goto B;
					}
					else
					{
						cout<<endl<<"此节点的前驱是：   "<<b[i-1]<<endl;
						goto B;
					}
				}
			}
			cout<<endl<<"你要查询的节点不存在，请确认"<<endl;
			goto B;
		
		}
		else if(opinion1==2)
		{
			cout<<endl<<"你要求哪个节点的后继，请输入：     ";
			char ch1;
			cin>>ch1;
			for(int i=0;i<20;i++)
			{
				if(ch1==b[i])
				{
					//if(i==0)
					//{
					//	cout<<endl<<"此节点没有前驱"<<endl;
					//	goto B;
					//}
					//else
					//{
						cout<<endl<<"此节点的后继是：   "<<b[i+1]<<endl;
						goto B;
					//}
				}
			}
			cout<<endl<<"你要查询的节点不存在，请确认"<<endl;
			goto B;
			
		}
		else
		{
			goto A;
		}

	}
	else if(opinion==4)
	{
		cout<<endl<<"请输入你准备在哪个节点后插入节点"<<endl;
		char ch2,ch3;
		cin>>ch2;
		cout<<endl<<"请输入你要插入的节点"<<endl;
		cin>>ch3;
		node * p=search(T,ch2);
		if(p==NULL)
		{
			cout<<endl<<"你输入的节点不存在，请确认"<<endl;
			goto B;
		}
		else
		{
			node * q=new node;
			q->rchild=p->rchild;
			q->lchild=NULL;
			q->ltag=q->rtag=0;
			p->rchild=q;
			cout<<endl<<"插入成功"<<endl;
			goto B;
		}

	}
	else if(opinion==5)
	{
		cout<<endl<<"请输入你要删除的节点"<<endl;
		char ch4;
		cin>>ch4;
		node * p=search(T,ch4);
		if(p=NULL)
		{
			cout<<endl<<"你输入的节点不存在，请确认"<<endl;
			goto B;
		}
		else
		{
			
			node * q1=search2(T,ch4);
			q1->lchild=NULL;
			delete p;
			cout<<endl<<"删除完毕"<<endl;
		}
	}

B:
	cout<<endl<<endl<<endl;
	cout<<"操作完毕，按任意键进入下一次操作！→"<<endl;
	while (!kbhit());                             //调用库函数，等待用户按键
	goto A;
	return 0;
}