唯一确定树的算法设计与分析

唯一确定树的算法设计与分析(任务书,文献综述,论文11000字)
摘要
树是数据结构数据存储的一个重要类型。许多的实际应用都可以抽象成数的结构形式，因此树的结构定义、遍历、及其根据遍历序列构造对应树的算法都十分重要。
所谓树形结构的遍历，就是从根（root）结点开始，按照某种特定的规则，对每个结点有且仅有一次访问，直到整棵树所有的结点都被访问，才算是对一棵树完整的遍历。对一棵树的遍历，是树所有算法中的基础，也是对树的结构最直观的认识。
现有的一些树的遍历，以基础的前序遍历（根-左-右），中序遍历（左-根-右），后序遍历（左-右-根），层序遍历（逐层次）。同时建立在这些遍历算法基础上，可以基于两种遍历序列唯一确定对应的一棵树。
本文通过上述的基础四种遍历以外的遍历方法，和遍历序列对应结点的某种信息，来唯一确定并且构造对应的树。第一种方法是，基于LR-Stack遍历序列，和序列对应结点父结点信息的非递归算法；第二种方法是，基于深度优先遍历序列，和序列对应结点层数信息的非递归算法。第三种方法是，基于深度优先遍历序列，和序列对应结点度的信息的非递归算法。

关键词：数据结构；树；遍历序列；构造树；算法
 
Abstract
Tree plays an important role in the data structures.Many practical applications canbeconsidered to bethe form of data structures.So,the series of operations of a tree are all important.
The so-called traversal of the tree structure starts from the root node, and according to a specific rule，each node is only visited for one time until all nodes of the whole tree are visited. That is the complete traversal of the tree. The traversal of a tree is the basis of all tree algorithms.What’s more, it is also the most intuitive understanding of the tree structure.
The traversal of existing trees, preordertraversal (root-left-right), inorder traversal (left-root-right), postorder traversal (left-right-root),level traversal. At the same time, based on these traversal algorithms, it is possible to determine uniquely a corresponding tree based on two traversal sequences.
This article uniquely identifies and constructs the corresponding tree through the basic four traversal methods other than traversal, and by traversing some information of the corresponding nodes of the sequence. The first method is the non-recursive algorithm of using the LR-Stack traversal sequence, and the information of the parent node corresponding to the sequence.The second method is the non-recursive algorithm of using the Depth-First-Search traversal sequence, and the information of the floor number corresponding to the sequence.The third method is the non-recursive algorithm of using theDepth-First-Search traversal sequences, and the information of the degree of the corresponding node to the sequence.

Keywords:DataStructure;Tree;Traversal;Construct tree;Algorithm

目录
前言        1
第一章    绪论    2
1.1    树的基本定义    2
1.2    树的结构定义    3
1.3    树的遍历定义及算法    4
1.4    算法的描述    4
第二章    遍历算法设计基本描述    6
2.1    LR-stack遍历序列和父结点信息    6
2.2    DFS遍历序列和层次信息    7
2.3    DFS遍历序列和度数信息    8
第三章    构造树的算法的基本描述    9
3.1    根据父结点插入对应孩子结点算法描述    9
3.2    根据长兄结点插入对应次兄结点算法描述    9
3.3    由LR-stack遍历序列和父结点信息构造树算法描述    9
3.4    由DFS遍历序列和层次信息构造树算法描述    10
3.5    由DFS遍历序列和度数信息构造树算法描述    10
第四章    构造树的算法的基本证明    11
4.1    根据父结点插入孩子结点的算法证明    11
4.2    根据长兄结点插入次兄结点的算法证明    11
4.3    由LR-stack遍历序列和父结点信息构造树算法证明    11
4.4    由DFS遍历序列和层次信息构造树算法证明    12
4.5    由DFS遍历序列和度数信息构造树算法证明    12
第五章    算法设计的代码实现及结果    14
5.1    树形结点的代码实现    14
5.2    根据父结点插入孩子结点的算法代码实现    15
5.3    根据长兄结点插入次兄结点的算法代码实现    15
5.4    由LR-stack遍历序列和父结点信息构造树算法    16
5.4.1代码实现    16
5.4.2实验结果    17
5.5    由DFS遍历序列和层次信息构造树算法    18
5.5.1代码实现    18
5.5.2实验结果    19
5.6    由DFS遍历序列和度数信息构造树算法    20
5.6.1代码实现    20
5.6.2实验结果    21
第六章总结与展望    23
6.1    本文总结    23
6.2    后续工作展望    23
参考文献    24
致谢    26