-
范例:二叉树基本操作
摘要
:
树型结构是一 类重要的非线性数据结构。其中以树和二叉树最为常用,直观看
来,
树是以分支关系定义的层次 结构。
树结构在客观世界广泛存在,
如人类社会的族谱
和各种社会组织都可用树来表示 。
树在计算机领域中也得到广泛应用,
如在编译程序中,
可用树来表示源程序的语法结 构。因此,本课程设计将介绍二叉树基本操作。
关键词
:
数据结构
课程设计
二叉树
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
-
-
-
-
-
-
-
-
本文更新与2021-01-25 09:21,由作者提供,不代表本网站立场,转载请注明出处:https://www.bjmy2z.cn/gaokao/565066.html
-
上一篇:英语阅读理解与完形填空150篇答案
下一篇:离散数学词汇表