pretbtree.h

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

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

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

class PreTree
{
public:
	TreeNode1 *BT;
	TreeNode1 *pre;
	PreTree();
	void CreatPreTree();
    void Print(TreeNode1*p);
	void ThreadPreTree(TreeNode1*p);
    void PrintPreTBTree(TreeNode1*p);
    TreeNode1* PreTBTreePre(TreeNode1*p);
    TreeNode1* PreTBTreeNext(TreeNode1*p);
	void Print1(TreeNode1*p);
};

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

void PreTree::CreatPreTree()
{
	TreeNode1* s[10];
	int top=-1;
    TreeNode1*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 TreeNode1;
			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 PreTree::Print(TreeNode1*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 PreTree::ThreadPreTree(TreeNode1*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 PreTree::PrintPreTBTree(TreeNode1*p)
{
	while(p!=NULL){
    cout<<p->data<<setw(5);
	p=PreTBTreeNext(p);

	}
}

TreeNode1*PreTree::PreTBTreeNext(TreeNode1*p){
	if(p->ltag==1)return p->right;
	else return p->left;
}

TreeNode1*PreTree::PreTBTreePre(TreeNode1*p){
	if(p->ltag==1)return p->left;
	else return NULL;
}

void PreTree::Print1(TreeNode1*p){
	TreeNode1*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;
	char c1;
	do{ 
    PreTree HT=PreTree();
    HT.CreatPreTree();
	cout<<endl;
	cout<<"二叉树初始状态广义表形式的输出:";
    HT.Print(HT.BT);
	cout<<endl<<endl;
	HT.ThreadPreTree(HT.BT);
    cout<<"对建立的二叉线索树进行前序遍历,序列为:";
    HT.PrintPreTBTree(HT.BT);
	cout<<endl<<endl;
	cout<<"按前序遍历序列显示各结点的线索以及所指结点:"<<endl<<endl;
	cout<<setw(42)<<"结点  左线索  左指针  右线索  右指针"<<endl<<endl;
    HT.Print1(HT.BT);
	cout<<endl;
	cout<<"是否继续(y/n)";
	cin>>c1;
	}while(c1=='y'||c1=='Y');
}