C语言编程二叉树

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

2、叶子个数。编写函数,交换二叉树每个结点的左子树和右子树。编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算 法。三、实验结果二叉树的叶子结处平数交按二賈树的所有左右子树 0 道出亲统诘选择：2递归-中序遍历二爻树:CBEDAFG递归-创逮二爻链表递归-中存遍圧二賈樋递归-前序遍历二叉树递归-后游遍历二夏樋诈递归冲序遍历二叉树层次-遍历二夏树f乂恻tu同區二夏槌的貉点个数二夏树的叶子结点于数交拴二賈树的所有左右子树0道出隶统诘选择：3递归-前序遍历二變树:ABCDEFG.递归-创建二夏链表递归冲存遍圧二賈樋3 递归-前序遍历二叉树递归-后游遍历二夏樋辱递归-中序遍历二變树 层次-遍历二

3、夏税 二叉树的高度二夏树的结点亍数9.二夏树的叶子结点于数10 交勲二叉树的所有左右子树0 追出东或谙选择：4递归-后序遍历二夏树:CEDBGFA1.递归-创遂二賈链表2 递归-中序遍历二叉密递归-前序遍历二賈树递归-后游遍历二變養非递归-中序遍历二夏树E 层次-遍历二叉也 F.二夏树的高度E二叉树的结点亍数二夏树的叶子结点于数10 交按二叉树的所有左右子树0追出亲端诘选挥：5非递归-中序遍历二叉树CBEDAFG递归-创連.二夏捱表递归-中序遍历二叉轆递归-前序遍历二叉树递归-后荐遍历二叉翌务谨归-中序遍历二夏树E趕次-遍历二曼税二叉树的高度E二叉树的结点亍数U j l-l U3-D J-.

4、I SV%y.二夏树的叶子洁点个数交拱二夏槪的所有左右子树 0 .追.出亲.纟充谙选择：6按层次遍圧二賈树:ABFCDGE递归-创逮二叉链表递归冲存遍历二叉備递归-俞序遍历二夏树4递归-后序遍历二曼树5 玉谨归-中序遍历二變树E億次-遍历二叉樋了.二賈树的高度_1-J二賈树的结点亍数_1-J二叟树的叶子结点于数交拱二夏梃的所诲左右子树 0 .追出亲统诘选择拧二愛树的高度为:4.谨归-创建二賈链爻递归-中序遍历二愛树递归-前芋遍历二賈农4.说扫-后序筒5二叉树5.非递归冲序遍历二賈树E 层次-遍圧二叉树7 二叟树的高度二賈树的结点于数二叉餌的叶子结点于数交玄g二賈树的所有左右子树谙选择辿二叉树的

5、箱点数肯口1 递归-创送二叉捱表递归冲序遍历二夏機递归-前序遍历二夏树递归-后序遍历二愛極玉谨归-中序遍历二.叉树 .层次-遍历二叉树二愛树的高度二叉祐的结点于数二曼树的罚子洁虑个数10.交捡二賈梃的所有左右子树0 .追出亲统谙选择：9二叉树中叶子结点数为:31 .递归-创遼二夏链表递归-中存遍历二叉擁递归-前序遍历二叉树递归-后游遍历二叉树5.玉谨归-中序遍历二叉树 层次-遍历二夏樋 7.ry树的高度8 二叉树的结点亍数v - - I j n -u j i!i.二叉树的叶子结找亍数10 .交拱二夏树的所有左右子树 0 .追出亲统诘选择：10交换二叉树的所有左右子树交换后二變树按中序遍历输出:

6、GFADEBC 交换帝二叉树嗾前障遍历输出:AFGBDL-C 交换后二叉树按后序遍历输出:GFEDCBA递归-创建二叉链表谨归-中序遍历二夏树3 递归-前序遍历二愛树4递归-后序遍历二夏树5.班递归-中序遍圧二賈树 层次-遍历二叉極 了.二叉树的高度二叉轲的结点于数二叉树的叶子诰点平数10 交瑕二夏树的所有左右子树0 .追出萦蛻谙选择:0Press any key to continue四、实验总结通过此实验，我掌握了二叉树的存储实现，掌握了二叉树的遍历思想 掌握了二叉树的常见算法的程序实现。附录#include #include #define MAXSIZE 100typedef char

7、 DataType;typedef struct BiTNode /* 二叉链表存储结构 */ DataType data;struct BiTNode *lchild,*rchild;BiTree;typedef BiTree* ElemType ; /* 栈中数据元素类型，栈中保存结点指针 */typedef struct ElemType dataMAXSIZE;int top;SeqStack; /* 栈的类型定义，顺序栈 */typedef structElemType queueMAXSIZE;int front,rear;SP;SeqStack *initSeqStack() /

8、* 初始化栈 */ SeqStack *s; /* 首先建立栈空间，然后初始化栈顶指针 */ s=(SeqStack*)malloc(sizeof(SeqStack);s-top=-1;return s;int push(SeqStack *s,ElemType 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)

9、return 1；else return 0；ElemType top(SeqStack *s) /* 设栈不空 */ return (s-datas-top)；/* 递归算法创建二叉链表 */BiTree *createBiTree() DataType 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； /* 中序遍历二叉树的递归算法 *

10、/void InOrder(BiTree *T) if(T) InOrder(T-lchild)；printf(%c,T-data)；InOrder(T-rchild)；/* 前序遍历二叉树的递归算法 */void PreOrder(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-dat

11、a);/* 中序遍历二叉树的非递归算法 */void InOrderFei(BiTree *p) SeqStack *s; s=initSeqStack();while(1) while(p) push(s,p); p=p-lchild; /* 先将结点指针压栈，待出栈时再访问 */ 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;

12、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(%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

13、 *T) int i,j;if(!T) return 0; i=height(T-lchild);/* 求左子树的高度 */ j=height(T-rchild);/* 求右子树的高度 */return ij?i+1:j+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); retu

14、rn n1+n2+1; /* 求二叉树的叶子结点个数 */int leafs(BiTree *T) int num1,num2;if(T=NULL) return 0; elseif(T-lchild=NULL&T-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=

15、NULL&T-rchild=NULL) return; elsetemp=T-lchild;T-lchild=T-rchild; T-rchild=temp; if(T-lchild) exchange(T-lchild); if(T-rchild) exchange(T-rchild);/* 交换后二叉树的遍历 */void Display(BiTree *T)printf(t 交换后二叉树按中序遍历输出:);InOrder(T);printf(n); printf(t 交换后二叉树按前序遍历输出:);PreOrder(T);printf(n); printf(t 交换后二叉树按后序遍历输出

16、:);PostOrder(T);printf(n);void menu() printf(n);printf(tt1.递归-创建二叉链表n); printf(tt2.递归冲序遍历二叉树n);printf(tt3.递归-前序遍历二叉树n);printf(tt4.递归-后序遍历二叉树n);printf(tt5.非递归冲序遍历二叉树5); printf(tt6 .层次-遍历二叉树n);printf(tt7.二叉树的高度n);printf(tt8.二叉树的结点个数5);printf(tt9.二叉树的叶子结点个数5); printf(ttlO.交换二叉树的所有左右子树n);printf(tt0 .退出系

17、统5);printf(nt 请选择:”)；void main() BiTree *bt; bt=NULL;int n,m=l;while(m)menu(); scanf(%d,&n); getchar();switch(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 按层次遍历二叉树:)；LevelOr