《字符串递归构建成一棵二叉树并用栈进行后序遍历打印出结果》Python代码实现
class Stack(object): def __init__(self):
self.items = [] def is_empty(self):
return self.items == [] def peek(self):
return self.items[len(self.items) – 1] def size(self):
return len(self.items) def push(self, item):
self.items.append(item) def pop(self): return self.items.pop()
class TreeNode(object): def __init__(self, x): self.expression = x self.left = None self.right = None self.parent = None self.state = 0
def structuralTree(root): str = root.expression nums = strToTree(str) if nums == -1 : if str.startswith("(") and str.endswith(")") : str = str[1:len(str)-1]; left = TreeNode(str) root.left = left left.parent = root structuralTree(left) else: return elif nums > 0 : leftStr = str[0:nums] rightStr = str[nums+1:len(str)] leftTree = TreeNode(leftStr) rightTree = TreeNode(rightStr) leftTree.parent = root rightTree.parent = root root.left = leftTree root.right = rightTree structuralTree(leftTree) structuralTree(rightTree)
def strToTree(str): num = 0 for i in range(len(str)): if str[i] == "(": num += 1 elif str[i] == ")": num -= 1 elif (str[i] == "+" or str[i] == "-") and num == 0 : return i return -1
def postOrder(root): stack = Stack() stack.push(root) while stack.size() >0 : current = stack.peek() num = 0 if current.left != None: num += 1 if current.right != None: num += 1 if current.state == num : print(current.expression) stack.pop() if current.parent != None : current.parent.state += 1 else: if current.left != None: stack.push(current.left) if current.right != None: stack.push(current.right)
#(4+8-(4-2)-3) #(6-3)-3+(4+5) #(1+2) #(3-2)+5 testTree = TreeNode("(4+8-(4-2)-3)") root = testTree structuralTree(root) postOrder(root)
相关文章
- Python使用tkinter组件Label显示简单数学公式
- 内网渗透之DCOM横向移动
- 以目标为导向的语义交流的共同语言——一个课程学习框架
- python爬虫前奏【成信笔记】
- HTML 5 File API:文件拖放上传功能
- 教你快速创建 Python 虚拟环境
- pyenv 实现Python多版本自由切换
- 用 Python 对 Excel文件进行批量操作
- Python - 接入钉钉机器人
- Python - 抓取 iphone13 pro 线下店供货信息并发送到钉钉机器人,最后设置为定时任务
- crontab - 解决 mac 下通过 crontab 设置了 Python 脚本的定时任务却无法运行
- [源码解析] PyTorch分布式(5) ------ DistributedDataParallel 总述&如何使用
- Python科普系列——类与方法(上篇)
- SAP对STO的交货单执行PGI,报错 -Fld selectn for mvmt type 643 acct 400020 differs
- Spring Boot 实现通用 Auth 认证的 4 种方式
- 盘点4种使用Python批量合并同一文件夹内所有子文件夹下的Excel文件内所有Sheet数据
- OushuDB 学习经验分享(三):技术特点
- Java和Python思维方式的不同之处
- Python中日志记录新技能
- 奥比中光Gemini OpenCV—Python使用