实验四二叉树基本操作

1、合用文档实验四二叉树的基本操作一、实验目的1进一步掌握指针变量的含义。2掌握二叉树的构造特点，以及各种储藏构造的特点及使用范围。3掌握用指针种类描述、接见和办理二叉树的运算。二、实验要求1、设计二叉树的基本操作；2、写出相应程序；3、保存和打印出程序的运行结果，并结合程序进行解析。三、实验内容给出一个可进行二叉树基本操作的完满程序，拥有以下功能：1）依照输入字符序列，建立二叉树；2）用递归算法实现输出二叉树的前序、中序、后序遍历序列；3）求二叉树的高度。附加题:（有时间可连续完成下面内容）用非递归算法实现输出二叉树的前序、中序遍历序列；5）求二叉树的叶子个数；6）求度为1的结点的个数；算法：四

2、、程序代码建树，遍历，求树高#include#include#includetypedefstructNodechardata;structNode*lchild;structNode*rchild;Node,*Tree;voida(Tree&t)/构造二叉树charch;scanf(%c,&ch);if(ch=.).合用文档t=NULL;elset=(Tree)malloc(sizeof(Node);t-data=ch;a(t-lchild);a(t-rchild);return;voidb(Tree&t)/先序遍历if(t)printf(%c,t-data);b(t-lchild);b(t

3、-rchild);voidc(Tree&t)/中序遍历if(t)c(t-lchild);printf(%c,t-data);c(t-rchild);voidd(Tree&t)/后序遍历if(t)d(t-lchild);d(t-rchild);printf(%c,t-data);intmax(intx,inty)returnxy?x:y;inthigh(Tree&t)if(t=NULL)return0;else.合用文档returnmax(high(t-lchild),high(t-rchild)+1;intmain()Treet;printf(请输入二叉树：n);a(t);printf(n先序

4、遍历nn);b(t);printf(nn中序遍历nn);c(t);printf(nn后序遍历nn);d(t);printf(nn树高为：%d,high(t);非递归先序，中序遍历，求叶子节点的个数，求度为1的节点的个数#include#include#includetypedefstructNodechardata;structNode*lchild;structNode*rchild;Node,*Tree;voida(Tree&t)/构造二叉树charch;scanf(%c,&ch);if(ch=.)t=NULL;elset=(Tree)malloc(sizeof(Node);t-data=

5、ch;a(t-lchild);a(t-rchild);return;.合用文档voidb(Treet)Treestack20,p;inttop=-1;if(t!=NULL)top+;stacktop=t;while(top-1)p=stacktop;top-;printf(%c,p-data);if(p-rchild!=NULL)top+;stacktop=p-rchild;if(p-lchild!=NULL)top+;stacktop=p-lchild;printf(n);voidc(Treet)Treestack20,p;inttop=-1;if(t!=NULL)p=t;while(top

6、-1|p!=NULL)while(p!=NULL)top+;stacktop=p;p=p-lchild;.合用文档if(top-1)p=stacktop;top-;printf(%c,p-data);p=p-rchild;printf(n);voidd(Tree&t,int&n)if(t)if(!t-lchild&!t-rchild)n+;d(t-lchild,n);d(t-rchild,n);voide(Tree&t,int&n)if(t)if(!t-lchild&t-rchild)|(t-lchild&!t-rchild)n+;e(t-lchild,n);e(t-rchild,n);intmain()Treet;intn1=0,n2=0;printf(请输入二叉树：n);a(t);printf(先序非递归遍历：n);b(t);printf(中序非递归遍历：n);c(t);d(t,n1);p