二叉树的遍历及其在排序中的应用
时间:2019-08-08 18:23 来源:毕业论文 作者:毕业论文 点击:次
| 摘 要：树型结构在客观世界中广泛存在，包括树、森林、二叉树、完全二叉树和满二叉树等,其中以二叉树最为常用，排序是将一个没有顺序的序列，通过一些列的变换变成有序的序列.排序操作是计算机的一个非常重要的功能.本文首先通过对一棵二叉树应用传统方法.得到先序遍历,中序遍历,后序遍历并且分析三者之间的关系.提出了另一种更加简便的求取二叉树先序遍历填空法.求取中序遍历的投影法.探索二叉树三种遍历方式之间的内在联系间.同时根据三种遍历序列之间的内在联系.找到对应的唯一的二叉树.其次介绍中序遍历在二叉排序树的作用，最后介绍基于二叉树的树形选择排序和堆排序，并对两者进行比较. 38316 毕业论文关键词：树；二叉树；遍历；树形选择排序；堆排列 Binary Tree Traversal and its Application in Sequence Abstract：Tree structure widely exists in the objective world, including trees, forest and binary tree and complete binary tree and binary tree, of which the most binary tree commonly used, sorting is a sequence of one order, by a series of transformation into an orderly sequence. The sorting operation is one of the most important function of computer. This article first through the use of a binary tree. Traditional methods for sequence traversal, first in the sequence traversal, after the sequence traversal and analyze the relationship between the three. Put forward a more convenient to calculate the binary tree to fill in the blanks sequence traversal method. Calculating the projection sequence traversal. Explore the three kinds of binary tree traversal methods between the inner link between. At the same time, according to inner link between the three kinds of traversal sequence. To find the corresponding only binary tree. Secondly introduces sequence traversal in the role of the binary sort tree, finally introduced the tree based on binary tree selection sort and heap sort, and carries on the comparison to both. Keywords: Tree; Binary tree; Traverse; The tree selection; Pile arrangement 目 录 摘 要 1 引言 2 1.预备知识 3 1.1 树的定义 3 1.2 树的基本性质 3 1.3 二叉树的定义 4 1.4 二叉树的性质 4 1.5 树和二叉树的区别 4 2.二叉树的遍历问题 5 2.1 二叉树的遍历 5 2.2根据遍历生成二叉树 8 3.中序遍历在二叉排序树中的应用 10 3.1 二叉排序树的定义 10 3.2 二叉排序树的构造过程 10 3.3 中序遍历二叉排序树 10 4.树形选择排序（Tree Selection Sort） 11 4.1 树形选择排序提出的背景 11 4.2 树形选择排序定义 12 4.3树形选择排序基本思想 12 5.堆排列 13 5.1堆排列的定义 13 5.2 堆排序思想 14 5.3 树形选择排序和堆排序的比较 17 6. 结束语 17 参考文献 18 致谢 19 二叉树的遍历及其在排序中的应用 引言 树型结构在客观世界中广泛存在，包括树，森林，二叉树，完全二叉树和满二叉树等.其中以二叉树在我们生活中经常用到.直观上看来树是层次结构.树结构在人类生活中广泛应用.如公司人员机构和我们各自的家谱都可以用树来形象表示.树还在数据库系统中有重要作用.也可以用树来形象表示数据结构中程序的语法结构.本文重点讨论树的三种遍历方式，和每种遍历在排序中的应用. (责任编辑：qin) |