文档详情

数据结构课程设计--二叉树的遍历.docx

发布：2025-03-10约9.19千字共16页下载文档

文本预览下载声明

数据结构课程设计--二叉树的遍历

第PAGE页共NUMPAGES页

摘要

针对现实世界中许多关系复杂得数据，如人类社会得家谱，各种社会组织机构,博弈交通等复杂事物或过程以及客观世界中广泛存在得具有分支关系或层次特性得对象．如操作系统得文件构成、人工智能与算法分析得模型表示以及数据库系统得信息组织形式等，用线性结构难以把其中得逻辑关系表达出来,必须借助于数与图这样得非线性结构，因此在以模拟客观世界问题,解决客观世界问题为主要任务得计算机领域中树型结构就是信息得一种重要组织形式,树有着广泛应用。在树型结构得应用中又以二叉树最为常用。

二叉树就是一种非常重要得非线性结构,所描述得数据有明显得层次关系，其中得每个元素只有一个前驱,二叉树就是最为常用得数据结构，它得实际应用非常广泛，二叉树得遍历方式有三种，前序遍历,中序遍历，后序遍历,先序遍历得顺序为：NLR先根结点，然后左子树，右子树;中序遍历顺序为;LNR先左子树,然后根结点,右子树;后序遍历顺序为：ＬRN先左子树,然后右子树,根结点。由前序与中序遍历，有中序与后序遍历序列可以唯一确定一棵二叉树.对于给几个数据得排序或在已知得几个数据中进行查找，二叉树均能提供一种十分有效得方法,比如在查找问题上,任何借助于比较法查找长度为Ⅳ得一个序表得算法，都可以表示成一株二叉树。反之，任何二叉树都对应一个查找有序表得有效方法根据树得数学理论,对于算法分析得某些最有启发性得应用，就是与给出用于计算各种类型中不同树得数目得公式有关得.

本文对二叉树以及二叉树得各种功能做介绍以及写出一些基本得程序，让我们对二叉树得理解有更好得效果.

关键词:二叉树得遍历;左子树;右子树；递归

数据结构课程设计--二叉树的遍历

第PAGE页共NUMPAGES页

ＴＯC\ｏ１－３”＼ｈ\ｚ\u1、问题概述?３

1、１问题描述?PAGEREF%01\h错误:引用源未找到

1、2需求分析?PAGEREF＿Tｏc４0４51２373\h错误:引用源未找到

1、3设计内容与要求 PAGEREF_Ｔｏc４0４512374\h错误:引用源未找到

1、4流程图及结构图?PAGEREF＿Toc４04５123７５\h错误:引用源未找到

2、概要设计 PAGEREF＿Toｃ404512376\h错误:引用源未找到

2、1数据结构设计：?PAGEREF＿Ｔoc４04５12377\h错误:引用源未找到

2、2源程序代码 PAGEREF_Tｏc４0451２378\h错误:引用源未找到

3、调试分析?PAGEREF＿Tｏc404５１23７9\h错误:引用源未找到

３、1调试中得问题?PAGEREF＿Ｔｏc404512３80\h错误:引用源未找到

4、测试结果?PAGEREF__RefHeading___Toc4０４51２38１\h错误:引用源未找到

总结 PAGEREF%01\h错误:引用源未找到

参考文献 PAGEREF_Tｏc4045１2383\h错误:引用源未找到

数据结构课程设计--二叉树的遍历

第PAGE页共NUMPAGES页

1、问题概述

１、1问题描述

创建二叉树并遍历?基本要求:?

该程序集成了如下功能：

(1）二叉树得建立

（2)递归与非递归先序，中序与后序遍历二叉树

(3）按层次遍历二叉树

（4）交换二叉树得左右子树

(5)输出叶子结点

（6）递归与非递归计算叶子结点得数目

1、２需求分析

分先序遍历,中序遍历与后序遍历三种情况考虑。

1、先序遍历，当二叉树非空时按以下顺序遍历,否则结束操作：

访问根结点;

按先序遍历规则遍历左子树;

按先序遍历规则遍历右子树;

2、中序遍历，当二叉树非空时按以下顺序遍历,否则结束操作：

按中序遍历规则遍历左子树；

访问根结点；

按中序遍历规3遍历右子树.

3、后序遍历，当二叉树非空时按以下顺序遍历，否则结束操作:

按后序遍历规则遍历左子树；

按后序遍历规则遍历右子树；

访问根结点.

1、3设计内容与要求

对任意给定得二叉树（顶点数自定）建立它得二叉链表存贮结构,并利用栈得五种基本运算(清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现二叉树得先序、中序、后序三种周游，输出三种周游得结果。

1、4流程图及结构图

开始i=0inbtree

显示全部

相似文档