网站建设得花多钱,设计网站的软件,制作php网站用什么软件,建筑网站ad数据结构之二叉树#xff1a;Python代码解决折纸问题
折纸问题
要求#xff1a;请把一段纸条竖着放在桌子上#xff0c;然后从纸条的下边向上方对折1次#xff0c;压出折痕后展开。此时折痕是凹下去的#xff0c;即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方…数据结构之二叉树Python代码解决折纸问题
折纸问题
要求请把一段纸条竖着放在桌子上然后从纸条的下边向上方对折1次压出折痕后展开。此时折痕是凹下去的即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次压出折痕后展开此时有三条折痕,从上到下依次是下折痕、下折痕和上折痕。 分析: 我们把对折后的纸张翻过来让粉色朝下这时把第-次对折产生的折痕看做是根结点那第二次对折产生的下折痕就是该结点的左子结点而第二次对折产生的上折痕就是该结点的右子结点这样我们就可以使用树型数据结构来描述对折后产生的折痕。这棵树有这样的特点:
根结点为下折痕;每一个结点的左子结点为下折痕;每一个结点的右子结点为 上折痕;
画成树会是这样 实现步骤:
1.定义结点类2.构建深度为N的折痕树;3.使用中序遍历,打印出树中所有结点的内容;
构建深度为N的折痕树:
1.第一次对折,只有一条折痕,创建根结点;2.如果不是第一次对折,则使用队列保存根结点;3.循环遍历队列: 3.1从队列中拿出一个结点; 3.2如果这个结点的左子结点不为空,则把这个左子结点添加到队列中; 3.3如果这个结点的右子结点不为空,则把这个右子结点添加到队列中; 3.4判断当前结点的左子结点和右子结点都不为空,如果是,则需要为当前结点创建一个值为down的左子结点 , 一个值为up的右子结点。
方法介绍
create_paper_folding_tree()创建折纸树queue为辅助队列初始时存入根结点(整棵树)如果queue不为空则将树取出来判断其是否有左右子树如果有将左右子树分别再放入queue继续循环判断print_this_tree()使用中序遍历的方式打印结点的值
接下来使用代码实现并将结点的值中序遍历打印出来
代码实现
class Node:def __init__(self, item):self.item itemself.left Noneself.right Noneclass PaperFolding:def __init__(self):self.root Nonedef create_paper_folding_tree(self, number):Emulate the process of paper-folding and create a binary treefor n in range(number):# When the first folding, assign down to the root node.item and go on loopif n 0:self.root Node(down)continue# When not the first folding, level-orderly traverse from up to down,# and from left to right to create new leaves# Create a subsidiary list to traverse level-orderlyqueue [self.root]while queue:# Pop from the left(prior to the left sub-tree)node queue.pop(0)# Append nodes to queue(priority order: left-parent-right) and go on traversing in while loopif node.left:queue.append(node.left)if node.right:queue.append(node.right)if not node.left and not node.right: # Have come to the leaves# In paper-folding tree,# sub-tree on the left value will be down and sub-tree on the right will be upnode.left Node(down)node.right Node(up)return self.rootdef print_this_tree(self):Traverse mid-orderly and print all values of the tree nodesif not self.root:returndef print_values(node):if node.left:print_values(node.left)print(node.item, end ) # Mid-order, left -- root -- rightif node.right:print_values(node.right)print_values(self.root)代码测试
if __name__ __main__:PF PaperFolding()PF.create_paper_folding_tree(3)PF.print_this_tree()测试结果
down down up down down up up 对比折纸树的层序遍历没有问题
