如何用代码实现二叉树顺序存储,实现查找,求高度先,中,后,层次遍历
3条回答 默认 最新
- 个人练习生xx 2023-04-10 19:27关注
下面是二叉树顺序存储实现,包括查找,求高度,先序遍历,中序遍历,后序遍历和层次遍历的详细代码
class BinaryTree: def __init__(self, size): self.data = [None] * size self.size = size def get_parent_index(self, index): return (index - 1) // 2 if index > 0 else -1 def get_left_child_index(self, index): left_child_index = index * 2 + 1 return left_child_index if left_child_index < self.size else -1 def get_right_child_index(self, index): right_child_index = index * 2 + 2 return right_child_index if right_child_index < self.size else -1 def get_height(self): height = 0 level_size = 1 while level_size <= self.size: height += 1 level_size *= 2 return height - 1 def insert(self, value): if None not in self.data: return False self.data[self.data.index(None)] = value return True def find(self, value): for i in range(self.size): if self.data[i] == value: return i return -1 def pre_order_traversal(self, index): if index == -1: return print(self.data[index], end=" ") self.pre_order_traversal(self.get_left_child_index(index)) self.pre_order_traversal(self.get_right_child_index(index)) def in_order_traversal(self, index): if index == -1: return self.in_order_traversal(self.get_left_child_index(index)) print(self.data[index], end=" ") self.in_order_traversal(self.get_right_child_index(index)) def post_order_traversal(self, index): if index == -1: return self.post_order_traversal(self.get_left_child_index(index)) self.post_order_traversal(self.get_right_child_index(index)) print(self.data[index], end=" ") def level_order_traversal(self): for i in range(self.size): if self.data[i] is not None: print(self.data[i], end=" ") def __str__(self): return str(self.data) tree = BinaryTree(7) tree.insert(2) tree.insert(3) tree.insert(5) tree.insert(7) tree.insert(1) tree.insert(6) print(tree.pre_order_traversal(0)) # 2 1 3 5 7 6 print(tree.in_order_traversal(0)) # 1 2 3 5 6 7 print(tree.post_order_traversal(0)) # 1 6 7 5 3 2 print(tree.level_order_traversal()) # 2 1 3 5 7 6 print(tree.get_height()) # 2
以上代码实现的是完全二叉树的顺序存储,并不适用于普通的二叉树,但是一般不会让你写不标准的
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 unity第一人称射击小游戏,有demo,在原脚本的基础上进行修改以达到要求
- ¥15 买了个传感器,根据商家发的代码和步骤使用但是代码报错了不会改,有没有人可以看看
- ¥15 关于#Java#的问题,如何解决?
- ¥15 加热介质是液体,换热器壳侧导热系数和总的导热系数怎么算
- ¥100 嵌入式系统基于PIC16F882和热敏电阻的数字温度计
- ¥15 cmd cl 0x000007b
- ¥20 BAPI_PR_CHANGE how to add account assignment information for service line
- ¥500 火焰左右视图、视差(基于双目相机)
- ¥100 set_link_state
- ¥15 虚幻5 UE美术毛发渲染