binarytree.cpp

这个是编译原理课程的词法分析器

// 
// 二叉树的创建与遍历.
//

#include "stdlib.h"
#include "stdio.h"

/* 
 * 二叉树的定义，采用二叉链表作为存储结构
 * Binarynode表示结点，Binarytree表示二叉链表头指针
 */
typedef struct BinaryNode{
	char data;						//数据域
	struct BinaryNode *lchild;	//左指针域
	struct BinaryNode *rchild;	//右指针域
}BinaryNode,*BinaryTree;


/*
 * 出错时调用error,显示错误提示信息.
 */
void error(char *s){
  fprintf(stderr,"%s\n",s);
  exit(1);
}

/*
 * 根据输入的前序遍历串创建二叉链表,返回链表的头指针t.
 */
BinaryTree createTree(){
	BinaryTree bt;
	char ch;
	scanf("%c",&ch);	
	if(ch=='#') 
		bt=NULL;
	else{	
		bt=(BinaryNode *)malloc(sizeof(BinaryNode));
		if(!bt)
			error("malloc fail");
		bt->data=ch;
		bt->lchild=createTree();
		bt->rchild=createTree();
	}
	return bt;
}

/*
 * 中序遍历链表bt.
 */
void inOrderTraverse(BinaryTree bt){
	if(bt){	 
		inOrderTraverse(bt->lchild);
		printf("%c",bt->data);
		inOrderTraverse(bt->rchild);
	}
}

/*
 * 先序(前序)遍历链表bt.
 */
void preOrderTraverse(BinaryTree bt){
	if(bt){	 
		printf("%c",bt->data);
		preOrderTraverse(bt->lchild);
		preOrderTraverse(bt->rchild);
	}
}

/*
 * 后序遍历链表bt.
 */
void postOrderTraverse(BinaryTree bt){
	if(bt){	
		postOrderTraverse(bt->lchild);
		postOrderTraverse(bt->rchild);
		printf("%c",bt->data);
	}
}

/*
 * 释放链表占用的空间.
 */
void freeTree(BinaryTree bt){
	if(bt){   
		freeTree(bt->lchild);
		freeTree(bt->rchild);	
		free(bt);
	}
}

/*
 * 主程序.
 */
void main(){
	BinaryTree bt;
	printf("输入前序遍历串:");
	bt=createTree();
	printf("\n前序序列为:");
	preOrderTraverse(bt);
	printf("\n中序序列为:");
	inOrderTraverse(bt);
	printf("\n后序序列为:");
	postOrderTraverse(bt);
	printf("\n");
	freeTree(bt);  
}