posttbtree.h

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

#include<iostream.h>
#include<strstrea.h>
#include<string.h>
#include<stdlib.h>
#include<iomanip.h>
//#include"InTBTree.h"
struct TreeNode3{

	char data;
	int ltag;
	int rtag;
	TreeNode3*left;
	TreeNode3*right;
	TreeNode3*parent;
};

class PostTBTree
{
public:
	TreeNode3 *BT;
	TreeNode3 *pre;
	PostTBTree();
	void CreatPostTree();
    void Print(TreeNode3*p);
	void ThreadPostTree(TreeNode3*p);
    void PrintPostTBTree(TreeNode3*p);
    TreeNode3* PostTBTreePre(TreeNode3*p);
    TreeNode3* PostTBTreeNext(TreeNode3*p);
	void Print3(TreeNode3*p);
};

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

void PostTBTree::CreatPostTree()
{
	TreeNode3* s[10];
	int top=-1;
    

	
	TreeNode3*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 TreeNode3;
			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 PostTBTree::Print(TreeNode3*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 PostTBTree::ThreadPostTree(TreeNode3*p){
	
      if(p!=NULL){
       	if(p->ltag==0)ThreadPostTree(p->left);
		if(p->rtag==0)ThreadPostTree(p->right);
		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;
		}
		if(pre!=NULL&&pre->ltag==0&&pre->rtag==0)
		{
			pre->parent=p;
		}
		pre=p;
	
	}
}

void PostTBTree::PrintPostTBTree(TreeNode3*p){
     if(p!=NULL){
	   while(p->ltag==0)p=p->left;
	    do{
           cout<<p->data<<setw(5);
		   p=PostTBTreeNext(p);
		}while(p!=NULL);
	}
}

TreeNode3* PostTBTree::PostTBTreeNext(TreeNode3*p){
	if(p->ltag==1)return p->right;
/*	if(p->ltag==0&&p->rtag==0)return p->parent;
	else return NULL;*/
	else{
		if(p->parent==NULL) 
			return 0;
        // return p->parent;
		if(p->parent->right==p||(p->parent->left==p&&p->rtag==1))
			return p->parent;
		if(p->parent->left==p&&p->parent->rtag==0)
		{
			while(p->parent->right->ltag==0||p->parent->right->rtag==0)
			{
				if(p->parent->right->ltag==0) p->parent->right=p->parent->right->left;
		        else p->parent->right=p->parent->right->right;
			}
			return p->parent->right;
		}

		}

	}
		


TreeNode3* PostTBTree::PostTBTreePre(TreeNode3*p){
	if(p->ltag==1)return p->left;
	else return NULL;
}

void PostTBTree::Print3(TreeNode3*p){
    TreeNode3*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=PostTBTreePre(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=PostTBTreeNext(p);
			if(pq!=NULL)cout<<pq->data<<setw(8);
			else cout<<"NULL"<<setw(8);
		}
		else cout<<setw(8);
		p=PostTBTreeNext(p);
		cout<<endl;

	}while(p!=NULL);
	}
}

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