2023年数据结构与算法实验报告二叉树

沈阳工程学院

学生实验报告

（课程名称：数据结构与算法）

实验题目:__________二叉树______________

班级软本111学号姓名吴月芬

地点F座606指导教师姜柳祝世东

实验日期：2023年10月25日

一、实验目的

1.掌握二叉树的结构特性，以及各种存储结构的特点及合用范围。

2.掌握用指针类型描述、访问和解决二叉树的运算。

二、实验环境

TurboC或是Visua1C++

三、实验内容与规定

1.输入字符序列，建立二叉链表。

2.按先序、中序和后序遍历二叉树(递归算法)。

3.按某种形式输出整棵二叉树。

4.求二叉树的高度。

5.求二叉树的叶结点个数。

6.互换二叉树的左右子树。

7.借助队列实现二叉树的层次遍历。

8.在主函数中设计一个简朴的菜单，调试上述算法，规定1-3必做，4-7

为选做。

为了实现对二叉树的有关操作，一方面要在计算机中建立所需的二叉树。

建立二叉树有各种不同的方法。一种方法是运用二叉树的性质5来建立二叉

树，输入数据时需要将结点的序号(按满二叉树编号)和数据同时给出：(序号,

数据元素)。图4.1所示二叉树的输入数据顺序应当是：(l,a),(2,b),(3,

c),(4,d),(6,e),(7,f),(9,g),(13,h).

另一种算法是主教材中介绍的方法，这是一个递归方法，与先序遍历有点

相似。数据的组织是先序的顺序，但是另有特点，当某结点的某孩子为空时

以字符“#”来充当，也要输入。这时，图4.1所示二叉树的输入数据顺序应当

是:abd#g###ce#h##f##。若当前数据不为“#"，则申请一个结点存入当前

数据。递归调用建立函数，建立当前结点的左右子树。

四、实验过程及结果分析

(-)二叉树

1.二叉树的综合程序源代码如下所示：

#include<stdio.h>

#inc1ude<malloc.h>

#defineNULLO

structbitree

(

chardata;

structbitree*1child,*rchi1d;

};

structbitree*createbitree_l(structbitree*t)

