《字符串递归构建成一棵二叉树并用栈进行后序遍历打印出结果》Python代码实现

757次阅读
没有评论
《字符串递归构建成一棵二叉树并用栈进行后序遍历打印出结果》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)

 

神龙|纯净稳定代理IP免费测试>>>>>>>>天启|企业级代理IP免费测试>>>>>>>>IPIPGO|全球住宅代理IP免费测试

相关文章:

版权声明:Python基础教程2022-11-22发表,共计1726字。
新手QQ群:570568346,欢迎进群讨论 Python51学习