新建 文本文档.txt

前序线索二叉树的前序遍历 中序线索二叉树的中序遍历 后序线索二叉树的后序遍历

class TBTree{
	TreeNode *BT;//定义头结点指针BT
	TreeNode *pre;//定义指向结点前驱的指针pre
    TBTree();//构造函数
	void CreatTree();//二叉树产生函数
    void Print(TreeNode*p);//输出二叉数函数

	void ThreadPreTree(TreeNode*p);//对二叉数进行前序线索话函数
    void PrintPreTBTree(TreeNode*p);//输出线索化后的二叉树函数
    TreeNode* PreTBTreePre(TreeNode*p);//求P结点的前序前驱函数
    TreeNode* PreTBTreeNext(TreeNode*p);//求P结点的前序后驱函数
	void Print1(TreeNode*p);//输出前序线索化后的结点的前后驱和ltag,rtag。

	void ThreadInTree(TreeNode*p);//对二叉树进行中序线索化函数
    void PrintInTBTree(TreeNode*p);//输出中序线索化二叉树
    TreeNode* InTBTreePre(TreeNode*p);//寻找P结点的中序前驱
    TreeNode* InTBTreeNext(TreeNode*p);//寻找P结点的中序后驱   
	void Print2(TreeNode*p);//输出中序线索化后的结点的前后驱和ltag,rtag。

	void ThreadPostTree(TreeNode*p);//对二叉树后序线索化函数
    void PrintPostTBTree(TreeNode*p);//输出线索化后的二叉树函数
    TreeNode* PostTBTreePre(TreeNode*p);//求二叉树的后序前驱
    TreeNode* PostTBTreeNext(TreeNode*p);//求二叉树的后序后驱
	void Print3(TreeNode*p);//输出后序线索化后的结点的前后驱和ltag,rtag。
};
TBTree::TBTree(){
	BT=NULL;
	pre=NULL;
}
void TBTree::CreatTree()
{
	TreeNode* s[10];
	int top=-1;
    

	
	TreeNode*p;
	
	int k;
	char a[50];
b:
	int i=0;
	cout<<"输入以'@'字符为结束符的二叉树广义表表示:"<<endl;
	char shu;
	cin>>shu;
	while(shu!='@'){
		a[i++]=shu;
		cin>>shu;
	}
	if(a[0]=='('||a[0]==')'||a[0]==','||a[i-1]!=')'){
		cout<<"广义表输入有错!请重新输入......"<<endl<<endl;
			goto b;
	}
	for(int j=0;j<i-1;j++){
		if(a[j]==','&&a[j+1]==','){
		cout<<"广义表输入有错!请重新输入......"<<endl<<endl;
				goto b;}
	if(a[j]=='('&&a[j+1]=='('){
        cout<<"广义表输入有错!请重新输入......"<<endl<<endl;
		goto b;
	}
	if((a[j]!='('&&a[j]!=','&&a[j]!=')')&&(a[j+1]!='('&&a[j+1]!=','&&a[j+1]!=')')){
        cout<<"广义表输入有错!请重新输入......"<<endl<<endl;
		goto b;
		}
	}
	a[i++]='@';
	istrstream ins(a);
	char ch;
	ins>>ch;
	while(ch!='@')
	{
		switch(ch)
		{
		case'(':
			top++;s[top]=p;k=1;
			break;
		case')':
			top--;
			break;
		case',':
			k=2;
			break;
		default:
			p=new TreeNode;
			p->ltag=0;
			p->rtag=0;
			p->data=ch;
			p->left=p->right=NULL;
			p->parent=NULL;
			if(BT==NULL)BT=p;
			else
			{
				switch(k)
				{
				case 1:
					s[top]->left=p;
					break;
				case 2:
					s[top]->right=p;				
				}			
			}		
		}
		ins>>ch;	
	}
}
void TBTree::Print(TreeNode*p){
	if(p!=NULL){
    cout<<p->data;
	if(p->left!=NULL||p->right!=NULL){
        cout<<'(';
		Print(p->left);
		if(p->right!=NULL)cout<<',';
	
		Print(p->right);
		cout<<')';
	}
	}
}
void TBTree::ThreadPreTree(TreeNode*p){

	
    if(p!=NULL){
        
		if(pre!=NULL&&pre->rtag==1)pre->right=p;
		if(p->left==NULL){
			p->ltag=1;
			p->left=pre;
		}
		if(p->right==NULL){
		    p->rtag=1;
		}
		pre=p;
		if(p->ltag==0)ThreadPreTree(p->left);
		if(p->rtag==0)ThreadPreTree(p->right);
	}
}
//////////////////////////////////////////////////////////////////
void TBTree::PrintPreTBTree(TreeNode*p)
{
	while(p!=NULL){
    cout<<p->data<<setw(5);
	p=PreTBTreeNext(p);

	}
}
/////////////////////////////////////////////////////////
TreeNode*TBTree::PreTBTreeNext(TreeNode*p){
	if(p->ltag==1)return p->right;
	else return p->left;
}
//////////////////////////////////////////////
TreeNode*TBTree::PreTBTreePre(TreeNode*p){
	if(p->ltag==1)return p->left;
	else return NULL;
}
///////////////////////////////////////////////
void TBTree::Print1(TreeNode*p){
	TreeNode*pq;
	
	while(p!=NULL){
        cout<<setw(8)<<p->data<<setw(8)<<p->ltag<<setw(8);
		if(p->ltag==1)
		{
			pq=PreTBTreePre(p);
			if(pq!=NULL)cout<<pq->data<<setw(8);
			else cout<<"NULL"<<setw(8);
		}
		else cout<<setw(16);
		cout<<p->rtag<<setw(8);
        if(p->rtag==1)
		{
			pq=PreTBTreeNext(p);
			if(pq!=NULL)cout<<pq->data<<setw(8);
			else cout<<"NULL"<<setw(8);
		}
		else cout<<setw(8);
		p=PreTBTreeNext(p);
		cout<<endl;

	}
	
	
}
////////////////////////////////////////////////////////////
void choice1(){
	system("cls");
	cout<<endl;
	cout<<"             --------------前序线索二叉树的前序遍历--------------"<<endl<<endl;
    TBTree fBT=TBTree();
    fBT.CreatTree();
	cout<<endl;
	cout<<"二叉树初始状态广义表形式的输出:";
    fBT.Print(fBT.BT);
	cout<<endl<<endl;
	fBT.ThreadPreTree(fBT.BT);
    cout<<"对建立的二叉线索树进行前序遍历,序列为:";
    fBT.PrintPreTBTree(fBT.BT);
	cout<<endl<<endl;
	cout<<"按前序遍历序列显示各结点的线索以及所指结点:"<<endl<<endl;
	cout<<setw(42)<<"结点  左线索  左指针  右线索  右指针"<<endl<<endl;
    fBT.Print1(fBT.BT);
	cout<<endl;
}