bitree1.cpp

与清华大学版的《数据结构》匹配二叉树的实现：BITREE1.CPP：为主程序

# include <stdio.h>
# include <iostream.h>
# include <stdlib.h>
# include <iomanip.h>
# include "tstack1.h"

/*typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
*/

BiTree CreateBiTree()
{
	BiTree T;
	char x;
	cin>>x;
	if (x=='0') T=NULL;
	else
	{
		T=(BiTNode *)malloc(sizeof(BiTNode));
		T->data=x;
		T->lchild=CreateBiTree();
		T->rchild=CreateBiTree();
	}
	return T;
}
void PreOrderTraverse(BiTree t)
{
	if (t!=NULL)
	{
		printf("%4c",t->data);
		PreOrderTraverse(t->lchild);
		PreOrderTraverse(t->rchild);
	}
}
void InOrderTraverse(BiTree t)
{
	if (t!=NULL)
	{
		InOrderTraverse(t->lchild);
		printf("%4c",t->data);
		InOrderTraverse(t->rchild);
	}
}
void PostOrderTraverse(BiTree t)
{
	if (t!=NULL)
	{
		PostOrderTraverse(t->lchild);
		PostOrderTraverse(t->rchild);
		printf("%4c",t->data);
	}
}

void InOrderTraverseF(BiTree T)
{
	SqStack s;
	BiTree p;
    //cout<<T<<' '<<T->data<<endl;
	InitStack(s); p=T;
	while(p||!stackEmpty(s))
	{
		if(p)
		{
			Push(s,p);
		    //cout<<"p:"<<p<<','<<p->lchild<<','<<p->data<<','<<p->rchild<<endl;
		    p=p->lchild;
		}
		else
		{
			Pop(s,p);
			//cout.width(4);
			//cout<<setw(4)<<p->data;
			printf("%4c",p->data);
			p=p->rchild;
		}
	}

}
void PreOrderTraverseF(BiTree T)
{
	SqStack s;
	BiTree p;
    InitStack(s); p=T;

	while(p||!stackEmpty(s))
	{
		if(p)
		{
			Push(s,p);
			printf("%4c",p->data);
		     //	cout<<setw(4)<<p->data;
		    //cout<<"p:"<<p<<','<<p->lchild<<','<<p->data<<','<<p->rchild<<endl;
		    p=p->lchild;
		}
		else
		{
			Pop(s,p);
			p=p->rchild;
		}//else
	}//while

}//PreOrderTraverseF

void PostOrderTraverseF(BiTree  t)
{
    SqStack s;
	InitStack(s);
	BiTree p;
	char e,tag;
	p=t;
	while (p || !stackEmpty(s))
	{
		if (p) { Push(s,p,'L');p=p->lchild; }
		else
		{	Pop(s,p,e); tag=e;
			if (tag=='R')
			{
				//cout<<setw(4)<<p->data;
				printf("%4c",p->data);
				p=NULL;
			}
			else
			{
				Push(s,p,'R');
				p=p->rchild;
			}
		} // else
	}  // end of while
}   // end of postOrderTraverse (bt)

void main()
{
BiTree r;
r=CreateBiTree();

cout<<"pre:"<<endl;
PreOrderTraverse(r);
cout<<endl;

cout<<"pre_f:"<<endl;
PreOrderTraverseF(r);
cout<<endl;

cout<<"in:"<<endl;
InOrderTraverse(r);
cout<<endl;

cout<<"in_f:"<<endl;
InOrderTraverseF(r);
cout<<endl;

cout<<"post:"<<endl;
PostOrderTraverse(r);
cout<<endl;

cout<<"post_f:"<<endl;
PostOrderTraverseF(r);
cout<<endl;

char t;
cin>>t;
}