xxx20xx届本科生毕业设计（论文）
第一章 绪论
1.1概述
随着计算机的普及应用以及科技的发达，系统建模和仿真技术已经日益成为各领域，特别是理工科各专业进行科学探索，系统可行性研究和工程设计不可缺少的环节。数据结构是计算机存储、组织数据的方式，所以这几年对数据结构的研究变得非常重要，而二叉树树是数据结构常用的结构之一。
众多的工作表明，二叉树的应用范围十分广泛，其应用已涉及到金融建模和期权规划，应用于资本市场、公司金融、风险管理与金融机构等领域，可以预料，随着对二叉树理论的深入研究，它的应用范围必将进一步拓广。正因为如此，人们自然地要求了解和掌握二叉树的应用技巧。所以使用matlab构造二叉树可以方便研究人员研究数据结构。以前的构造处于书本和作图，没有软件辅助不便于广泛应用，而且具有内容繁多、概念抽象、设计复杂等特点，学生在学习时常常会感到枯燥，难以理解和掌握。而用软件的形式对数据结构进行构造有着界面可视性强，操作简单方便；便于数据修改，文件保存，使用效率高，实验内容丰富，结果直观易懂，便于分析；而且系统容易扩展新的实验项目。所以使用软件构造很有必要而且急为迫切。因而选择此课题作为我们的毕业设计。
Matlab在全世界内都很是流行，特别是在工程计算领域。近年来越来越多的国人也喜爱上了这一套软件。本文旨在基于分析法的基础上，在MATLAB中编制对二叉树的判断、分析和计算过程的程序，决策者只要输入层次结构方案和判断矩阵，就能迅速得出相应的结果，为决策者解决问题提供一种快速的、具有较强实用价值的方法。
1
xxxx20xx届本科生毕业设计（论文）
第二章 树与二叉树
2.1树的定义与结构
树是一类重要的非线性数据结构，是以分支关系定义的层次结构
2.1.1树的定义
树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。
树是一种简单的线性结构。在树这种数据结构中，所有数据元素之间的关系具有明显的层次特性。
2.1.2 树的结构
在树结构中，每一个结点只有一个前件，称为父结点。没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。
在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。
树（tree）是包含n（n>0）个结点的有穷集合K，且在K中定义了一个关系N，N满足 以下条件：
（1）有且仅有一个结点 k0，他对于关系N来说没有前驱，称K0为树的根结点。简称为根（root）。
（2）除K0外，k中的每个结点，对于关系N来说有且仅有一个前驱。 （3）K中各结点，对关系N来说可以有m个后继（m>=0）。
若n>1，除根结点之外的其余数据元素被分为m（m>0）个互不相交的结合T1，T2，……Tm，其中每一个集合Ti（1<=i<=m）本身也是一棵树。树
T1，T2，……Tm称作根结点的子树（sub tree）。
树也就可以这样定义：树是有根结点和若干颗子树构成的。
树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。我们可以形式地给出树的递归定义如下:
单个结点是一棵树，树根就是该结点本身。
设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n
2
xxxx20xx届本科生毕业设计（论文）
作为n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点，它们都是结点n的儿子结点。我们还称n1,n2,..,nk为结点n的子树。
空集合也是树，称为空树。空树中没有结点。
ABEKL
CFGHM图2-1 树的结构图
DIJ
2.2二叉树的定义与性质
二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树 相互转换，这样就解决了树的 存储结构及其运算中存在的复杂性
2.2.1二叉树的定义
二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树不是树的特殊情况，它们是两个概念。 基本形态：
?ABAABBAC
图2-2 二叉树结构图
3
xxxx20xx届本科生毕业设计（论文）
数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：
若D＝φ，则R＝φ，称BinaryTree为空二叉树； 若D≠φ，则R＝｛H｝，H是如下二元关系；
(1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) 若D-{root}≠φ,则存在D-{root}＝{Dl,Dr},且Dl∩Dr ＝φ； (3) 若Dl ≠φ，则Dl中存在唯一的元素Xl,
2.2.2二叉树的性质
性质1：在二叉树的第i层上至多有2i-1个结点(i≥1) 性质2：深度为k的二叉树至多有2k－1个结点（k>=1).
深度为k的二叉树的最大的结点时为二叉树中每层上的最大结点数之和 性质3： 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2 设二叉树中度为1的结点数为n1，二叉树中总结点数为N， 性质4：如果对一棵有n个结点的完全二叉树的结点按层序 编号，则对任一结点i(1?i?n)
2.2.3两种特殊形式的二叉树
满二叉树
定义：一棵深度为k且有2k-1个结点的二叉树称为满二叉树 特点：每一层上的结点数都是最大结点数
1248910511126131437154621357
图2-3 满二叉树结构图
完全二叉树
4
相关推荐：
loading