实现链式存储二叉树构建,完成查找、求树高度、中序遍历、先遍历、后序遍历和层序遍历的程序,并用相关数据进行测试。给出算法的时间和空间复杂度。
1条回答 默认 最新
- 天际的海浪 2022-06-07 21:20关注
获得2.50元问题酬金 from collections import deque class BiTreeNode: def __init__(self, data): self.data = data self.lchild = None self.rchild = None # ABCDE#F##G##### class CreateBiTree: """ str_tree: 传入字符串 return: 返回根结点 """ def __init__(self, str_tree): self.str_tree = str_tree def create_tree(self): l1 = list(self.str_tree) l1 = [None if i == '#' else i for i in l1] nodes = [BiTreeNode(l1[i]) for i in range(len(l1))] root = nodes[0] for i in range(len(l1)): if 2*i+2 > len(l1): break cur_node = nodes[i] if nodes[2*i+1].data: cur_node.lchild = nodes[2*i+1] if nodes[2*i+2].data: cur_node.rchild = nodes[2*i+2] return root def __call__(self): return self.create_tree() class BiTreeSorted: def __init__(self, root): self.root = root def pre_order(self, root): # 前序排列 if root: print(root.data, end=',') self.pre_order(root.lchild) self.pre_order(root.rchild) def in_order(self, root): # 中序排列 if root: self.in_order(root.lchild) print(root.data, end=',') self.in_order(root.rchild) def post_order(self, root): # 后序排列 if root: self.post_order(root.lchild) self.post_order(root.rchild) print(root.data, end=',') def level_order(self, root): # 层序排列 queue = deque() queue.append(root) while len(queue) > 0: node = queue.popleft() print(node.data, end=',') if node.lchild: queue.append(node.lchild) if node.rchild: queue.append(node.rchild) def __call__(self): print('前序排列') self.pre_order(self.root) print() print('中序排列') self.in_order(self.root) print() print('后序遍历') self.post_order(self.root) print() print('层序遍历') self.level_order(self.root) print() a = CreateBiTree('ABCDE#F##G#####') root = a() print('根结点为:', root.data) sorted = BiTreeSorted(root) sorted() # 调用__call__方法
解决 1无用
悬赏问题
- ¥15 安卓adb backup备份应用数据失败
- ¥15 eclipse运行项目时遇到的问题
- ¥15 关于#c##的问题:最近需要用CAT工具Trados进行一些开发
- ¥15 南大pa1 小游戏没有界面,并且报了如下错误,尝试过换显卡驱动,但是好像不行
- ¥15 没有证书,nginx怎么反向代理到只能接受https的公网网站
- ¥50 成都蓉城足球俱乐部小程序抢票
- ¥15 yolov7训练自己的数据集
- ¥15 esp8266与51单片机连接问题(标签-单片机|关键词-串口)(相关搜索:51单片机|单片机|测试代码)
- ¥15 电力市场出清matlab yalmip kkt 双层优化问题
- ¥30 ros小车路径规划实现不了,如何解决?(操作系统-ubuntu)