bint.h

创建二叉树修改二叉树添加二叉树删除二叉树

//屏幕提示后，从键盘输入个数和随机数种子，在数组elem中生成指定个数的数据，供其他程序使用，0表示数据结束
void init0(int elem[])
{
	int i,n;
	while (1)
	{
	    cout << "输入数据个数（0－" << max-1 << "）：" << flush;
		cin >> n;
		if (n >= 0 && n <= max-1)
			break;
		cout << endl;
	}
	while (1)
	{
	    cout << "输入随机数种子（0－32767）：" << flush;
		cin >> i;
		if (i >= 0 && i <= 32767)
			break;
		cout << endl;
	}
	srand(i);       //指定随机数种子，相同的种子将产生相同的数据序列
	rand();

	for (i = 0; i < n; i++)
	{
		elem[i] = rand() % 999 +1;             //存放原始数据
	}
	elem[n] = 0;
	Tree=init1();
}
//MAP数据显示
void getWidth(BiTNode *Tree, int depth, int shift, char map[max*2][max*2])
{
	int i;

	if (Tree->left != NULL)
	{
		getWidth(Tree->left, depth+1, shift, map);
		Tree->tem1 = Tree->left->tem1 + Tree->left->tem2 + 1;
		for (i=(Tree->left->tem1+shift)*2; i<shift*2; i=i+2)
		{
			map[depth*2+1][i]='-';
			map[depth*2+1][i+1]='-';
		}
	}
	else Tree->tem1 = 0;
	if (Tree->right != NULL)
	{
		getWidth(Tree->right, depth+1, shift+Tree->tem1+1, map);
		Tree->tem2 = Tree->right->tem1 + Tree->right->tem2 + 1;
	}
	else Tree->tem2 = 0;

	for (i=shift*2; i<(Tree->tem1+shift)*2; i++)
		map[depth*2][i]=' ';
	
	map[depth*2][(Tree->tem1+shift)*2]=(char)(Tree->data / 1000 +48);
	map[depth*2][(Tree->tem1+shift)*2+1]=(char)(Tree->data / 100 % 10 +48);
	map[depth*2][(Tree->tem1+shift)*2+2]=(char)(Tree->data / 10 % 10 +48);
	map[depth*2][(Tree->tem1+shift)*2+3]=(char)(Tree->data %10 +48);
	if (Tree->data<1000)
	{
		map[depth*2][(Tree->tem1+shift)*2]=' ';
		if (Tree->data<100)
		{
			map[depth*2][(Tree->tem1+shift)*2+1]=map[depth*2][(Tree->tem1+shift)*2+2];
			map[depth*2][(Tree->tem1+shift)*2+2]=map[depth*2][(Tree->tem1+shift)*2+3];
			map[depth*2][(Tree->tem1+shift)*2+3]=' ';
			if (Tree->data<10)
				map[depth*2][(Tree->tem1+shift)*2+1]=' ';
		}
	}

	if (Tree->left != NULL)
	{
		map[depth*2+1][(Tree->left->tem1+shift)*2+1]=(char)0xa9;
		map[depth*2+1][(Tree->left->tem1+shift)*2+2]=(char)0xb0;
		map[depth*2+1][(Tree->tem1+shift)*2+1]=(char)0xa9;
		map[depth*2+1][(Tree->tem1+shift)*2+2]=(char)0xbc;
		for (i=(Tree->left->tem1+shift)*2+3; i<(Tree->tem1+shift)*2; i=i+2)
		{
			map[depth*2+1][i]=(char)0xa9;
			map[depth*2+1][i+1]=(char)0xa4;
		}
	}
	if (Tree->right != NULL)
	{
		map[depth*2+1][(Tree->tem1+shift)*2+1]=(char)0xa9;
		map[depth*2+1][(Tree->tem1+shift)*2+2]=(char)0xb8;
		map[depth*2+1][(Tree->tem1+Tree->right->tem1+shift)*2+3]=(char)0xa9;
		map[depth*2+1][(Tree->tem1+Tree->right->tem1+shift)*2+4]=(char)0xb4;
		for (i=(Tree->tem1+shift)*2+3; i<(Tree->tem1+Tree->right->tem1+shift)*2+2; i=i+2)
		{
			map[depth*2+1][i]=(char)0xa9;
			map[depth*2+1][i+1]=(char)0xa4;
		}
	}
	if (Tree->left != NULL && Tree->right != NULL)
	{
		map[depth*2+1][(Tree->tem1+shift)*2+1]=(char)0xa9;
		map[depth*2+1][(Tree->tem1+shift)*2+2]=(char)0xd8;
	}

}

//生成文件Map.txt，显示以Tree为根指针的二叉树
void showBinTree(BiTNode *Tree)
{
	char map[max*2][max*2];
	FILE *f;
	int i,j,k;

	f=fopen("Map.txt","w");
	if (Tree == NULL)
	{
		fprintf(f,"空树");
		fclose(f);
		return;
	}
	for (i=0; i<max*2; i++)
		for (j=0; j<max*2; j++)
			map[i][j]=' ';
	getWidth(Tree,0,0,map);
	for (i=0; i<max*2; i++)
	{
		k=max*2-1; 
		while (k>=0 && map[i][k]==' ')
			k--;

		for (j=0; j<=k; j++)
			fprintf(f,"%c",map[i][j]);
		fprintf(f,"\n");
//		if (k<0)
//			break;
	}
	fclose(f);
}

