实验四二叉树的基本操作.doc

《实验四二叉树的基本操作.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验四二叉树的基本操作一、实验目的1．进一步掌握指针变量的含义。2．掌握二叉树的结构特征，以及各种存储结构的特点及使用围。3．掌握用指针类型描述、访问和处理二叉树的运算。二、实验要求1、设计二叉树的基本操作；2、写出相应程序；3、保存和打印出程序的运行结果，并结合程序进行分析。三、实验容给出一个可进行二叉树基本操作的完整程序，具有以下功能： （1）根据输入字符序列，建立二叉树； （2）用递归算法实现输出二叉树的前序、中序、后序遍历序列； （3）求二叉树的高度。附加题:（有时间可继续完成下面容）(4)用非递归算法实现输出二叉树的前序、中序遍历序列； （5）求二叉树的叶子

2、个数； （6）求度为1的结点的个数； 算法：四、程序代码建树，遍历，求树高#include#include#includetypedefstructNode{chardata;structNode*lchild;structNode*rchild;}Node,*Tree;voida(Tree&t){//构造二叉树charch;scanf("%c",&ch);if(ch=='.')t=NULL;else{t=(Tree)malloc(sizeof(Node));t->data=ch;a(t->lchild);a(

3、t->rchild);}return;}voidb(Tree&t){//先序遍历if(t){printf("%c",t->data);b(t->lchild);b(t->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){returnx>y?x:y;}inthigh(T

4、ree&t){if(t==NULL)return0;elsereturnmax(high(t->lchild),high(t->rchild))+1;}intmain(){Treet;printf("请输入二叉树：");a(t);printf("先序遍历");b(t);printf("中序遍历");c(t);printf("后序遍历");d(t);printf("树高为：%d",high(t));}非递归先序，中序遍历，求叶子节点的个数，求度为1的节点的个数#include#include

5、ring.h>#includetypedefstructNode{chardata;structNode*lchild;structNode*rchild;}Node,*Tree;voida(Tree&t){//构造二叉树charch;scanf("%c",&ch);if(ch=='.')t=NULL;else{t=(Tree)malloc(sizeof(Node));t->data=ch;a(t->lchild);a(t->rchild);}return;}voidb(Treet){Treestack[20],p;inttop=-1;if(t!=

6、NULL){top++;stack[top]=t;while(top>-1){p=stack[top];top--;printf("%c",p->data);if(p->rchild!=NULL){top++;stack[top]=p->rchild;}if(p->lchild!=NULL){top++;stack[top]=p->lchild;}}printf("");}}voidc(Treet){Treestack[20],p;inttop=-1;if(t!=NULL){p=t;while(top>-1

7、

8、p!=NULL){while(p!=NULL){top

9、++;stack[top]=p;p=p->lchild;}if(top>-1){p=stack[top];top--;printf("%c",p->data);p=p->rchild;}}printf("");}}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)

10、

11、(t->lchild&&!t->rchild))n++