bitree.cpp

创建静态

#include "calculate.cpp"
#include"huffmantree.cpp"
tlink STACK[30];

status creatt(tlink &T)//树的创建
{                     
	char c;	
	cin>>c;
	if(c=='0')
		T=NULL;
	else
	{
		T=(tlink)malloc(sizeof(tnode));
		if(!T) exit (-2);
		T->data=c;
        T->ltag=lin;
		T->rtag=lin;
		creatt(T->left);
		creatt(T->right);
	}
	return 1;
}

void print(tlink T,int n)//树的打印
{
	
	if(T)
	{
		for(int i=0;i<n;i++)
			cout<<"\t";
		cout<<T->data<<endl;
		print(T->left,n+1);
		print(T->right,n+1);
	}
}




void exchange(tlink &T)//交换左右子树
{
	if(T->left==T->right)
		return;
	else
	{
		tlink p=T->left;
		T->left=T->right;
		T->right=p;
	}
	if(T->left)
		exchange(T->left);
	if(T->right)
		exchange(T->right);
}

void upr(char &e)//遍历函数
{
	e=e>='a'&&e<='z'?e-32:e;
	cout<<e<<endl;
}

status traverse(tlink T, void (*visit)(char &e))//中序非递归函数
{
	int i=0;
	tlink p=T;
	STACK[i++]=T;
	while(p||i)
	{
		if(p)
		{
			STACK[i++]=p;
			p=p->left;
		}
		else
		{
			p=STACK[--i];
			visit(p->data);
			p=p->right;
		}
	}
return 1;
}


void tra()
{
	s=traverse(T,upr);
	if(s==1)
	cout<<"遍历成功! "<<kg;
	print(T,0);
}





void threading(tlink p) //线索化二叉树(1)
{  
	if (p) 
	{
		threading(p->left);    
		if (!p->left)   
		{ 
			p->ltag = thread; 
			p->left = pre;
		}
		if (!pre->right) 
		{ 
			pre->rtag = thread; 
			pre->right = p; 
		} 
		pre = p;                  
		threading(p->right); 
	}
} 


status inthreading(tlink &thrt, tlink T) //线索化二叉树(2)
{  
	if (!(thrt = (tlink)malloc(sizeof(tnode)))) exit(-2);
	thrt->ltag = lin; 
	thrt->rtag =thread; 
	thrt->right = thrt;              
	if (!T) thrt->left = thrt;      
	else 
	{
		thrt->left = T;
		pre = thrt;
		threading(T); 
		pre->right = thrt; 
		pre->rtag = thread; 
		thrt->right = pre;  
	}
	return 1;
} 



void threa()
{
	s=inthreading(thrt,T);
	if(s==1)
		cout<<"线索化成功! "<<kg;
	else
		cout<<"线索化失败! "<<kg;
}


void traversal(tlink T, void (*visit)(char &e)) //线索化遍历
{
	tlink p = T->left;                            
	while (p != T)
	{                          
		while (p->ltag==lin) 
			p = p->left;
		visit(p->data);
		while (p->rtag==thread && p->right!=T)
		{
			p = p->right;
			visit(p->data);     
		}
		p = p->right; 
	}
	cout<<"遍历成功! "<<kg;
} 



void cret()
{
    cout<<"   *********************罗伟的图***********************   "<<endl;
	cout<<"   ****************************************************   "<<endl; 
	cout<<"   *             请按格式输入二叉树                   *   "<<endl;
	cout<<"   *例如格式：AB00C00(0代表空树，例的输入结果如下):   *   "<<endl;
	cout<<"   *                 A                                *   "<<endl;
	cout<<"   *               ↙ ↘                              *   "<<endl;
	cout<<"   *              B     c                             *   "<<endl;
	cout<<"   *            ↙ ↘ ↙ ↘                           *   "<<endl;
	cout<<"   *     （空）0    0 0    0（空）                    *   "<<endl;
	cout<<"   *      请输入二叉树元素进行创建:                   *   "<<endl;
	cout<<"   ****************************************************   "<<endl;
	cout<< " input !"<<endl;
	s=creatt(T);
	if(s==1)
		cout<<"创建成功 !"<<kg;
	else
		cout<<"创建不成功 !"<<kg;
}



int selectt()
{
	int n;
	cout<<"   *********************************************************************** "<<endl;   
	cout<<"   *                         1.创建二叉树                                * "<<endl;   
	cout<<"   *                         2.中序非递归遍历(大小写转换)                * "<<endl;    
	cout<<"   *                         3.线索化                                    * "<<endl; 
	cout<<"   *                         4.线索化遍历                                * "<<endl;
	cout<<"   *                         5.交换左右子树(线索化后不能使用)            * "<<endl;
	cout<<"   *                         6.凹入法显示(线索化后不能使用)              * "<<endl;
	cout<<"   *                         7.                                          * "<<endl;
	cout<<"   *                         8.                                          * "<<endl;
	cout<<"   *                         9.返回上一层                                * "<<endl;
	cout<<"   *                         0.退出                                      * "<<endl;
	cout<<"   *********************************************************************** "<<endl;       
	cout<<"                            选择你想进行的操作:                            "<<endl;   
	cout<<"请选择0~9!"<<endl;
	cin>>n;
	for(;;)
	{
		if(n<0||n>9)
		{
			cout<<"重选"<<endl;
			cin>>n;
		}
		else
			break;
	}
	return n;	
}