//供init1O调用的释放函数
void release(BiTNode *Tree)
{
	if (Tree==NULL)
		return;
	release(Tree->left);
	release(Tree->right);
	free(Tree);
}

//供init1调用的生成函数
BiTNode *Generate(int n)
{
	int nl;
	if (n==0)
		return NULL;

	BiTNode *P = new BiTNode;
	P->data = rand() % 999 +1;
	nl=rand() % (n);
	P->left = Generate(nl);
	P->right = Generate(n-1-nl);
	return P;
}

//屏幕提示后，从键盘输入个数和随机数种子，以Tree为根指针，生成指定结点个数的二叉树，供其他程序使用，同时生成文件Map.txt，显示这课二叉树
BiTNode *init1()
{
	int i,n;

	while (1)
	{
	    cout << "输入数据个数（0－" << max-1 << "）：" << flush;
		cin >> n;
		if (n >= 0 && n <= max-1)
			break;
		cout << endl;
	}
	while (1)
	{
	    cout << "输入随机数种子（0－32767）：" << flush;
		cin >> i;
		if (i >= 0 && i <= 32767)
			break;
		cout << endl;
	}
	srand(i);  //指定随机数种子，相同的种子将产生相同的数据序列
	rand();

//	release(Tree);
	return Generate (n);
}
//先序显示
void PreOrderTraverse(BiTNode *Tree)
{
    counter=0;
	system("cls");
    if(Tree)
	{
		cout<<setw(5)<<Tree->data <<"\t";
		counter++;
		if(counter%10==0)
			cout<<" ";
		PreOrderTraverse(Tree->left );
		PreOrderTraverse(Tree->right );
	}
	
}
//中序显示
void InOrderTraverse(BiTNode *Tree)
{
	counter=0;
	system("cls");
	if(Tree)
	{
		InOrderTraverse(Tree->left );
		cout<<setw(5)<<Tree->data <<"\t";
		counter++;
		if(counter%10==0)
			cout<<" "<<endl;
		InOrderTraverse(Tree->right );
	}

}
//后序显示
void PostOrderTraverse(BiTNode *Tree)
{
	counter=0;
	system("cls");
	if(Tree)
	{
	PostOrderTraverse(Tree->left );
		PostOrderTraverse(Tree->right );
		cout<<setw(5)<<Tree->data <<"\t";
		counter++;		
		if(counter%10==0)
			cout<<" "<<endl;
	}
}
//二叉排序树的构造
void BuildsortTree(int x)
{
	BiTNode *q,*p=Tree;
	while(p)
	{
		if(p->data ==x)
			return;                         
		q=p;                                
		p=(x<p->data)?p->left:p->right ;
	}
	p=(BiTNode *)malloc(LEN);
	p->data =x;
	p->left =p->right=NULL;
	if(Tree==NULL)
		Tree=p;
	else
	{
		if(x<q->data )
		q->left=p;
		else
				q->right=p;
	}
}

void BinarysortTree(BiTNode *Tree)
{
	int i=0;
	while(elem[i])
	{
		BuildsortTree(elem[i]);
		i++;
	}
	cout<<"二叉排序树构造成功!"<<endl<<flush;
}
//二叉排序树的查找
void SearchTree(BiTNode *Tree)
{
   if(!b)
	{
		cout<<"请先建立二叉排序树!"<<endl<<flush;
		wait();
		return;
	}
	else
	{
		int a,i=0;
		cout<<"请输入查找结点值:";
		cin>>a;
		BiTNode *p=Tree;
		while(p)
		{
			if(p->data==a)
			{
				cout<<"找到该结点值。\n";
				cout<<"查找成功!!!"<<"比较次数："<<i<<endl<<flush;
				wait();
				return;
			}
			else
			{
				p=(a<p->data )?p->left :p->right ;
				i++;
			}
		}
		cout<<"查找失败!"<<endl<<flush;
		wait();
		free(p);
	}

}
//二叉排序树的删除
void DeleteTree(BiTNode *Tree)
{
if(!b)
	{
		cout<<"请先建立二叉排序树!"<<endl<<flush;
		wait();
		return;
	}
	else
	{
		int key;
		cout<<"请输入要删除的值:";
		cin>>key;
		BiTNode *parent=NULL,*p=Tree,*q,*s;
		while(p)
		{
			if(p->data ==key)
				break;
			parent=p;
			p=(key<p->data )?p->left :p->right ;
		}
		if(!p)                             //查找不成功
		{
			cout<<"找不删除结点。\n"
				<<"删除失败!"<<endl<<flush;
			wait();
			return;
		}
		if(!p->right )                      //右子树为空
		{
			if(parent->left==p)//p是左边的
			{
				parent->left=p->left;
				 free(p);
			}
			else if(parent->right==p)		 //p是右边的
			{
	    		parent->right=p->left;
	    		 free(p);
			}
		}
		else if(!p->left )                  //左子树为空   
		{
			if(parent->left==p)				//p是左边的
			{
				parent->left=p->right;
				 free(p);
			}
			else if(parent->right==p)       //p是右边的
			{
	    		parent->right=p->right;
	    		 free(p);
			}
		}
		else                                //左右子树均不为空
		{
			q=p;
			s=p->left ;
			while(s->right )
			{
				q=s;
				s=s->right ;
			}
			p->data =s->data ;
			if(q!=p)
				q->right =s->left ;
			else
				q->left =s->left ;
			delete s;
		}
		showBinTree(Tree);
		cout<<"找到该结点。\n";
		cout<<"删除成功!"<<endl<<flush;
		wait();
	}

}