二叉树的遍历及其在排序中的应用(2)
时间:2019-08-08 18:23 来源:毕业论文 作者:毕业论文 点击:次
二叉树是一个重要抽象数据类型.因为二叉树有比较简单的存储结构和算法，因此在现实生活中有许多抽象的数据结构大多数以二叉树的形式存在，并且二叉树可以由树通过转换生成，因此研究二叉树很重要. 文献[1]-[7]介绍在计算机中我们经常将一组“无序”的序列通过一些操作变成为“有序”的序列的操作.这种变化叫做排序.排序在我们日常生活中也经常见到，因此，学习和研究不同的排序方法是非常重要. 文献[8]-[10]介绍二叉树是一种非常重要的树型结构. 每个二叉树都有左子树和右子树之分.在二叉树中不存在度大于2的结点.二叉树的这个性质非常重要，这个特点经常被用来做排序操作. 本文首先介绍了树和二叉树的基本定义，并且分析了树与二叉树的区别.然后介绍了二叉树的三种遍历方法，并给出了算法实现，通过分析先序遍历和后序遍历，本文给出了另外一种更加快捷的先序遍历和中序遍历方法，填空法，和投影法.进而讨论了中序遍历在二叉排序树和树形选择排序中的作用.并由树形选择排序推出更加简单的堆排序. 1. 预备知识 1.1 树的定义 树(Tree):是具有m（m>=0)个结点的有限集.当一颗树不是空树时： (1)树的根（root）结点有且仅有一个； (2)当m>1时，则树的剩余结点可以构成m不相交的有限集合.这m个集合每个都可以表示成一棵树.生成的树被称为子树(Sub Tree). 这个定义成为树的递归定义,由于树的定义之中还用到了树的概念.对于树的结构定义还需要注意两点： (1)在一棵树中不可能存在2个或者2个以上的根结点，即树的根结点是唯一存在的. (2)m>0时，一棵树的子树个数是没有限制.但一棵树的所有子树之间是不能相互有连接的,.如下图所示由于都有相交的子树，故不构成树. (责任编辑：qin) |