算法分析与设计PPT02-数据结构和STL - ZOJ1167.ppt

1、2.14 ZOJ1167-TREES ON THE LEVEL本题要求建立和遍历二叉树。本题要求建立和遍历二叉树。编写程序：给出一组二叉树，实现按层遍历每棵树。本题编写程序：给出一组二叉树，实现按层遍历每棵树。本题中二叉树的每个结点都是一个正整数，并且所有的二叉树中二叉树的每个结点都是一个正整数，并且所有的二叉树都不超过都不超过256个结点。个结点。按层遍历一棵树时，同一层上所有结点的数据从左到右输按层遍历一棵树时，同一层上所有结点的数据从左到右输出，第出，第k层的结点应该在第层的结点应该在第k+1层的结点之前输出。层的结点之前输出。1输入样例输入样例(11,LL)(7,LLL)(8,R)(5

2、,)(4,L)(13,RL)(2,LLR)(1,RRR)(4,RR)()(3,L)(4,R)()输出样例输出样例5 4 8 11 13 4 7 2 1not complete2.14 ZOJ1167-TREES ON THE LEVEL在本题中，二叉树是由一组数据对在本题中，二叉树是由一组数据对(n,s)来表示，其中来表示，其中n表示结点的值，表示结点的值，s是一个字符串，表示从根结点到达此结点的路径。是一个字符串，表示从根结点到达此结点的路径。路径由一组路径由一组R和和L表示，其中表示，其中L表示左分支，表示左分支，R表示右分支。在图中，值表示右分支。在图中，值为为13的结点表示为（的结点表

3、示为（13，RL），值为），值为2的结点表示为（的结点表示为（2，LLR），而），而根结点表示为（根结点表示为（5，），其中空字符串表示该结点是根。，），其中空字符串表示该结点是根。如果二叉树的每个结点，从根到结点的路径描述有而且只有一个，则认如果二叉树的每个结点，从根到结点的路径描述有而且只有一个，则认为该二叉树是完整的。为该二叉树是完整的。2输入样例输入样例(11,LL)(7,LLL)(8,R)(5,)(4,L)(13,RL)(2,LLR)(1,RRR)(4,RR)()(3,L)(4,R)()输出样例输出样例5 4 8 11 13 4 7 2 1not complete2.14 ZOJ11

4、67-TREES ON THE LEVEL二叉树是数据结构中的基础知识，其遍历方法有前树遍历，中树遍二叉树是数据结构中的基础知识，其遍历方法有前树遍历，中树遍历和后树遍历等。本题中的二叉树，是要我们自己构造的，然后再历和后树遍历等。本题中的二叉树，是要我们自己构造的，然后再按层遍历。由于构造二叉树的方法不同，编程的方法就各不相同，按层遍历。由于构造二叉树的方法不同，编程的方法就各不相同，在网站上能搜索到各种各样的代码。这里采用哈希（在网站上能搜索到各种各样的代码。这里采用哈希（Hash）映射的）映射的方法，将二叉树映射为一维数组。方法，将二叉树映射为一维数组。从图中看出，除叶子结点之外的任意结

5、点从图中看出，除叶子结点之外的任意结点p，其左孩子结点的编号是，其左孩子结点的编号是2p，右孩子结点的编号是，右孩子结点的编号是2p+1。在输入数据中，刚好给出了结点的。在输入数据中，刚好给出了结点的完整路径，当路径中有完整路径，当路径中有L时，就是左孩子结点；路径中有时，就是左孩子结点；路径中有R时，就是时，就是右孩子结点。右孩子结点。32.14 ZOJ1167-TREES ON THE LEVEL图中有一个明显的特征，其结点编号刚好是按层遍历的。因此，就图中有一个明显的特征，其结点编号刚好是按层遍历的。因此，就能够把完全二叉树映射到一维数组中。对一般的二叉树，有些结点能够把完全二叉树映射到

6、一维数组中。对一般的二叉树，有些结点是没有的。是没有的。对样例数据对样例数据1，二叉树映射为一维数组后，其值如，二叉树映射为一维数组后，其值如表所表所示示。二叉树输出时，只需遍历数组，输出非零元素的值二叉树输出时，只需遍历数组，输出非零元素的值。4结点编号结点编号（数组下标）（数组下标）123456789101112131415结点数据结点数据54811013472000001 调用该算法时，调用该算法时，complete的的初值初值为为1。int data;/结点数据结点数据int p;/结点结点编号编号5算法算法2.17 二叉树的构建和遍历二叉树的构建和遍历输入样例输入样例(11,LL)(7,LLL)(8,R)(5,)(4,L)(13,RL)(2,LLR)(1,RRR)(4,RR)()(3,L)(4,R)()输出样例输出样例5 4 8 11 13 4 7 2 1not complete