二叉树先序遍历非递归.cpp

共有10个文件代码

#include <iostream.h>
#include <malloc.h>
#define Maxsize 100
#define Maxwidth 40
typedef char elemtype;
typedef struct node
{
	elemtype data;
	struct node *left,*right;
}BTree;
void create(BTree * &b,char *str)
{
	BTree *stack[Maxsize],*p;
	int top=-1,k,j=0;  //top为栈指针，k指定是左还是右孩子，j为str指针
	char ch;
	b=NULL;
	ch=str[j];
	while(ch!='\0')
	{
		switch(ch)
		{
		case '(':top++;stack[top]=p;k=1;break;
		case ')':top--;break;
		case ',':k=2;break;
		default:p=(BTree *)malloc(sizeof(BTree));
			p->data=ch;p->left=p->right=NULL;
			if(b==NULL)
				b=p;
			else
			{
				switch(k)
				{
				case 1:stack[top]->left=p;break;
				case 2:stack[top]->right=p;break;
				}
			}
		}
		j++;
		ch=str[j];
	}
}
void printree(BTree *b)
{
	if(b!=NULL)
	{
		cout<<b->data;
		if(b->left!=NULL ||b->right!=NULL)
		{
			cout<<"(";
			printree(b->left);
			if(b->right!=NULL) 
				cout<<",";
			printree(b->right);
			cout<<")";
		}
	}
}
void porder(BTree *b)
{
	BTree *stack[Maxsize],*p;
	int top;
	if(b!=NULL)
	{
		top=1;
		stack[top]=b;
		while(top>0)
		{
			p=stack[top];
			top--;
			cout<<p->data<<"  ";
			if(p->right!=NULL)
			{
				top++;
				stack[top]=p->right;
			}
			if(p->left!=NULL)
			{
				top++;
				stack[top]=p->left;
			}
		}
	}
}
void main()
{
	BTree *b;
	create(b,"(a(b(c),d(e(,f),g)))");
	cout<<"嵌套表示法:";
	printree(b);
	cout<<endl<<"先序遍历:";
	porder(b);
	cout<<endl;
}