traverse.cpp

C++的电子教程

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#define M 3
#define N 100

typedef struct node
{	char data;
	struct node *child[M];
}NODE;

//Alp_Tree用于创建树结构，参数s指向用嵌套括号表示的树的字符串 ,m为树的度
//图7.2中树的嵌套括号表示形式：A(B(E,F(L),G),C(H,I),D(J,K(M,N)))
NODE *Alp_Tree(char *s,int m)
{	
	NODE *stack[N],*p=NULL,*q;
	/* stack[]存放父结点，p指向当前结点,q指向父结点 */
	int i,k=0,top=0;

	char ch=s[0];            //取一个字符为当前处理字符

	while(ch!='\0')
	{	
		if(isalpha(ch))      //若当前字符为字母，((ch>='A' && ch<='Z') || (ch>='a' && ch<='z'))
		{	p=(NODE *)malloc(sizeof(NODE));
			p->data=ch;
			for(i=0;i<m;i++)
				p->child[i]=NULL;
		}
		else
			switch(ch)
			{	case '(':
					stack[top++]=p;//当前结点进栈
					/* A,B,F,C,D,K */
					break;
				case ',':
					q=stack[top-1];//取栈顶结点（不出栈）为父结点
					/* B,B,A,C,A,D,K */
					i=-1;
					while(q->child[++i]!=NULL);//找空的指针域
					q->child[i]=p;//当前结点作为孩子结点进行链接
					break;
				case ')':
					q=stack[--top];//取栈顶结点（出栈）为父结点
					/* F,B,C,K,D,A */
					i=-1;
					while(q->child[++i]!=NULL);//找空的指针域
					q->child[i]=p;//当前结点作为孩子结点进行链接
					p=q;//取父结点为当前结点
					break;
			}
		ch=s[++k];	/* 取下一个字符为当前处理字符 */
	}
	return p;/* 返回树根地址 */
}

/* PreRecur递归实现树的前序遍历：根结点-从左到右各子树 */
void PreRecur(NODE* T,int m)
{	int i;

	if(T==NULL) return;
	printf("[%c]",T->data); //输出根结点的值

	for(i=0;i<m;i++)        //前序遍历根结点的各子树
		PreRecur(T->child[i],m);
}

/* PreStack用堆栈实现树的前序遍历 */
void PreStack(NODE* T,int m)
{ 	
	NODE* s[N];
	int i,top;

	if(T==NULL) return;
	s[0]=T; top=1;      //根结点进栈，top指向栈顶空闲单元

	while(top>0)        //栈非空时
	{	T=s[--top];     //取出栈结点为当前处理结点
		printf("[%c]",T->data);  //输出当前结点的值
		for(i=m-1;i>=0;i--)      //对于当前结点从右到左各子树
			if(T->child[i]!=NULL)
				s[top++]=T->child[i];//子树根结点进栈
	}
}

/* LevOrder用队列实现树的层次遍历 */
void LevOrder(NODE* T,int m)
{	
	NODE* q[N];        //存放各个结点
	int head,tail,i; /* head指向队首结点，tail指向待进队结点 */

	if(T==NULL) return;
	q[0]=T;head=0;tail=1;//根结点进队

	while(head<tail)//队列非空时
	{	
		T=q[head++];//取出队首结点为当前处理结点
		printf("[%c]",T->data);//输出当前结点的值

		for(i=0;i<m;i++)//对于当前结点从左到右各子树
			if(T->child[i]!=NULL)
				q[tail++]=T->child[i];//子树根结点进队
	}
}


void main()
{	
	NODE *h;
	char s[]="A(B(E,F(L),G),C(H,I),D(J,K(M,N)))";
	int m=3;

	//printf("\n Input string : ");
	//gets(s);
	h=Alp_Tree(s,m);

	printf("\n 前序遍历结点顺序：");
	PreRecur(h,m);
	printf("\n");

	printf("\n 前序遍历结点顺序：");
	PreStack(h,m);
	printf("\n");

	printf("\n 层次遍历结点顺序：");
	LevOrder(h,m);
	printf("\n\n");
}