(

intch;

oscanf("％d”,&ch);

if(ch==0)

0(

—NULL;

。}

eIse

0(

t->data=ch；

t->lchild=(structbitree*)malloc(sizeof(structb

itree));

。t->lchi1d=createbitree_l(t->lchi1d);

。t->rchild=(structbitree*)mal1oc(sizeof(structbitree));

t->rchild=createbitree_1(t->rchild);

)

returnt;

)

structbitree*createbitree_2(struetbitree*t)

(

intch;

oscanf(n%dH,&ch)；

»if(ch==0)

(

«t=NULL;

)

else

s(

st->lchild=(structbitree*)malloc(sizeof(structbitre

e));

ot->lchi1d=createbitree_2(t->lchild);

t->data=ch;

»t->rchild=(structbitree*)ma11oc(sizeof(structbitree));

t—>rchild=createbitree_2(t->rchild);

°}

returnt;

}

voidpreorder_1(structbitree*T)

(

if(T!=NULL)

{。

8printf("％d\t\tn,T—>data);

preorder_l(T—>lchiId);

preorder_l(T->rchild)；

)

)

voidpreorder_yezi(struetbitree*T)

(

if(T!=NULL)

(

。if(T->1chi1d=NULL&&T->rchild==NULL)〃只输出叶子节点

gprintf(H%d\t\t'\T->data);

preorder_1(T->1child);

preorder_l(T->rchild);

voidinorder_l(structbitree*H)

if(H)

(

inorder_1(H->lchi1d);

printf("%d\t\t",H->data)；

inorder_l(H->rchi1d);

)

voidpreorder_2(structbitree*p)

(

structbitree*s[100]；

inttop=-1;

while(p!=NULL||top!=-l)

。while(p!=NULL)

8tOP++；

8S[tOp]=p；

8printf("%d\t\tM,p->data);

p=p->lchild;

00}

°if(top!二一1)

6{

°p=s[top];

“op—；

8p=p->rchild;

voidpreorder_yezi_2(structbitree*p)

(

structbitree*s[100]；

。inttop=-l;

?whi1e(p!二NULL||top!=-1)

°t

^whi1e(p!=NULL)

(

00top++；

°s[top]=p;

»if(p->1child==NULL&&p->rchild==NULL)//只输出叶子

节点

printf("%d\t\t",p—>data);

p=p—>1child；

0)

<>if(top!=-l)

»P=SEtop];

°top--；

8P=p->rchild；

°)

)

)

voidinorder_2(structbitree*p)

(

structbitree*sL100]；

inttop-1;

<>while(p!=NULL||top!=-l)

{

8\vhile(p!=NULL)

bb{

84Op++；

8S[top]=p;

°p=p->lchi1d;

0)

-if(top!=-l)

。{

8p=s[top]；

8tOp—；

8Printf（"%d\t\t",p->data）;

^p=p->rchiId;

6）

°）

）

voidmenu_l（）

（

oprintf（"\n\t******菜单******

oprintf（"\t1.树的建立\n"）;

printf（"\t2.树的遍历\n"）；

printf（"\tO.退出\n"）;

}

voidmenu_2（intn）

（

»if（n==l）

（

aprintf（"\n\t******菜单*******\n"）；

。printf（"\n\tl.树的递归的先序建立\n"）;

。printf（"\n\t2.树的递归的中序建立\n"）;

Printf（"\n\t3.树的非递归的先序建立'n"）;

printf（"\n\t4.树的非递归的中序建立\n"）;

）

if（n==2）

»printf（"\n\t******菜单******

ooprintf（"\n\t1.树的递归的先序遍历\n"）;

»printf（"\n\t2.树的递归的中序遍历\n"）;

。叩rintf（"\n\t3.树的非递归的先序遍历\n"）;

8Printf（"\n\t4.树的非递归的中序遍历\n"）；

printf（"\n\t5.树的递归的先序遍历叶子节点\n"）;

。printf（"\n\t6.树的非递归的先序遍历叶子节点\n"）;

）

}

voidmain()

(

structbitree*H；

“ntn,m；

oH=(structbitree*)ma1loc(sizeof(structbitree))；

do

gmenu_1();

ooscanf("％d”,&n);

sif(n>2||n<0)

叩rintf(”\n\t\t您的输入有误!”)；

。elseif(n!=0)

o{menu_2(n)；scanf("％d",&m);}

gif(n==1)

oif(m==l)

H=createbitree_1(H);

。“f(m二二2)

0H二createbitree_2(H);

)

if(n==2)

°{

oif(m==1)

。epreorder_1(H);

qf(m=2)

einorder_l(H);

bif(m==3)

。preorder_2(H);

°bif(m==4)

inorder_2(H);

附>if(m==5)

。preorder_yezi(H);

。3if(m==6)

皿叩reorderyezi2(H);

6)

}whi1e(n!=O);

}

2.运营过程

二叉树递归的先序建立过程如图1.1所示。

菜

**注X

的

-M^-立

18

的

2历

^w

0

X共关*.关菜单MX.WMMX

1.树的递归的先序建立

2.树的递归的中序建立

3.树的非递归的先序建立

4.树的非递归的中序建立

1

1

2

0

0

3

0

0

图1.1先序建立二叉树

二叉树的递归的先序遍历如图1.2所示。

--D:\®5\SUgSt3\Debuq\t59a«)iS^®5.exe'

***菜*

的

1立

的

2历

0

******菜单*******

1.树的递归的先序遍历

2.树的递归的中序遍历

3.树的非递归的先序遍历

4.树的非递归的巾序遍历

5.树的递归的先序遍历叶子节点

6.树的非递归的先序遍历叶子节点

1

123

图1.2递归先序遍历

二叉树的递归的中序遍历如图1.3所示。

图1.3递归的中序遍历

二叉树的非递归的先序遍历如图1