数据结构-二叉树类型的实现资料.doc

实验4 表达式二叉树类型的实现 源代码及每步注解： 文件expression.h /*头文件以及存储结构*/ #includestdio.h #includeconio.h #includestdlib.h #includestring.h #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW 0 typedef int Status; /*二叉树结点类型*/ typedef enum{INT,CHAR}ElemTag;/*INT为整型数据num，CHAR为字符型数据c*/ typedef struct TElemType { ElemTag tag;/*{INT,CHAR}指示是整型还是字符型*/ union { int num;/*tag=INT时，为整型*/ char c;/*tag=CHAR时，为字符型*/ }; } TElemType; /*二叉树的二叉链表存储表示 */ typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; /* 左右孩子指针 */ }BiTNode,*BiTree; typedef BiTree SElemType;/*栈SqStack的元素*/ typedef char SElemType1; /*栈SqStack1的元素*/ /*栈的顺序存储表示 */ #define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */ #define STACKINCREMENT 2 /* 存储空间分配增量 */ /*两个顺序栈*/ typedef struct SqStack { SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */ SElemType *top; /* 栈顶指针 */ int stacksize; /* 当前已分配的存储空间，以元素为单位 */ }SqStack; /* 顺序栈 */ typedef struct SqStack1 { SElemType1 *base; /* 在栈构造之前和销毁之后，base的值为NULL */ SElemType1 *top; /* 栈顶指针 */ int stacksize; /* 当前已分配的存储空间，以元素为单位 */ }SqStack1; /* 顺序栈 */ /*顺序栈的基本操作*/ Status InitStack(SqStack *S) { /* 构造一个空栈S */ (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!(*S).base) exit(OVERFLOW); /* 存储分配失败 */ (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; return OK; } Status StackEmpty(SqStack S) { /* 若栈S为空栈，则返回TRUE，否则返回FALSE */ if(S.top==S.base) return TRUE; else return FALSE; } Status Push(SqStack *S,SElemType e) { /* 插入元素e为新的栈顶元素 */ if((*S).top-(*S).base=(*S).stacksize) /* 栈满，追加存储空间 */ { (*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!(*S).base) exit(OVERFLOW); /* 存储分配失败 */ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; } *((*S).top)++=e; return OK; } Status Pop(SqStack *S,SElemType *e) { /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ER