实验4二叉树 -数据结构

数据结构课程实验报告

学生姓名学号

班级指导老师

实验名称实验4二叉树实验成绩

实验报告

实验目的：1、了解二叉树的顺序存储结构和链式存储结构。

2、了解二叉树的遍历.

实

验实验要求：(1)在主函数中，通过键盘输入建立设定的完全二叉树的顺序存储结构。

概(2)设计子函数，其功能为将顺序结构的二叉树转化为链式结构。

述(3)设计子函数，其功能为对给定二叉树进行中序遍历，显示遍历结果。

(4)通过实例判断算法和相应程序的正确性。

(5)掌握前序遍历二叉树的步骤，针对任意一棵二叉树能人工完成对二叉树的前序

遍历。

(6)能掌握栈的工作特点，并能正确应用这一特点实现对二叉树的遍历。

实验基本原理：一、设一棵完全二叉树用顺序存储方法存储于数组tree中，编写程

序：

(1)根据数组tree,建立与该二叉树对应的链式存储结构。

(2)对该二叉树采用中序遍历法显示遍历结果。

二、设一棵二叉树采用链式方式存储，编写一个前序遍历该二叉树的非递归算法。

实验设计思路、步骤和方法等：一、(1)顺序存储的二叉树转化为链式存储结构，

采用递归算法，递归函数的形式为Creab(tree,n,i,b),其中形参：tree为顺序存储二叉

实树的数组，n为二叉树的结点数，i是二叉树某结点在数组tree中的下标(初始值为

验1),b为要建立的链式存储二叉树结点指针、转化时，首先建立*b结点，将tree[ij

内的值赋给*b的数据域，再调用递归函数分别构造左子树和右子树。

容(2)中序遍历采用递归算法，即中序遍历左子树、访问根结点、中序遍历右子树。

二、(1)使用一个栈(指针数组)。首先将根结点(指针)入栈，然后逐次循环，

从栈中退出栈顶元素，作为当前要操作结点的指针(设为p),访问p的数据，然后

令其右结点(指针)入栈，再将其左结点(指针)入栈，直至栈空为止。

(2)前序遍历的次序为：根结点、左子树、右子树。

实验过程(实验中涉及的记录、数据、分析)：

一、程序代码如下：

/*实验3.1二叉树的顺序存储结构和链式存储结构*/

#include<stdio.h>

#include<stdlib.h>

#defineMaxSize20

/*二叉树链式存储结构结点定义*/

typedefstructBTreeNode

(

chardata;

structBTreeNode*left;

structBTreeNode*right;

}BTreeNode;

BTreeNode*Creab(char*tree,intnjnti,BTreeNode*b);/*建立二叉树链式结构*/

voidInorder(BTreeNode*BT);/*中序遍历二叉树*/

voidmain()

(

BTreeNode*BT;/*根结点指针*/

chartree[MaxSize],c;

intn=0;/*二叉树的结点数*/

inti=l;/*结点在数组tree中的下标*/

printf(”请输入完全二叉树的结点值(连续输入字符，以回车结束输入)：”)；

while((c=getchar())!-\n*)tree[++n]=c;

BT=(BTreeNode*)malloc(sizeof(BTreeNode));

BT=Creab(tree,n,i,BT);

printf(n\n中序遍历二叉树的输出序列为：”)；

Inorder(BT);

printf(n\nn);

)

/*将顺序结构的二叉树转化为链式结构*/

BTreeNode*Creab(char*tree,intnjnti,BTreeNode*b)

1

\

BTreeNode*p;

if(i<=n)

(

if(i==l)

p=b;当前结点为根结点*/

else

p=(BTreeNode*)malloc(sizeof(BTreeNode));

p->data=tree[i];

p->left=Creab(tree,n,2*i,p);/*递归构造左子树*/

p->right=Creab(tree,n,2*i+l,p)；/*递归构造右子树*/

)

else

p=NULL;/*叶子结点*/

returnp;

)

/*中序遍历二叉树*/

voidInorder(BTreeNode*BT)

I

i

if(BT!=NULL)

(

Inorder(BT->left);/*递归遍历左子树*/

printf("%c\BT->data);

Inorder(BT->right);/*递归遍历右子树*/

)

)

二、程序代码如下：

/*实验3.2二叉树的遍历*/

#include<stdio.h>

#include<stdlib.h>

#defineMaxSize20

/*二叉树链式存储结构结点定义*/

typedefstructBTreeNode

(

chardata;

structBTreeNode*left;

structBTreeNode*right;

[BTreeNode;

/*定义栈*/

typedefstruct

(

BTreeNode*data[MaxSize];

inttop;

)Stack;

BTreeNode*Creab(char*tree,intn,inti,BTreeNode*b);/*建立二叉树链式结构*/

voidPreorderN(BTreeNode*BT);/*前序非递归遍历二叉树*/

voidmain()

(

BTreeNode*BT;/*根结点指针*/

chartree[MaxSize],c;

intn=0;/*二叉树的结点数*/

inti=l;/*结点在数组tree中的下标*/

printf(”请输入完全二叉树的结点值(连续输入字符，以回车结束输入)：”)；

while((c=getchar())!=,\n')tree[++n]=c;

BT=(BTreeNode*)malloc(sizeof(BTreeNode));

BT=Creab(tree,n,i,BT);

printfC'\n前序遍历二叉树的输出序列为：”)；

PreorderN(BT);

printf(M\nH);

)

/*将顺序结构的二叉树转化为链式结构*/

BTreeNode*Creab(char*tree,intn,inti,BTreeNode*b)

(

BTreeNode*p;

if(i<=n)

(

if(i==l)

p=b;/*当前结点为根结点*/

else

p=(BTreeNode*)malloc(sizeof(BTreeNode));

p->data=tree[i];

p->left=Creab(lree,n,2*i,p);/*递归构造左子树*/

p->right=Creab(tree,n,2*i4-1,p);/*递归构造右子树*/

)

else

p=NULL;/*叶子结点*/

returnp;

}

/*前序非递归遍历二叉树*/

voidPreorderN(BTreeNode*BT)

(

if(BT!=NULL)

(

BTreeNode*p;

Stacks;

s.top=-l;

s.top++;

s.data[s.top]=BT;/*根结点进栈*/

while(s.top!=-1)

(

p=s.data[s.top];/*出栈*/

s.top";

printf(n%cM,p->data);/*访问根结点*/

if(p->right!=NULL)

(

s.top++;

s.data|s.top]=p・>right;/*右孩子进栈*/

)

if(p->left!=NULL)

{

s.top++;

s.data[s.top]=p->left;/*左孩子进栈*/

)

)

)

else

printf("此二叉树无效!\nn);

)

实验结果：一、

c\*C:\Docu>entsandSettings\AllUsers'桌面\sy3_l\Debug\sy3_l・exe”

请输入完整二叉箱前基点卷《逑续输入学将，以回车结束输入）：abcdefgh

中序遍历二叉树的输出序列为：hdbeafcS

Pressan9keytocontinue.

c<*C:\Docu>entsandSettings\AllUsers'桌面\sy3_l\Debug\sye*e"

请输不舞嘉曾"隹续输入字符，以回车结束输入）：abcdefghij

中序遍历二叉树的输出序列为：hdibjeafcg

Pressanykeytocontinue.

二、

c\*C:\DOCU1ESTSAIDSETTIIGS\ALLUSERS\^ffi\sy3_2\Debug\sy3_2.exe*

产输胭惠曾《最输人字符，遍睾赛欧L

,序遍历二叉树的输出序列为：abdhec£g

Pressanykeytocontinue

c<*C:\