intbtree.h

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

//#include"TBTree.h"
#include<iostream.h>
#include<strstrea.h>
#include<string.h>
#include<stdlib.h>
#include<iomanip.h>
struct TreeNode2{

	char data;
	int ltag;
	int rtag;
	TreeNode2*left;
	TreeNode2*right;
	
};

class InTree
{
public:
	TreeNode2 *BT;
	TreeNode2 *pre;
	InTree();
	void CreatInTree();
    void Print(TreeNode2*p);
	void ThreadInTree(TreeNode2*p);
    void PrintInTBTree(TreeNode2*p);
    TreeNode2* InTBTreePre(TreeNode2*p);
    TreeNode2* InTBTreeNext(TreeNode2*p);  
	void Print2(TreeNode2*p);
};

InTree::InTree(){
	BT=NULL;
	pre=NULL;
}

void InTree::CreatInTree()
{
	TreeNode2* s[10];
	int top=-1;
    

	
	TreeNode2*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 TreeNode2;
			p->ltag=0;
			p->rtag=0;
			p->data=ch;
			p->left=p->right=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 InTree::Print(TreeNode2*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 InTree::ThreadInTree(TreeNode2*p){
     if(p!=NULL){
        if(p->ltag==0)ThreadInTree(p->left);
		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->rtag==0)ThreadInTree(p->right);
	}
}

void InTree::PrintInTBTree(TreeNode2*p){
	
	if(p!=NULL){
	while(p->ltag==0)p=p->left;
	do{
        cout<<p->data<<setw(5);
		p=InTBTreeNext(p);
	}while(p!=NULL);
	}
}

TreeNode2* InTree::InTBTreePre(TreeNode2*p){
	TreeNode2*q;
	if(p->ltag==1)q=p->left;
	else{
		q=p->left;
		while(q->rtag==0)q=q->right;
	}
	return q;
}

TreeNode2*InTree::InTBTreeNext(TreeNode2 *p){

	if(p->rtag==1)return p->right;
	else {
		p=p->right;
		while(p->ltag==0)p=p->left;
		return p;
	}
}



void InTree::Print2(TreeNode2*p){
	TreeNode2*pq;
	if(p!=NULL){
	while(p->ltag==0)p=p->left;
	do{
        cout<<setw(8)<<p->data<<setw(8)<<p->ltag<<setw(8);
		if(p->ltag==1){
			pq=InTBTreePre(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=InTBTreeNext(p);
			if(pq!=NULL)cout<<pq->data<<setw(8);
			else cout<<"NULL"<<setw(8);
		}
		else cout<<setw(8);
		p=InTBTreeNext(p);
		cout<<endl;

	}while(p!=NULL);
	}
}

	

void choice2(){
    system("cls");
	cout<<endl;
	cout<<"             --------------中序线索二叉树的前序遍历--------------"<<endl<<endl;
    char c2;
	do{
	InTree HT=InTree();
    HT.CreatInTree();
	cout<<endl;
	cout<<"二叉树初始状态广义表形式的输出:";
    HT.Print(HT.BT);
	cout<<endl<<endl;
	HT.ThreadInTree(HT.BT);
    cout<<"对建立的二叉线索树进行中序遍历,序列为:";
    HT.PrintInTBTree(HT.BT);
	cout<<endl<<endl;
	cout<<"按中序遍历序列显示各结点的线索以及所指结点:"<<endl<<endl;
	cout<<setw(42)<<"结点  左线索  左指针  右线索  右指针"<<endl<<endl;
    HT.Print2(HT.BT);
	cout<<endl;
	cout<<"是否继续(y/n)";
	cin>>c2;
	}while(c2=='y');

}