二叉树论文 二叉树的应用

《二叉树论文 二叉树的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、本科毕业论文（设计）模板2013年度本科实践论文实践题目：二叉树的应用学生姓名：杜鑫学号：1105290124专业：软件工程班级：软件工程1101完成日期：2013年08月25日-12-序言在计算机科学中，树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构。二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”（leftsubtree）和“右子树”（rightsubtree）。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是，二叉树不是树的特殊情形。在图论中，二叉树是一个连通的无环图，并且每一个顶点的度

2、不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点后，每个顶点定义了唯一的根结点，和最多2个子结点。数据结构中二叉树的应用有着很重要的作用，对解决很多程序问题都有很大帮助，因此，我们更应该深入的学习和了解二叉树的应用，为以后更方便的解决计算机的相关问题做铺垫。只有详细学习二叉树，了解二叉树的具体应用范围、方法以及针对性，才能很好地完成任务，解决问题。-12-内容摘要本实践论文主要包含以下几个方面：二叉树的定义，二叉树的特点，二叉树的存储结构，二叉树的排序、查找、插入、删除，平衡二叉树，二叉树的遍历，二叉树的相关应用等内容。由浅入深的介绍了二叉树的主要

3、内容和结构特性、操作实现，同时介绍了线索二叉树和哈夫曼树的基本情况。最后简短的引用两个二叉树应用的源程序例子来说明二叉树的具体使用。二叉树结构的应用非常广泛，特别是在大量数据处理方面，如在文件系统、编译系统、目录组织等方面显得更加突出。存储结构的不同，二叉树实现的操作也不同。其中，二叉树的遍历运算时一个重要的基础，对访问根结点操作的理解可包括多种操作。关键词：二叉树二叉树特性二叉树存储结构二叉树遍历、拓展哈夫曼树-12-目录一、二叉树的基本内容-4-（一）二叉树-4-（二）二叉树的存储结构-4-（三）二叉树的遍历-5-错误！未找到索引项。二、二叉树的应用-5

4、-（一）二叉排序树-5-（二）二叉排序树查找-6-（三）二叉排序树插入结点的算法-6-（四）二叉排序树删除结点的算法-6-（五）平衡二叉树-6-（六）判定树-7-（七）二分查找判定树的查找-7-（八）线索二叉树-7-一、哈夫曼树-10-（一）哈夫曼树的构造算法-10-参考文献-12--12-一、二叉树的基本内容（一）二叉树二叉树很像一株倒悬着的树，从树根到大分枝、小分枝、直到叶子把数据联系起来，这种数据结构就叫做树结构，简称树。树中每个分叉点称为结点，起始结点称为树根，任意两个结点间的连接关系称为树枝，结点下面不再有分枝称为树叶。结点的前趋结点称为该结点的"

5、双亲"，结点的后趋结点称为该结点的"子女"或"孩子"，同一结点的"子女"之间互称"兄弟"。二叉树也是递归定义的，其结点有左右子树之分：(1)完全二叉树——若设二叉树的高度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。(3)深度——二叉树的层数，就是高度。（二）二叉树的存储结构（1）顺序存储结构（适合完全二叉树和满二叉树）（2）链式存储结构（适合非完全二叉树）（三）二叉树的遍历（1）递归遍历

6、（中序遍历、先序遍历、后序遍历）（2）非递归遍历（利用堆栈实现）（四）二叉树的拓展（1）线索二叉树——（在节点空指针域存放前驱和后继节点的指针，加上线索标志域区分是线索指针还是child指针；建立线索二叉树，实质上就是遍历一颗二叉树，在相应的指针域进行操作）（2）二叉排序树——（可以了解到二叉树生成的过程）-12-（3）最优二叉树——（哈夫曼树）：对于一组有确定权值的叶子节点，构造的具有最小带权路径长度的二叉树（典型应用：哈夫曼编码）（4）平衡树——它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。（防止退化为链表，

7、提高搜索效率）（5）排序树——特点：所有结点“左小右大（6）字典树——由字符串构成的二叉排序树（7）判定树——特点：分支查找树（例如12个球如何只称3次便分出轻重）（8）带权树——特点：路径带权值（例如长度）二、二叉树的应用（一）二叉排序树或是一棵空树；或者是具有如下性质的非空二叉树： （1）若左子树不为空，左子树的所有结点的值均小于根的值； （2）若右子树不为空，右子树的所有结点均大于根的值； （3）它的左右子树也分别为二叉排序树。（二）二叉排序树查找在二叉排序树b中查找x的过程为：若b是空树，则搜索失败，否则：若x等于b的根节点的数据域之值，则查找成功；

8、否则：若x小于b的根节点的数据域之值，则搜索左子树；