数据结构二叉树实验报告源代码及运行文件

//#include"stdafx.h" #include<stdio.h> #include<malloc.h> #include <stdlib.h> #define OVERFLOW -2 #define MAX 100 #define maxsize 100 typedef struct bitnode { char data; struct bitnode *lch,*rch; }bitnode,*bitree; typedef struct queuenode { bitree ch[maxsize]; int front; int rear; }queuenode; int m=0; void creat(bitree &T) // 创建二叉树 { char ch; scanf("%c",&ch); if(ch=='*') T=NULL; else { T=(bitree)malloc(sizeof(bitnode)); if(T==NULL) exit(OVERFLOW); T->data=ch; creat(T->lch); creat(T->rch); } } void perorder (bitree T) //先序遍历 { if (T) { printf("%c ",T->data); perorder(T->lch); perorder(T->rch); } } void incorder(bitree T) //中序非递归遍历 { bitree p; int top; bitree s[MAX]; bool boolean; p=T; top=0; boolean=1; do { while(p) { if((p->rch==NULL&&p->lch!=NULL)||(p->rch!=NULL&&p->lch==NULL)) m++; s[top]=p; top++; p=p->lch; } if(top==0) boolean=0; else { top--; p=s[top]; printf("%c ",p->data); p=p->rch; } }while(boolean); } void postorder(bitree T) //后序遍历 { if(T) { postorder(T->lch); postorder (T->rch); printf("%c ",T->data); } } void initqueue(queuenode &q) //初始化一个带头结点的队列 { q.front=q.rear=0; } int enqueue(queuenode &q,bitree T) //入队列 { if((q.rear+1)%maxsize==q.front) { printf("队列满!!!\n"); return 0; } q.ch[q.rear]=T; q.rear=(q.rear+1)%maxsize; return 1; } void dequeue(queuenode &q,bitree &T) //出队列 { T=q.ch[q.front]; q.front=(q.front+1)%maxsize; char data; data=T->data; printf("%c ",data); } int queueempty(queuenode q) //判断队列是否为空 { if(q.front==q.rear) return 1; return 0; } void traverse(bitree T) //按层次遍历树中结点 { queuenode q; bitree p; initqueue(q); p=T; enqueue(q,p); while(queueempty(q)!=1) { dequeue(q,p); if(p->lch!=NULL) if(enqueue(q,p->lch)==0) return; if(p->rch!=NULL) if(enqueue(q,p->rch)==0) return; } printf("\n"); } int depth(bitree T) //求树深 { if(!T) return 0; int d1; d1= depth(T->lch); int d2; d2= depth(T->rch); return (d1>d2?d1:d2)+1; } void main() { char i; bitree A; printf("先序遍历算法建立二叉树，请输入节点值（空用用*表示）：\n"); creat(A); putchar('\n'); printf("先序遍历:"); perorder(A); putchar('\n'); printf("中序遍历:"); incorder(A); putchar('\n'); printf("后序遍历:"); postorder(A); putchar('\n'); printf("层次遍历:"); traverse(A); printf("\n度为1的节点个数为：m=%d\n",m); putchar('\n'); printf("树的深度为:%d\n\n",depth(A)); printf("是否再次进行二叉树操作(Y/N)?\n"); scanf("%s",&i); if(i=='Y') main(); }