验证性实验四.docVIP

验证性实验四 二叉树的基本操作 实验课程名：数据结构 专业班级： 学号： 姓名： 实验时间： 实验地点： K4－207 指导教师： 一、实验目的 1、进一步掌握指针变量、动态变量的含义。 2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。 3、掌握用指针类型描述、访问和处理二叉树的运算。 二、实现内容 1、以二叉链表作存储结构，试编程实现前序、中序、后序及层次顺序遍历二叉树的算法。 #include iostream #include stdlib.h #include malloc.h using namespace std; #define STACK_INIT_SIZE 10 #define STACKINCREMENT 2 typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; }BiTNode; typedef struct { BiTNode *base; BiTNode *top; int stacksize; }Stack; typedef struct QNode { BiTNode data; struct QNode *next; }Queue; typedef struct { Queue *front; Queue *rear; }LinkQueue; int InitStack(Stack *s) { s-base=(BiTNode *)malloc(STACK_INIT_SIZE*sizeof(BiTNode)); if(!s-base) exit(0); s-top=s-base; s-stacksize=STACK_INIT_SIZE; return 1; } int Push(Stack *s,BiTNode e) { if(s-top-s-base=s-stacksize) { s-base=(BiTNode *)realloc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(TElemType)); if(!s-base) exit(0); s-top=s-base+s-stacksize; s-stacksize+=STACKINCREMENT; } *(s-top++)=e; return 1; } int Pop(Stack *s,BiTNode **e) { if(s-top==s-base) return 0; s-top--; *e=s-top; return 1; } BiTNode *CreateBiTree() { TElemType ch; BiTNode *T; cinch; if(ch==/) T=NULL; else { if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(0); T-data=ch; T-lchild=CreateBiTree(); T-rchild=CreateBiTree(); } return T; } int StackEmpty(Stack *s) { if(s-base==s-top) return 1; else return 0; } int InitQueue(LinkQueue *Q) { Q-front=Q-rear=(Queue *)malloc(sizeof(Queue)); if(!Q-front) exit(0); Q-front-next=NULL; return 1; } int EnQueue(LinkQueue *Q,BiTNode e) { Queue *p; p=(Queue *)malloc(sizeof(Queue)); if(!p) exit(0); p-data=e; p-next=NULL; Q-rear-next=p; Q-rear=p; return 1; } int DeQueue(LinkQueue *Q,BiTNode *e) { Queue *p; if(Q-fron