C语言编程二叉树

1、班级： 数学101软件 学号：5姓名： 田贵文实验组别： 实验日期： 报告日期： 成绩： 报告内容：（目的和要求、原理、步骤、数据、计算、小结等）实验名称：C语言编程二叉树一、实验目的及要求1.掌握二叉树的存储实现2.掌握二叉树的遍历思想3.掌握二叉树的常见算法的程序实现二、实验内容1.编写函数,输入字符序列,建立二叉树的二叉链表。2.编写函数,实现二叉树的中序递归遍历算法。(最好也能实现前缀和后缀遍历算法)3.编写函数,实现二叉树的中序非递归遍历算法。4.编写函数,借助队列实现二叉树的层次遍历算法。5.编写函数,求二叉树的高度。6.编写函数,求二叉树的结点个数。7.编写函数,求二叉树的叶子个

2、数。8.编写函数,交换二叉树每个结点的左子树和右子树。9.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法。三、实验结果四、实验总结通过此实验，我掌握了二叉树的存储实现，掌握了二叉树的遍历思想，掌握了二叉树的常见算法的程序实现。附录#include #include #define MAXSIZE 100typedef char DataType;typedef struct BiTNode/* 二叉链表存储结构 */DataType data; struct BiTNode *lchild,*rchild;BiTree;typedef BiTree* ElemType ;/*

3、栈中数据元素类型，栈中保存结点指针 */typedef struct ElemType dataMAXSIZE; int top;SeqStack;/* 栈的类型定义，顺序栈 */typedef structElemType queueMAXSIZE;int front,rear;SP;SeqStack *initSeqStack() /* 初始化栈 */ SeqStack *s; /* 首先建立栈空间，然后初始化栈顶指针 */ s=(SeqStack*)malloc(sizeof(SeqStack); s-top=-1; return s;int push(SeqStack *s,ElemT

4、ype x) if(s-top=MAXSIZE-1) /* 栈满不能入栈 */printf(栈满); return 0; s-top+; s-datas-top=x; return 1;void pop(SeqStack *s) /* 出栈，假设栈不空 */ s-top-; int empty(SeqStack *s) if(s-top=-1) return 1; else return 0; ElemType top(SeqStack *s) /* 设栈不空 */return (s-datas-top); /* 递归算法创建二叉链表 */BiTree *createBiTree()DataT

5、ype ch; BiTree *T; ch=getchar(); if(ch=0) return NULL; else T=(BiTree *)malloc(sizeof(BiTree); T-data=ch; T-lchild=createBiTree(); T-rchild=createBiTree(); return T; /* 中序遍历二叉树的递归算法 */void InOrder(BiTree *T) if(T) InOrder(T-lchild); printf(%c,T-data); InOrder(T-rchild); /* 前序遍历二叉树的递归算法 */void PreOrd

6、er(BiTree *T)if(T)printf(%c,T-data); PreOrder(T-lchild); PreOrder(T-rchild); /* 后序遍历二叉树的递归算法 */void PostOrder (BiTree *T)if(T) PostOrder(T-lchild); PostOrder(T-rchild); printf(%c,T-data); /* 中序遍历二叉树的非递归算法 */void InOrderFei(BiTree *p)SeqStack *s; s=initSeqStack(); while(1) while(p) push(s,p); p=p-lch

7、ild;/* 先将结点指针压栈，待出栈时再访问 */ if(empty(s) break; p=top(s); pop(s); printf(%c,p-data); p=p-rchild; /* 按层次遍历 */void LevelOrder(BiTree *T) SP *p; p=(SP*)malloc(sizeof(SP); p-front=0; p-rear=0; if(T!=NULL) p-queuep-front=T; p-front=p-front+1; while(p-front!=p-rear) T=p-queuep-rear; p-rear=p-rear+1; printf(

8、%c,T-data); if(T-lchild!=NULL) p-queuep-front=T-lchild;/*左孩子进队列*/ p-front=p-front+1; if(T-rchild!=NULL) p-queuep-front=T-rchild;/*右孩子进队列*/ p-front=p-front+1; /* 求二叉树的高度 */int height(BiTree *T)int i,j; if(!T) return 0; i=height(T-lchild);/* 求左子树的高度 */ j=height(T-rchild);/* 求右子树的高度 */ return ij?i+1:j+

9、1;/* 二叉树的高度为左右子树中较高的高度加1 */* 求二叉树的所有结点个数 */int Nodes(BiTree *T) int n1,n2; if(T=NULL) return 0; else if(T-lchild=NULL&T-rchild=NULL) return 1; else n1=Nodes(T-lchild); n2=Nodes(T-rchild); return n1+n2+1; /* 求二叉树的叶子结点个数 */int leafs(BiTree *T)int num1,num2; if(T=NULL) return 0; elseif(T-lchild=NULL&T-

10、rchild=NULL) return 1; num1=leafs(T-lchild);/* 求左子树中叶子结点数 */ num2=leafs(T-rchild);/* 求右子树中叶子结点数 */ return num1+num2; /* 交换二叉树的所有左右子树 */void exchange(BiTree *T) BiTree *temp=NULL; if(T-lchild=NULL&T-rchild=NULL) return; elsetemp=T-lchild; T-lchild=T-rchild; T-rchild=temp; if(T-lchild) exchange(T-lchi

11、ld); if(T-rchild) exchange(T-rchild);/* 交换后二叉树的遍历 */void Display(BiTree *T)printf(t交换后二叉树按中序遍历输出:);InOrder(T);printf(n); printf(t交换后二叉树按前序遍历输出:);PreOrder(T);printf(n); printf(t交换后二叉树按后序遍历输出:);PostOrder(T);printf(n);void menu() printf(n);printf(tt1.递归-创建二叉链表n);printf(tt2.递归-中序遍历二叉树n);printf(tt3.递归-前序

12、遍历二叉树n);printf(tt4.递归-后序遍历二叉树n);printf(tt5.非递归-中序遍历二叉树n);printf(tt6.层次-遍历二叉树n); printf(tt7.二叉树的高度n); printf(tt8.二叉树的结点个数n); printf(tt9.二叉树的叶子结点个数n);printf(tt10.交换二叉树的所有左右子树n);printf(tt0.退出系统n);printf(nt请选择:); void main() BiTree *bt; bt=NULL; int n,m=1;while(m) menu(); scanf(%d,&n); getchar();switch(

13、n) case 1:printf(nt请输入结点的前序序列创建二叉树:0表示空:); bt=createBiTree(); break;/* 生成二叉树 */ case 2:printf(nt递归-中序遍历二叉树:); InOrder(bt);printf(n); break;case 3:printf(nt递归-前序遍历二叉树:); PreOrder(bt); printf(n); break;case 4:printf(nt递归-后序遍历二叉树:); PostOrder(bt);printf(n); break;case 5:printf(nt非递归-中序遍历二叉树); InOrderFei(bt);printf(n); break;case 6:printf(nt按层次遍历二叉树:); LevelOrder(bt);printf(n); break;case 7:printf(nt二叉树的高度为:%dn,height(b