摘 要
Matlab是一种用于算法开发,数据可视化，数据分析以及数值计算的高级技术计算语言和交互式环境。MATLAB是当今最优秀的科技应用软件之一，利用MATLAB对层次分析法的判断、分析和计算过程进行处理后，为决策者提供方便友好的对话界面。只要决策者在MATLAB软件中输入自己的层次结构方案和两两对比的判断矩阵后能迅速得出相应的结果，为解决实际问题提供一个快捷的方法。从而提高人们的决策效率，同时也为科技工作者使用层次分析法提供一种新思路。本文是利用matlab的强大功能来构造最优二叉树。二叉树是一种非常重要以及常见的数据结构，不仅在计算机系统中运用广泛，而且在日常生活中也有一定的应用。本文概述了二叉树的数据结构以及使用matlab来模拟出二叉树的数据结构，从而来实现二叉树的插入，删除，查询等常用功能。
关键词：Matlab；二叉树；数据结构；
ABSTRACT
Matlab is used for algorithm development, data visualization, data analysis and
numerical calculation of the senior technical computing language and interactive environment. Matlab is the most outstanding application of science and technology, using MATLAB to determine the right level of analysis, analysis and computation processing, in order to provide decision makers with convenient user-friendly dialog interface. When the decision-makers in MATLAB software, enter their own hierarchy of the program and judgment matrix to determine quickly after the corresponding results obtained, in order to solve practical problems to provide a quick method. Thereby enhancing the efficiency of people's decision-making, but also for the scientific and technological workers to use AHP to provide a new idea.This article is using matlab to construct optimal binary tree. Binary Tree is a very important and common data structures, it is widely used in the computer system. This article outlines the binary tree data structure and the use of matlab to simulate a binary tree data structure, in order to achieve the binary tree insertion, deletion, query and other commonly used functions. Key words：Matlab；binary tree；data struction；
目 录
第一章 绪论 ............................................. 1
1.1概述 ......................................................... 1
第二章 树与二叉树 ....................................... 2
2.1树的定义与结构 ............................................... 2
2.1.1树的定义 .................................................. 2
2.1.2 树的结构 ................................................. 2
2.2二叉树的定义与性质 ........................................... 3
2.2.1二叉树的定义 .............................................. 3
2.2.2二叉树的性质 .............................................. 4
2.2.3两种特殊形式的二叉树 ...................................... 4
2.2.4二叉树的存储结构 .......................................... 5
2.2.5最优二叉树 ................................................ 6
2.2.6最优二叉树的构造 .......................................... 7
第三章 matlab的基本内容 ................................ 9
3.1 matlab7.0介绍 ............................................... 9
3.2 图形用户界面（GUI） .......................................... 9
第四章 基于matlab的最优二叉树构造 ..................... 11
4.1构造最优二叉树方法 .......................................... 11
4.2 用Matlab构造最优二叉树图形 ................................. 11
4.3 用Matlab构造最优二叉树算法 ................................. 18
结束语 .................................................. 22
致 谢 .................................................. 23 参考文献 ................................ 错误！未定义书签。
xxx20xx届本科生毕业设计（论文）
第一章 绪论
1.1概述
随着计算机的普及应用以及科技的发达，系统建模和仿真技术已经日益成为各领域，特别是理工科各专业进行科学探索，系统可行性研究和工程设计不可缺少的环节。数据结构是计算机存储、组织数据的方式，所以这几年对数据结构的研究变得非常重要，而二叉树树是数据结构常用的结构之一。
众多的工作表明，二叉树的应用范围十分广泛，其应用已涉及到金融建模和期权规划，应用于资本市场、公司金融、风险管理与金融机构等领域，可以预料，随着对二叉树理论的深入研究，它的应用范围必将进一步拓广。正因为如此，人们自然地要求了解和掌握二叉树的应用技巧。所以使用matlab构造二叉树可以方便研究人员研究数据结构。以前的构造处于书本和作图，没有软件辅助不便于广泛应用，而且具有内容繁多、概念抽象、设计复杂等特点，学生在学习时常常会感到枯燥，难以理解和掌握。而用软件的形式对数据结构进行构造有着界面可视性强，操作简单方便；便于数据修改，文件保存，使用效率高，实验内容丰富，结果直观易懂，便于分析；而且系统容易扩展新的实验项目。所以使用软件构造很有必要而且急为迫切。因而选择此课题作为我们的毕业设计。
Matlab在全世界内都很是流行，特别是在工程计算领域。近年来越来越多的国人也喜爱上了这一套软件。本文旨在基于分析法的基础上，在MATLAB中编制对二叉树的判断、分析和计算过程的程序，决策者只要输入层次结构方案和判断矩阵，就能迅速得出相应的结果，为决策者解决问题提供一种快速的、具有较强实用价值的方法。
第二章 树与二叉树
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
T1，T2，„„Tm称作根结点的子树（sub tree）。
树也就可以这样定义：树是有根结点和若干颗子树构成的。
树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。我们可以形式地给出树的递归定义如下:
单个结点是一棵树，树根就是该结点本身。
设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n
作为n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点，它们都是结点n的儿子结点。我们还称n1,n2,..,nk为结点n的子树。
空集合也是树，称为空树。空树中没有结点。
A
BE
KL CFGHM图2-1 树的结构图 DIJ
2.2二叉树的定义与性质
二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树 相互转换，这样就解决了树的 存储结构及其运算中存在的复杂性
2.2.1二叉树的定义
二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树不是树的特殊情况，它们是两个概念。
基本形态：
A
BAABBAC
图2-2 二叉树结构图
数据对象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,∈H，且存在Dl上的关系Hl∈H；若Dr≠φ，则Dr中存在唯一的元素Xr，∈H , 且存在Dr上的关系Hr∈H； H＝{,， Hl, Hr };
(4) (Dl, {Hl})是一棵符合本定义的二叉树,称为根的左子树
(Dr,{Hr})是一棵符合本定义的二叉树,称为根的右子树
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(1in)
2.2.3两种特殊形式的二叉树
满二叉树
定义：一棵深度为k且有2k-1个结点的二叉树称为满二叉树
特点：每一层上的结点数都是最大结点数 1
2
4
[***********]4621357
图2-3 满二叉树结构图
完全二叉树
定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树
特点：叶子结点只可能在层次最大的两层上出现对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或l+1 1
2
4
891051112
图2-4 完全二叉树结构图 136724536
2.2.4二叉树的存储结构
1、顺序存储结构
它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法：
#define max-tree-size 100
Typedef telemtype sqbitree[max-tree-size];
Sqbitree bt
从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的右单支树确需要2h-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！
例如
0 1 2 3 4 5 6 7 8 9 10 11 12
kl bt
abcdefghij图2-5 顺序存储结构图
顺序存储结构的特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树
2、链式存储结构
在计算机中，二叉树通常采用链式存储结构。
与线性链表类似，用于存储二叉树中各元素的存储结点也由两部分组成：数据域和指针域。但在二叉树中，由于每一个元素可以有两个后件(即两个子结点)，因此，用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域;另一个用于指向该结点的右子结点的存储地址，称为右指针域。 PARENT
LCHILD
二叉树的二叉链表存储表示
typedef struct BiTNode{
TElemType data;
struct BiTNode * lchild , * rchild ;
} BiTNode , * BiTree ;
特点：
指针直接表示关系，操作简单
增加指针域，浪费空间，特别是存在多个空指针域 RCHILD 图2-6 存储二叉树指针图
2.2.5最优二叉树
最优二叉树，也称哈夫曼（Haffman）树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。
在前面我们介绍过路径和结点的路径长度的概念，而二叉树的路径长度则是指由根结点到所有叶结点的路径长度之和。如果二叉树中的叶结点都具有一定的权值，则可将这一概念加以推广。设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度。
在给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树。例如，给出4个叶结点，设其权值分别为1，3，5，7，我们可以构造出形状不同的多个二叉树。这些形状不同的二叉树的带权路径长度将各不相同。图给出了其中5个不同形状的二叉树：
图2-7 五种带权路径二叉树
由此可见，由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同的带权路径长度，那么如何找到带权路径长度最小的二叉树（即哈夫曼树）呢？根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。
哈夫曼（Haffman）依据这一特点于1952年提出了一种方法，这种方法的基本思想是：
（1）由给定的n个权值{W1，W2，„，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F＝{T1，T2，„，Tn}；
（2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；
（3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中；
（4）重复（2）（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。
由于这种算法是哈夫曼最早提出的，所以将最优二叉树称为哈夫曼树。 图7.4给出了前面提到的叶结点权值集合为W＝{1，3，5，7}的哈夫曼树的构造过程。可以计算出其带权路径长度为29，由此可见，对于同一组给定叶结点所构造的哈夫曼树，树的形状可能不同，但带权路径长度值是相同的，一定是最小的。
2.2.6最优二叉树的构造
中的二叉树的“合并”，最终得到哈夫曼树。
从上述算法中可以看出，F实际上是森林，该算法的思想是不断地进行森林F
在构造哈夫曼树时，可以设置一个结构数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n－1个结点，所以数组HuffNode的大小设置为2n－1，数组元素的结构形式如下：
表2-1 哈夫曼树结构形式
其中，weight域保存结点的权值，lchild和rchild域分别保存该结点的左、右孩子结点在数组HuffNode中的序号，从而建立起结点之间的关系。为了判定一个结点是否已加入到要建立的哈夫曼树中，可通过parent域的值来确定。初始时parent的值为－1，当结点加入到树中时，该结点parent的值为其双亲结点在数组HuffNode中的序号，就不会是－1了。
构造哈夫曼树时，首先将由n个字符形成的n个叶结点存放到数组HuffNode的前n个分量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HuffNode数组中的前n个分量的后面。
第三章 matlab的基本内容
3.1 matlab7.0介绍
Matlab(MATrix LABoratory)语言是美国的Cleve Moler 博士构思并开发集命令翻译、科学计算于一身的一套交互式软件系统，是目前国际工程控制界应用最广、最流行的一种控制系统计算机辅助设计的软件工具，它集成了计算功能,符号运算,数据可视化等功能,具有功能强大、界面友好、配套工具箱完善等特点，其SIMULINK仿真环境及S函数的应用为我们提供了有效实用的设计方法，该软件先前的版本与Visual C++和Visual Basic等可视化编程软件相比功能较差,但是新版的MATLAB 7.0软件已经在这方面向这些软件靠近,其可视化编程能力有了很大程度的提高.该软件最突出的特点就是简洁的,开放式代码。提供了更为直观,符合人们思维习惯的代码,现简单介绍该软件的主要特点。
1) 语言简单，代码灵活，极其丰富的库函数资源。在程序设计中该软件对代码的书写形式没有很严格的限制，同时利用丰富的库函数简化了子程序的编写任务，利用极其丰富的库函数可以使程序开发避免繁杂的子程序编程任务避免了一些不必要的错误，提高了程序的可靠性。
2) 丰富灵活的运算符。Matlab提供了和C语言一样多的运算符，使用这些运算符可使程序短小、灵活。
3) 面向对象编程和结构化控制功能。尤其是新版的MATLAB7.0软件在可视化方面较以前版本有了很大程度的提高，使得界面编程更加自由，方便。
4) 程序设计自由度大。在新版的MATLAB7.0软件中，用户无须对矩阵进行预定义就可以使用，对数组和变量的应用也得到很大程度的扩展。
5) 程序可移植性好，基本上可以不作修改就可以在各种型号的计算机和操作系统上运用。
6) 分门别类的工具箱是该软件的又一大特点。核心工具箱和学科类的工具箱。这些工具箱都是该学科的高水平的专业人士所编，所以用户可以直接使用。提高了编程效率。
7) 开放的共享源代码。开放性的代码是该软件最受欢迎的另一大特点。所有的核心文件和工具箱文件都是可读可该的源代码。所以matlab语言被称为第四代编程语言[3]。
3.2 图形用户界面（GUI）
图形用户界面（GUI）是用户与计算机程序之间的交互方式，是用户与计算机进行信息交流的方式。计算机在屏幕显示图形和文本，若有扬声器还可
产生声音。用户通过输入设备，如：键盘、鼠标、跟踪球、绘制板或麦克风，与计算机通讯。用户界面设定了如何观看和如何感知计算机、操作系统或应用程序。通常，多是根据悦目的结构和用户界面功能的有效性来选择计算机或程序。图形用户界面或GUI是包含图形对象，如：窗口、图标、菜单和文本的用户界面。以某种方式选择或激活这些对象，通常引起动作或发生变化。最常见的激活方法是用鼠标或其它点击设备去控制屏幕上的鼠标指针的运动。按下鼠标按钮，标志着对象的选择或其它动作。
Matlab在demo命令中包含了GUI功能的极好例子。Matlab为表现其基本功能而设计的演示程序demo 是使用图形界面的最好范例。Matlab的用户，在指令窗中运行demo 打开那图形界面后，只要用鼠标进行选择和点击，就可浏览那丰富多彩的内容。如:
>> demo
研究该命令，以了解uimenu和uicontrol如何给MATLAB函数提供交互输入。
在运行了 demo 例子后，很可能会问“为什么要在 MATLAB 中建立一个GUI？”这是一个很好的问题，简单的回答是可能并不需要．使用MATLAB来分析数据，求解问题，绘制结果的绝大多数的人，并不会发现GUI 工具很有用。但另一方面，GUI可以在MATLAB中生成非常有效的工具和应用程序，或是建立演示工作的交互式界面。
对“句柄图形”的理解是设计和实现GUI的先决条件。
由图形命令生成的每一事物是一个图形对象。图形对象不仅包括uimenu和uicontrol对象，而且还包括图形、坐标轴和他们的子对象。让我们从另一个角度来看这一层次结构。计算机的屏幕本身是根结点，图形是根对象的子对象，坐标轴，uimenu ，uicontrol是图形的子对象。根可以包括多个图形，每个图形含有一组或多组坐标轴以及其子对象，每个图形也可以有一个或多个与坐标轴无关的 uimenu和uicontrol。虽然uicontrol对象无子对象结点，但他们确实具有多种类型。uimenu对象常将其它的uimenu对象作为其子对象。
第四章 基于matlab的最优二叉树构造
4.1构造最优二叉树方法
要构造哈夫曼树（即最优树），哈夫曼最早给出了一个带有一般规律的算法，俗称哈夫曼算法。现叙述如下：
① 根据给定的n个概率（或频率）构造一个集合
这n个值对应树T的n个结点，置in1。
② 在集合F中选择两个最小的值求和作为fi加入集合F中；在树T中构造一结点，使得该结点是两最小值对应结点的父结点。
③ 在集合F中删除两最小值，并置ii1。
④ 重复②和③，直到i2n1或集合F只有一个元素为止。这样形成的一棵树就是哈夫曼树（最优树）。 F{f1,f2,,fn}，同时
4.2 用Matlab构造最优二叉树图形
利用构造最有二叉树的仿真图形的Matlab程序如下：
function huff(str)
if ~exist('str','var') %var is a keyword defined by exist function %str=['aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbccccccccccccccccccdddddddddddddddddeeeeeeeeeeeeeeeffffffffffg'];
%str=['aaabbbbcccccccdddddddddd'];
str=['cccccccccccccccdddddddddddddddddeeeoooooeeeeeeeeeeeeffffffffaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbcccffg'];
%str=['ccaaabbbbbbcdddccccddddddd'];
end
n=length(str);
list=[];p=[];
% count characters
for i=1:n
k=find(list==str(i)); %"find" finds the offset of some character in the array
if(length(k)==0)
list=[list;str(i)];
p=[p;1];
else
p(k)=p(k)+1;
end
end
disp( 'character count (list):')
for i=1:length(p)
disp([list(i) ': ' num2str(p(i))]);
end
% p contains the numbers of the characters in str
% "list" is the characters, the sequence of the list is according to the % sequence of occurrence in "str"
tempp=p/sum(p);
%---------------------
% sort p
pp=-p; [pp t]=sort(pp); p=-pp; %pp是降序实际排序结果，t是pp中的某个元素在原来数组中的位置。
%[p t]=sort(p,'descend');实现按降序排列
l(1:length(list))=list(t);
disp( 'after sort:')
m=length(p);
for i=1:m
disp([l(i) ': ' num2str(p(i))]);
end
% make tree
len=length(t);
tr=zeros(len,1);%len行，1列的0
tr(t)=1:len; %tr是list按降序排列后的脚标
disp( 'start to build the haffman tree:')
p=p/sum(p); % p is a vector with the probability
listp=p;
disp('% tr is a pointer vector which means the relationship between p and list');
disp('% It is the leaf of huffman tree');
disp(tr');
disp('% p is a vector with the probability');
disp(p');
ltr=length(tr);% augment with the growing of the huffman tree
lp=length(p);% decrease with the growing of huffman tree
roolp=3;
while lp>1
%if(length(list)-lp+1
%subplot(roolp,roolp,length(list)-lp+1);
figure(length(list)-lp+1);
drawhufftree(tr,list,tempp);
%end
% merge p(lp) and p(lp-1);
p(lp-1)=p(lp-1)+p(lp);
p=p(1:lp-1);
% tr(ltr+1) is a new node of the huffman tree
% tr(find(tr==lp)) and tr(find(tr==lp-1)) is its two children ltr=length(tr);
tr(find(tr==lp))=ltr+1;
tr(find(tr==lp-1))=ltr+1;
tr(ltr+1)=lp-1;
tempp(ltr+1)=p(lp-1); % record the probability of this node % sort p again after merging;
pp=-p; [pp t]=sort(pp); p=-pp;
%[p,t]=sort(p,'descend');
lp=length(p);
% tempp(1:lp-1)=p(1:lp-1); % update the order of probability to display % update the pointer of tr then
temp=tr;
for j=1:lp
tr(find(temp==t(j)))=j;
end
%show the middle result
disp('tr:(huffman tree)');
disp(tr');
disp('tempp:(probability on the tree)');
disp(tempp');
disp('p:(probability)');
disp(p');
disp('t:(sort of p)');
disp(t');
end
tr(length(tr))=0; % the root of huffman tree %draw the result
figure(length(list)-lp+1);
drawhufftree(tr,list,tempp);
end
经过matlab的仿真可得到如下最优二叉树图形：
图4-1 最优二叉树仿真图（1）
图4-2 最优二叉树仿真图（2）
图4-3 最优二叉树仿真图（3）
图4-4 最优二叉树仿真图（4）
图4-5 最优二叉树最终生成图
4.3 用Matlab构造最优二叉树算法
在MATLAB中实现哈夫曼算法，可用一个5(2n1)的矩阵来表示哈夫曼树，该矩阵的含义如表6-3-3所示。
表4-1 最优二叉树算法结构表
下面给出哈夫曼树的生成算法： function htree = HuffmanTree(pro) %构造哈夫曼树 %pro为一概率向量
n=size(pro,2);%得到字符个数 tree=ones(6,2*n-1);%构造树数据结构 tree(1,:)=1:(2*n-1);%填充结点序号 tree(5,(n+1):end)=0;%设置结点是否在集合 tree(2,1:n)=pro;%设置概率
tree(6,1:end)=0;%记录查找的结点对顺序 for i=(n+1):(2*n-1);%循环控制
[l,r]=findminval(tree);%找到集合中两个最小的值的序号 tree(2,i)=tree(2,l)+tree(2,r);%得到父结点概率值 tree(5,i)=1;%设置新构造结点在集合中
tree(3,l)=i;tree(3,r)=i;%设置父结点序号 tree(4,l)=0;tree(4,r)=1;%设置左右标志 tree(5,l)=0;tree(5,r)=0;%设置不在集合中
tree(6,l)=i-n;tree(6,r)=i-n;%记录该次删除的结点对顺序 end
htree=tree;
function [l,r]=findminval(tree) s=find(tree(5,:)==1); if size(s,2)
error('Error input!'); end
firval=realmax;secval=realmax; for i=s;
if firval>tree(2,i) if secval>firval
second=first;secval=firval; end
first=i;firval=tree(2,i); elseif secval>tree(2,i) second=i;secval=tree(2,i); end
end
l=min([first,second]);r=max([first,second]); 该算法还显示了删除结点对的先后顺序。 如在MATLAB命令窗口输入以下指令： >> a=[5 29 7 8 14 23 3 11]; >> HuffmanTree(a)
将生成如下结果可以说明算法是可以实现相关功能的
图4-6 最优二叉树算法图
利用分析法，并结合被称为第四代计算机语言的MATLAB工具软件，来解决多目标、多准则的问题，大大缩减了决策者计算复杂矩阵的时间。目前很多领域都采用这种方法，如资本市场、公司金融、风险管理与金融机构等。由此可见，二叉树结合MATLAB时很有发展前景的。
感谢我的指导老师在我选题及写作论文期间的悉心指导，为我指点迷津，帮我开拓思路，精心点拨，热忱激励。四年的本科学习，导师渊博的专业知识，严谨的治学态度，诲人不倦的高尚师德，平易近人的人格魅力对我影响深远，将使我终身受益。
感谢班级同学们在我准备论文期间的关心和支持。
特别要感谢我的父母和亲人，他们的关爱和鼓励是我一生努力前进的巨大动力。
最后感谢论文评审委员会的专家和老师们百忙之中对本论文的认真指正!
参考文献
[1]张贤明.MATLAB语言及应用案例.南京：东南大学出版社，2003. [2]苏金平.matlab高级编程.北京：电子工业出版社，2006. [3]李强.matlab数据处理与应用.北京：国防工业出版社，2001. [4]杨高波.精通matlab7.0混合编程.北京：电子工业出版社，2005 [5]吴越.数据结构与算法.北京：机械工业出版社，2010. [6]朱全名.二叉树及其运用.北京：国防工业出版社，2008.
[7]唐国明，王国均.数据结构（C语言版）.北京：清华大学出版社,2005. [8]田鲁怀.数据结构.北京：电子工业出版社出版，2006
[9] Thomas H.Cormen ,Charles E.Leiserson ,Ronald L.Rivest ,Clifford Stein., 1992 [10] Michael Main. Data Structures and Other Objects Using Java. Addison-Wesley,2006 [11] Mohiuddin A. Khan. Structure Rehablitation and Repair. McGraw-Hill,2009
摘 要
Matlab是一种用于算法开发,数据可视化，数据分析以及数值计算的高级技术计算语言和交互式环境。MATLAB是当今最优秀的科技应用软件之一，利用MATLAB对层次分析法的判断、分析和计算过程进行处理后，为决策者提供方便友好的对话界面。只要决策者在MATLAB软件中输入自己的层次结构方案和两两对比的判断矩阵后能迅速得出相应的结果，为解决实际问题提供一个快捷的方法。从而提高人们的决策效率，同时也为科技工作者使用层次分析法提供一种新思路。本文是利用matlab的强大功能来构造最优二叉树。二叉树是一种非常重要以及常见的数据结构，不仅在计算机系统中运用广泛，而且在日常生活中也有一定的应用。本文概述了二叉树的数据结构以及使用matlab来模拟出二叉树的数据结构，从而来实现二叉树的插入，删除，查询等常用功能。
关键词：Matlab；二叉树；数据结构；
ABSTRACT
Matlab is used for algorithm development, data visualization, data analysis and
numerical calculation of the senior technical computing language and interactive environment. Matlab is the most outstanding application of science and technology, using MATLAB to determine the right level of analysis, analysis and computation processing, in order to provide decision makers with convenient user-friendly dialog interface. When the decision-makers in MATLAB software, enter their own hierarchy of the program and judgment matrix to determine quickly after the corresponding results obtained, in order to solve practical problems to provide a quick method. Thereby enhancing the efficiency of people's decision-making, but also for the scientific and technological workers to use AHP to provide a new idea.This article is using matlab to construct optimal binary tree. Binary Tree is a very important and common data structures, it is widely used in the computer system. This article outlines the binary tree data structure and the use of matlab to simulate a binary tree data structure, in order to achieve the binary tree insertion, deletion, query and other commonly used functions. Key words：Matlab；binary tree；data struction；
目 录
第一章 绪论 ............................................. 1
1.1概述 ......................................................... 1
第二章 树与二叉树 ....................................... 2
2.1树的定义与结构 ............................................... 2
2.1.1树的定义 .................................................. 2
2.1.2 树的结构 ................................................. 2
2.2二叉树的定义与性质 ........................................... 3
2.2.1二叉树的定义 .............................................. 3
2.2.2二叉树的性质 .............................................. 4
2.2.3两种特殊形式的二叉树 ...................................... 4
2.2.4二叉树的存储结构 .......................................... 5
2.2.5最优二叉树 ................................................ 6
2.2.6最优二叉树的构造 .......................................... 7
第三章 matlab的基本内容 ................................ 9
3.1 matlab7.0介绍 ............................................... 9
3.2 图形用户界面（GUI） .......................................... 9
第四章 基于matlab的最优二叉树构造 ..................... 11
4.1构造最优二叉树方法 .......................................... 11
4.2 用Matlab构造最优二叉树图形 ................................. 11
4.3 用Matlab构造最优二叉树算法 ................................. 18
结束语 .................................................. 22
致 谢 .................................................. 23 参考文献 ................................ 错误！未定义书签。
xxx20xx届本科生毕业设计（论文）
第一章 绪论
1.1概述
随着计算机的普及应用以及科技的发达，系统建模和仿真技术已经日益成为各领域，特别是理工科各专业进行科学探索，系统可行性研究和工程设计不可缺少的环节。数据结构是计算机存储、组织数据的方式，所以这几年对数据结构的研究变得非常重要，而二叉树树是数据结构常用的结构之一。
众多的工作表明，二叉树的应用范围十分广泛，其应用已涉及到金融建模和期权规划，应用于资本市场、公司金融、风险管理与金融机构等领域，可以预料，随着对二叉树理论的深入研究，它的应用范围必将进一步拓广。正因为如此，人们自然地要求了解和掌握二叉树的应用技巧。所以使用matlab构造二叉树可以方便研究人员研究数据结构。以前的构造处于书本和作图，没有软件辅助不便于广泛应用，而且具有内容繁多、概念抽象、设计复杂等特点，学生在学习时常常会感到枯燥，难以理解和掌握。而用软件的形式对数据结构进行构造有着界面可视性强，操作简单方便；便于数据修改，文件保存，使用效率高，实验内容丰富，结果直观易懂，便于分析；而且系统容易扩展新的实验项目。所以使用软件构造很有必要而且急为迫切。因而选择此课题作为我们的毕业设计。
Matlab在全世界内都很是流行，特别是在工程计算领域。近年来越来越多的国人也喜爱上了这一套软件。本文旨在基于分析法的基础上，在MATLAB中编制对二叉树的判断、分析和计算过程的程序，决策者只要输入层次结构方案和判断矩阵，就能迅速得出相应的结果，为决策者解决问题提供一种快速的、具有较强实用价值的方法。
第二章 树与二叉树
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
T1，T2，„„Tm称作根结点的子树（sub tree）。
树也就可以这样定义：树是有根结点和若干颗子树构成的。
树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。我们可以形式地给出树的递归定义如下:
单个结点是一棵树，树根就是该结点本身。
设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n
作为n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点，它们都是结点n的儿子结点。我们还称n1,n2,..,nk为结点n的子树。
空集合也是树，称为空树。空树中没有结点。
A
BE
KL CFGHM图2-1 树的结构图 DIJ
2.2二叉树的定义与性质
二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树 相互转换，这样就解决了树的 存储结构及其运算中存在的复杂性
2.2.1二叉树的定义
二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树不是树的特殊情况，它们是两个概念。
基本形态：
A
BAABBAC
图2-2 二叉树结构图
数据对象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,∈H，且存在Dl上的关系Hl∈H；若Dr≠φ，则Dr中存在唯一的元素Xr，∈H , 且存在Dr上的关系Hr∈H； H＝{,， Hl, Hr };
(4) (Dl, {Hl})是一棵符合本定义的二叉树,称为根的左子树
(Dr,{Hr})是一棵符合本定义的二叉树,称为根的右子树
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(1in)
2.2.3两种特殊形式的二叉树
满二叉树
定义：一棵深度为k且有2k-1个结点的二叉树称为满二叉树
特点：每一层上的结点数都是最大结点数 1
2
4
[***********]4621357
图2-3 满二叉树结构图
完全二叉树
定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树
特点：叶子结点只可能在层次最大的两层上出现对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或l+1 1
2
4
891051112
图2-4 完全二叉树结构图 136724536
2.2.4二叉树的存储结构
1、顺序存储结构
它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法：
#define max-tree-size 100
Typedef telemtype sqbitree[max-tree-size];
Sqbitree bt
从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为H且只有H个结点的右单支树确需要2h-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！
例如
0 1 2 3 4 5 6 7 8 9 10 11 12
kl bt
abcdefghij图2-5 顺序存储结构图
顺序存储结构的特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树
2、链式存储结构
在计算机中，二叉树通常采用链式存储结构。
与线性链表类似，用于存储二叉树中各元素的存储结点也由两部分组成：数据域和指针域。但在二叉树中，由于每一个元素可以有两个后件(即两个子结点)，因此，用于存储二叉树的存储结点的指针域有两个：一个用于指向该结点的左子结点的存储地址，称为左指针域;另一个用于指向该结点的右子结点的存储地址，称为右指针域。 PARENT
LCHILD
二叉树的二叉链表存储表示
typedef struct BiTNode{
TElemType data;
struct BiTNode * lchild , * rchild ;
} BiTNode , * BiTree ;
特点：
指针直接表示关系，操作简单
增加指针域，浪费空间，特别是存在多个空指针域 RCHILD 图2-6 存储二叉树指针图
2.2.5最优二叉树
最优二叉树，也称哈夫曼（Haffman）树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。
在前面我们介绍过路径和结点的路径长度的概念，而二叉树的路径长度则是指由根结点到所有叶结点的路径长度之和。如果二叉树中的叶结点都具有一定的权值，则可将这一概念加以推广。设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度。
在给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树。例如，给出4个叶结点，设其权值分别为1，3，5，7，我们可以构造出形状不同的多个二叉树。这些形状不同的二叉树的带权路径长度将各不相同。图给出了其中5个不同形状的二叉树：
图2-7 五种带权路径二叉树
由此可见，由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同的带权路径长度，那么如何找到带权路径长度最小的二叉树（即哈夫曼树）呢？根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。
哈夫曼（Haffman）依据这一特点于1952年提出了一种方法，这种方法的基本思想是：
（1）由给定的n个权值{W1，W2，„，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F＝{T1，T2，„，Tn}；
（2）在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；
（3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中；
（4）重复（2）（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。
由于这种算法是哈夫曼最早提出的，所以将最优二叉树称为哈夫曼树。 图7.4给出了前面提到的叶结点权值集合为W＝{1，3，5，7}的哈夫曼树的构造过程。可以计算出其带权路径长度为29，由此可见，对于同一组给定叶结点所构造的哈夫曼树，树的形状可能不同，但带权路径长度值是相同的，一定是最小的。
2.2.6最优二叉树的构造
中的二叉树的“合并”，最终得到哈夫曼树。
从上述算法中可以看出，F实际上是森林，该算法的思想是不断地进行森林F
在构造哈夫曼树时，可以设置一个结构数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n－1个结点，所以数组HuffNode的大小设置为2n－1，数组元素的结构形式如下：
表2-1 哈夫曼树结构形式
其中，weight域保存结点的权值，lchild和rchild域分别保存该结点的左、右孩子结点在数组HuffNode中的序号，从而建立起结点之间的关系。为了判定一个结点是否已加入到要建立的哈夫曼树中，可通过parent域的值来确定。初始时parent的值为－1，当结点加入到树中时，该结点parent的值为其双亲结点在数组HuffNode中的序号，就不会是－1了。
构造哈夫曼树时，首先将由n个字符形成的n个叶结点存放到数组HuffNode的前n个分量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HuffNode数组中的前n个分量的后面。
第三章 matlab的基本内容
3.1 matlab7.0介绍
Matlab(MATrix LABoratory)语言是美国的Cleve Moler 博士构思并开发集命令翻译、科学计算于一身的一套交互式软件系统，是目前国际工程控制界应用最广、最流行的一种控制系统计算机辅助设计的软件工具，它集成了计算功能,符号运算,数据可视化等功能,具有功能强大、界面友好、配套工具箱完善等特点，其SIMULINK仿真环境及S函数的应用为我们提供了有效实用的设计方法，该软件先前的版本与Visual C++和Visual Basic等可视化编程软件相比功能较差,但是新版的MATLAB 7.0软件已经在这方面向这些软件靠近,其可视化编程能力有了很大程度的提高.该软件最突出的特点就是简洁的,开放式代码。提供了更为直观,符合人们思维习惯的代码,现简单介绍该软件的主要特点。
1) 语言简单，代码灵活，极其丰富的库函数资源。在程序设计中该软件对代码的书写形式没有很严格的限制，同时利用丰富的库函数简化了子程序的编写任务，利用极其丰富的库函数可以使程序开发避免繁杂的子程序编程任务避免了一些不必要的错误，提高了程序的可靠性。
2) 丰富灵活的运算符。Matlab提供了和C语言一样多的运算符，使用这些运算符可使程序短小、灵活。
3) 面向对象编程和结构化控制功能。尤其是新版的MATLAB7.0软件在可视化方面较以前版本有了很大程度的提高，使得界面编程更加自由，方便。
4) 程序设计自由度大。在新版的MATLAB7.0软件中，用户无须对矩阵进行预定义就可以使用，对数组和变量的应用也得到很大程度的扩展。
5) 程序可移植性好，基本上可以不作修改就可以在各种型号的计算机和操作系统上运用。
6) 分门别类的工具箱是该软件的又一大特点。核心工具箱和学科类的工具箱。这些工具箱都是该学科的高水平的专业人士所编，所以用户可以直接使用。提高了编程效率。
7) 开放的共享源代码。开放性的代码是该软件最受欢迎的另一大特点。所有的核心文件和工具箱文件都是可读可该的源代码。所以matlab语言被称为第四代编程语言[3]。
3.2 图形用户界面（GUI）
图形用户界面（GUI）是用户与计算机程序之间的交互方式，是用户与计算机进行信息交流的方式。计算机在屏幕显示图形和文本，若有扬声器还可
产生声音。用户通过输入设备，如：键盘、鼠标、跟踪球、绘制板或麦克风，与计算机通讯。用户界面设定了如何观看和如何感知计算机、操作系统或应用程序。通常，多是根据悦目的结构和用户界面功能的有效性来选择计算机或程序。图形用户界面或GUI是包含图形对象，如：窗口、图标、菜单和文本的用户界面。以某种方式选择或激活这些对象，通常引起动作或发生变化。最常见的激活方法是用鼠标或其它点击设备去控制屏幕上的鼠标指针的运动。按下鼠标按钮，标志着对象的选择或其它动作。
Matlab在demo命令中包含了GUI功能的极好例子。Matlab为表现其基本功能而设计的演示程序demo 是使用图形界面的最好范例。Matlab的用户，在指令窗中运行demo 打开那图形界面后，只要用鼠标进行选择和点击，就可浏览那丰富多彩的内容。如:
>> demo
研究该命令，以了解uimenu和uicontrol如何给MATLAB函数提供交互输入。
在运行了 demo 例子后，很可能会问“为什么要在 MATLAB 中建立一个GUI？”这是一个很好的问题，简单的回答是可能并不需要．使用MATLAB来分析数据，求解问题，绘制结果的绝大多数的人，并不会发现GUI 工具很有用。但另一方面，GUI可以在MATLAB中生成非常有效的工具和应用程序，或是建立演示工作的交互式界面。
对“句柄图形”的理解是设计和实现GUI的先决条件。
由图形命令生成的每一事物是一个图形对象。图形对象不仅包括uimenu和uicontrol对象，而且还包括图形、坐标轴和他们的子对象。让我们从另一个角度来看这一层次结构。计算机的屏幕本身是根结点，图形是根对象的子对象，坐标轴，uimenu ，uicontrol是图形的子对象。根可以包括多个图形，每个图形含有一组或多组坐标轴以及其子对象，每个图形也可以有一个或多个与坐标轴无关的 uimenu和uicontrol。虽然uicontrol对象无子对象结点，但他们确实具有多种类型。uimenu对象常将其它的uimenu对象作为其子对象。
第四章 基于matlab的最优二叉树构造
4.1构造最优二叉树方法
要构造哈夫曼树（即最优树），哈夫曼最早给出了一个带有一般规律的算法，俗称哈夫曼算法。现叙述如下：
① 根据给定的n个概率（或频率）构造一个集合
这n个值对应树T的n个结点，置in1。
② 在集合F中选择两个最小的值求和作为fi加入集合F中；在树T中构造一结点，使得该结点是两最小值对应结点的父结点。
③ 在集合F中删除两最小值，并置ii1。
④ 重复②和③，直到i2n1或集合F只有一个元素为止。这样形成的一棵树就是哈夫曼树（最优树）。 F{f1,f2,,fn}，同时
4.2 用Matlab构造最优二叉树图形
利用构造最有二叉树的仿真图形的Matlab程序如下：
function huff(str)
if ~exist('str','var') %var is a keyword defined by exist function %str=['aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbccccccccccccccccccdddddddddddddddddeeeeeeeeeeeeeeeffffffffffg'];
%str=['aaabbbbcccccccdddddddddd'];
str=['cccccccccccccccdddddddddddddddddeeeoooooeeeeeeeeeeeeffffffffaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbcccffg'];
%str=['ccaaabbbbbbcdddccccddddddd'];
end
n=length(str);
list=[];p=[];
% count characters
for i=1:n
k=find(list==str(i)); %"find" finds the offset of some character in the array
if(length(k)==0)
list=[list;str(i)];
p=[p;1];
else
p(k)=p(k)+1;
end
end
disp( 'character count (list):')
for i=1:length(p)
disp([list(i) ': ' num2str(p(i))]);
end
% p contains the numbers of the characters in str
% "list" is the characters, the sequence of the list is according to the % sequence of occurrence in "str"
tempp=p/sum(p);
%---------------------
% sort p
pp=-p; [pp t]=sort(pp); p=-pp; %pp是降序实际排序结果，t是pp中的某个元素在原来数组中的位置。
%[p t]=sort(p,'descend');实现按降序排列
l(1:length(list))=list(t);
disp( 'after sort:')
m=length(p);
for i=1:m
disp([l(i) ': ' num2str(p(i))]);
end
% make tree
len=length(t);
tr=zeros(len,1);%len行，1列的0
tr(t)=1:len; %tr是list按降序排列后的脚标
disp( 'start to build the haffman tree:')
p=p/sum(p); % p is a vector with the probability
listp=p;
disp('% tr is a pointer vector which means the relationship between p and list');
disp('% It is the leaf of huffman tree');
disp(tr');
disp('% p is a vector with the probability');
disp(p');
ltr=length(tr);% augment with the growing of the huffman tree
lp=length(p);% decrease with the growing of huffman tree
roolp=3;
while lp>1
%if(length(list)-lp+1
%subplot(roolp,roolp,length(list)-lp+1);
figure(length(list)-lp+1);
drawhufftree(tr,list,tempp);
%end
% merge p(lp) and p(lp-1);
p(lp-1)=p(lp-1)+p(lp);
p=p(1:lp-1);
% tr(ltr+1) is a new node of the huffman tree
% tr(find(tr==lp)) and tr(find(tr==lp-1)) is its two children ltr=length(tr);
tr(find(tr==lp))=ltr+1;
tr(find(tr==lp-1))=ltr+1;
tr(ltr+1)=lp-1;
tempp(ltr+1)=p(lp-1); % record the probability of this node % sort p again after merging;
pp=-p; [pp t]=sort(pp); p=-pp;
%[p,t]=sort(p,'descend');
lp=length(p);
% tempp(1:lp-1)=p(1:lp-1); % update the order of probability to display % update the pointer of tr then
temp=tr;
for j=1:lp
tr(find(temp==t(j)))=j;
end
%show the middle result
disp('tr:(huffman tree)');
disp(tr');
disp('tempp:(probability on the tree)');
disp(tempp');
disp('p:(probability)');
disp(p');
disp('t:(sort of p)');
disp(t');
end
tr(length(tr))=0; % the root of huffman tree %draw the result
figure(length(list)-lp+1);
drawhufftree(tr,list,tempp);
end
经过matlab的仿真可得到如下最优二叉树图形：
图4-1 最优二叉树仿真图（1）
图4-2 最优二叉树仿真图（2）
图4-3 最优二叉树仿真图（3）
图4-4 最优二叉树仿真图（4）
图4-5 最优二叉树最终生成图
4.3 用Matlab构造最优二叉树算法
在MATLAB中实现哈夫曼算法，可用一个5(2n1)的矩阵来表示哈夫曼树，该矩阵的含义如表6-3-3所示。
表4-1 最优二叉树算法结构表
下面给出哈夫曼树的生成算法： function htree = HuffmanTree(pro) %构造哈夫曼树 %pro为一概率向量
n=size(pro,2);%得到字符个数 tree=ones(6,2*n-1);%构造树数据结构 tree(1,:)=1:(2*n-1);%填充结点序号 tree(5,(n+1):end)=0;%设置结点是否在集合 tree(2,1:n)=pro;%设置概率
tree(6,1:end)=0;%记录查找的结点对顺序 for i=(n+1):(2*n-1);%循环控制
[l,r]=findminval(tree);%找到集合中两个最小的值的序号 tree(2,i)=tree(2,l)+tree(2,r);%得到父结点概率值 tree(5,i)=1;%设置新构造结点在集合中
tree(3,l)=i;tree(3,r)=i;%设置父结点序号 tree(4,l)=0;tree(4,r)=1;%设置左右标志 tree(5,l)=0;tree(5,r)=0;%设置不在集合中
tree(6,l)=i-n;tree(6,r)=i-n;%记录该次删除的结点对顺序 end
htree=tree;
function [l,r]=findminval(tree) s=find(tree(5,:)==1); if size(s,2)
error('Error input!'); end
firval=realmax;secval=realmax; for i=s;
if firval>tree(2,i) if secval>firval
second=first;secval=firval; end
first=i;firval=tree(2,i); elseif secval>tree(2,i) second=i;secval=tree(2,i); end
end
l=min([first,second]);r=max([first,second]); 该算法还显示了删除结点对的先后顺序。 如在MATLAB命令窗口输入以下指令： >> a=[5 29 7 8 14 23 3 11]; >> HuffmanTree(a)
将生成如下结果可以说明算法是可以实现相关功能的
图4-6 最优二叉树算法图
利用分析法，并结合被称为第四代计算机语言的MATLAB工具软件，来解决多目标、多准则的问题，大大缩减了决策者计算复杂矩阵的时间。目前很多领域都采用这种方法，如资本市场、公司金融、风险管理与金融机构等。由此可见，二叉树结合MATLAB时很有发展前景的。
感谢我的指导老师在我选题及写作论文期间的悉心指导，为我指点迷津，帮我开拓思路，精心点拨，热忱激励。四年的本科学习，导师渊博的专业知识，严谨的治学态度，诲人不倦的高尚师德，平易近人的人格魅力对我影响深远，将使我终身受益。
感谢班级同学们在我准备论文期间的关心和支持。
特别要感谢我的父母和亲人，他们的关爱和鼓励是我一生努力前进的巨大动力。
最后感谢论文评审委员会的专家和老师们百忙之中对本论文的认真指正!
参考文献
[1]张贤明.MATLAB语言及应用案例.南京：东南大学出版社，2003. [2]苏金平.matlab高级编程.北京：电子工业出版社，2006. [3]李强.matlab数据处理与应用.北京：国防工业出版社，2001. [4]杨高波.精通matlab7.0混合编程.北京：电子工业出版社，2005 [5]吴越.数据结构与算法.北京：机械工业出版社，2010. [6]朱全名.二叉树及其运用.北京：国防工业出版社，2008.
[7]唐国明，王国均.数据结构（C语言版）.北京：清华大学出版社,2005. [8]田鲁怀.数据结构.北京：电子工业出版社出版，2006
[9] Thomas H.Cormen ,Charles E.Leiserson ,Ronald L.Rivest ,Clifford Stein., 1992 [10] Michael Main. Data Structures and Other Objects Using Java. Addison-Wesley,2006 [11] Mohiuddin A. Khan. Structure Rehablitation and Repair. McGraw-Hill,2009