二叉树-范例

2021年1月25日发(作者：法务部)

范例：二叉树基本操作


摘要
：
树型结构是一 类重要的非线性数据结构。其中以树和二叉树最为常用，直观看
来，
树是以分支关系定义的层次 结构。
树结构在客观世界广泛存在，
如人类社会的族谱
和各种社会组织都可用树来表示 。
树在计算机领域中也得到广泛应用，
如在编译程序中，
可用树来表示源程序的语法结 构。因此，本课程设计将介绍二叉树基本操作。


关键词
：























数据结构

课程设计

二叉树










































1

































目



录


一

绪论

---------- -------------------------------------------------- ----------------------------- 5

二

需求分析

--------------------------------- -------------------------------------------------- - 5

三

概要设计

-------------- -------------------------------------------------- -------------------- 5

四

详细设计

---------------------------------------------- -------------------------------------- 7

五

源程序

------------------------ -------------------------------------------------- ------------ 12

六

程序运行结果

-------------------------------------------------- --------------------------- 18

七

总结

----------------------------------- -------------------------------------------------- ---- 19

参考文献

-------------------- -------------------------------------------------- ----------------- 19











2

一、绪论

本系统采用
Visual C
语言编写
,
运用软件工程的思想
,
采用面向对象分析、设计的< br>方法学完成。
通过建立系统的对象模型、
功能模型，
设计界面窗口，
算 法结构，
函数之
间互相调用完成实现二叉树基本操作系统的功能。熟悉并巩固数据结构的基本概 念知
识，
培养学生自主学习，
独立思考的能力，
学会查找资料并善于分析资料 的能力，
培养
学生独立设计，独立调试程序的能力。


二、需求分析

建立二叉树，并对树进行操作。


基本功能要求：

1
、利用完全二叉树的性质建立一棵二叉树。
（层 数不小于
4
层）
。

2
、统计树叶子结点的个数。

3
、求二叉树的深度。


4
、能够输出用两种或两种以上的方法对二叉树进行遍历的遍历序列。


三、概要设计


本程序采用了各种同的方法对同一个输入进行排序，且每一 个元素其本身亦是一
个结构体，
又可以进行扩充，
使其可以存储其他的相关的信息。< br>通过二叉树的建立来实
现二叉树各种遍历、叶子结点的个数、二叉树的深度。

由题目要求，画出程序流程图如下：









3























bintree t






















char ch






按前序输入字符串
=>ch
T
t=NULL
case 0
case 1

前序

遍历

case 2

中序

遍历

case 3

后序

遍历

case 4

叶子

结点

数目

exit

T

t=' '

















F
t->data (
遍历根结点
)
t->lchild (
左子树递归
)
t->rchild (
右子树递归
)
t=' '

















F
t->lchild (
左子树递归
)
t->data (
遍历根结点
)
t->rchild (
递归
)
t=' '

















F
t->lchild (
左子树递归

t->rchild (
右子树递归
)
t->data (
遍历根结点
)
ch=' '




















F
遍历二叉树建立











int

choice














输入选择
(0-5)=>choice


T

T

int front=0 , rear=0 , num=0



bintree p=t




bintree queue[maxsize]










p!=NULL



queue [++rear]=p





front


p=queue[++front]
case 5

二叉

树的

深度

queue[++rear]=
p->lchild
p->rchild==NULL
queue[++rear]=
p->rchild
int front=0 , rear=0 , depth=0 , level=0

bintree p=t ; bintree queue[maxsize]
p->lchild==NULL&&
p->rchild==NULL
p->lchild!=NULL
num++










p!=NULL



queue [++rear]=p

level=rear





front


p=queue[++front]
if (p->lchild!=NULL)
if (p->rchild!=NULL)
if (front==level)
queue[++rear]=
p->lchild
queue[++rear]=
p->rchild
depth++;
level=rear;

4

四、详细设计

对部分头文件和函数的说明
：

#include

#include

#define MAXSIZE 100

/*
定义队列最大值
*/

#define NULL 0


/*
定义
NULL
为空
*/

typedef struct bitnode

/*
结点结构类型
*/

{
char data;

struct bitnode *lchild,*rchild;

}bintnode,*bintree;



核心程序算法
：

/*
根据先序建立二叉树
*/

bintree createbitree()
{
bintree t;
char ch;
scanf(
if(ch= =' ') t=NULL;
else
{


t=(bintnode *)malloc(sizeof(bintnode));


t->data=ch;


t->lchild=createbitree();


t->rchild=createbitree();
}
return(t);

5

}
基本思想：

通过键盘输入一串字符 串存放
&ch
中，当
ch
中字符不为空时，建立二叉树。首先
t指
针指向第一字符为根结点，
然后指向左结点，
逐次递归遍历根结点—
>
左结点—
>
右结点。
其中

' '
代表空结点。

建树时比如：














a












/












b



e









/



/








c


d

() ()






/


/





() () () ()
在输入时得输
abc()()d()()e()()
括号是空格



/*
前序遍历
*/

void preorder(bintree t)

{
if(t)
{
printf(
preorder(t->lchild);
preorder(t->rchild);
}
}
基本思想：

通过
bintree
createbitree()
已建立成一棵二叉树
bintree
t < br>，前序遍历就访问根结点—
>
左
结点—
>
右结点，逐次递归遍 历打印。




6

/*
中序遍历
*/

void midorder(bintree t)
{
if(t)
{


midorder(t->lchild);


printf(


midorder(t->rchild);
}
}
基本思想：

通过
bintree
createbitree()
已建立成一棵二叉树
bintree
t < br>，中序遍历就访问左结点—
>
根
结点—
>
右结点，逐次递归遍 历打印。



/*
后序遍历
*/

void lastorder(bintree t)

{
if(t)


{lastorder(t->lchild);



lastorder(t->rchild);



printf(



}
}
基本思想：

通过
bintree
createbitree()
已建立成一棵二叉树
bintree
t < br>，后序遍历就访问左结点—
>
右
结点—
>
根结点，逐次递归遍 历打印。





7

/*
求二叉树叶子结点数目
*/
int search_leaves(bintree t)
{
int num=0;
bintree queue[MAXSIZE];
bintree p=t;
int front=0,rear=0;
if (p!=NULL)
{
queue [++rear]=p;
while (front{
p=queue[++front];
if (p->lchild==NULL&&p->rchild==NULL)
num++;
if (p->lchild!=NULL)
queue[++rear]=p->lchild;
if (p->rchild!=NULL)
queue [++rear]=p->rchild;
}
}
return (num);
}
基本思想：

先定义整数型
front=0,
rear=0
,num=0
，< br>queue[MAXSIZE]
。通过遍历二叉树根结点不为
空，令为
p=qu eue
[1]
，通过
front条件判断，令
p=
queue
[1]
进行判断其结点所指
向的左右结点是否为空，若成立，则
num++
；然后判断
queue
[1]
结点所指向的左结点是否为空，
若不为空成立，
则令
queue [1]
结点所向的左结点为
p= queue [2]
；
再判断
queue
[1]
结点所指向的右结点是否为空，若不为空，则令
queue
[1]
结点所指向的右结点为
queue [4]
。
然后循环
if (p!=NULL)
，
那时
queue [5]=p
，
front=1
，
rear=4
。
while (front
8