数据结构实验报告-树与二叉树.doc

《数据结构实验报告-树与二叉树.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、福建农林大学计算机与信息学院实验报告树与二叉树一、实验目的和要求1)进一步掌握指针变量、动态变量的含义。2)掌握二叉树的结构特性及各种存储结构的特点及适用范围。3)掌握用指针类型描述、访问和处理二叉树的运算。4)熟悉各种存储结构的特征及如何应用树结构解决具体问题。二、实验内容和原理实验内容：编写程序实现交换二叉树中所有结点的左右子树的算法。实验原理：【问题描述】建立一棵二叉树，按层次遍历该二叉树，并实现将二叉树中所有结点的左右子树交换，显示其结果。【基本要求】从键盘接受输入点（按层次遍历顺序），以“#”号结束，以二叉链表作为存储结构，将其二叉树

2、中所有结点的左右子树交换，并将结果输出。【实现】交换二叉树中所有结点的左右子树的具体步骤如下:将根结点进指针栈seqstack;当指针栈不空时，从栈顶取结点，如果此结点的左右孩子不为空，则把其左右孩子交换，然后再分别将其左右孩子进栈；反复执行步骤，直至指针栈为空时止。三、实验环境WindowsXP系统visualc++6.0四、算法描述及实验步骤#include"stdio.h"#include"stdlib.h"#defineMAXSIZE100typedefcharelemtype;typedefstructbtnode{elemtyped

3、ata;structbtnode*lchild,*rchild;}bitnode,*bitree;typedefstructnodd{bitreeaddr;intparent;}sequre;bitreeins_node(bitrees,bitreet);voidprint_tree(bitreet);bitreecreat_ordbt();sequreseq[MAXSIZE];voidswap(bitreetree);intn=0;voidmain(){bitreetree;tree=creat_ordbt();swap(tree);prin

4、tf("输出交换后的二叉树");print_tree(tree);}bitreecreat_ordbt(){bitreet,s;elemtypex;t=NULL;printf("请按层次输入结点1的值(以#号结束，0号为空的结点)：");scanf("%c",&x);getchar();while(x!='#'){n++;if(x!='0'){s=(bitree)malloc(sizeof(bitnode));s->data=x;s->lchild=NULL;s->rchild=NULL;seq[n].addr=s;t=ins_node(s

5、,t);}elseseq[n].addr=NULL;printf("请输入结点%d的值(以#号结束，0号为空的结点)：",n+1);x=getchar();getchar();}returnt;}bitreeins_node(bitrees,bitreet){intkk;if(n==1)t=s;else{kk=n/2;if(n%2==0)seq[kk].addr->lchild=s;elseseq[kk].addr->rchild=s;}returnt;}voidprint_tree(bitreet){inti,j,k,nn,start,hea

6、d,rear;sequreseqq[MAXSIZE];bitreep;if(t==NULL)return;head=0;nn=rear=0;seqq[rear].addr=t;for(;head<=rear&&nnlchild=NULL)seqq[++rear].addr=p->lchild;if(p->lchild!=NULL)seqq[++rear].addr=p->rchild;}for(head=0,j=0,k=1;head<=rear;){printf(

7、"第%d层数据:",j);for(i=0,start=head;headdata);if(seqq[head].addr->lchild==NULL)i=i-1;if(seqq[head].addr->rchild==NULL)i=i-1;}k=k*2+i;j++;}}voidswap(bitreeroot){inttop;bitreetemp,stack[MAXSIZE];if(root!=NULL){top=1;stack[top]=root;d

8、o{root=stack[top];top=top-1;if((root->lchild!=NULL)

9、

10、(root->rchild!=NULL)){