数据结构学习-python实现-树--0414

import stack  # 之前写好的栈
import binarytree  # 之前写好的二叉树
import operator  # 处理运算符
 
def buildparsetree(fpexp):
    print(fpexp)  # 打印输入，避免出问题，例如不符合解析形式，这段代码必须是全括号。
    fplist = list(fpexp)
    pstack = stack.Stack()
    etree = binarytree.BinaryTree('')  #新建空树
    pstack.push(etree)  # 讲树的根节点压入栈
    currenttree = etree  # 确定当前节点位置
    for i in fplist:
        if i == '(':
            currenttree.insertleft('')  # 插入左子树
            pstack.push(currenttree)  # 将根节点压入栈
            currenttree = currenttree.getleftchild()  # 当前节点移动到左子节点
        elif i not in ['+', '-', '*', '/', ')']:
            currenttree.setrootvalue(int(i))
            parent = pstack.pop()
            currenttree = parent  # 为了此步骤才需要栈，当前节点退回根节点
        elif i in ['+', '-', '*', '/']:
            currenttree.setrootvalue(i)
            currenttree.insertright('')
            pstack.push(currenttree)
            currenttree = currenttree.getrightchild()
        elif i == ')':
            currenttree = pstack.pop()
        else:
            raise ValueError
    return etree


def evaluate(parsetree):
    opers = {'+': operator.add, '-': operator.sub,
             '*': operator.mul, '/': operator.truediv}
    leftc = parsetree.getleftchild()
    rightc = parsetree.getrightchild()

    if leftc and rightc:
        fn = opers[parsetree.getrootvalue()]
        return fn(evaluate(leftc), evaluate(rightc))
    else:
        return parsetree.getrootvalue()


c = buildparsetree("((3+2)*(4+5))")
print(evaluate(c))


def postordereval(tree):  # 后缀表达式的解析树
    opers = {'+': operator.add, '-': operator.sub,
             '*': operator.mul, '/': operator.truediv}
    res1 = None
    res2 = None
    if tree:
        res1 = postordereval(tree.getleftchild())
        res2 = postordereval(tree.getrightchild())
        if res1 and res2:
            return opers[tree.getrootvalue()](res1, res2)
        else:
            return tree.getrootvalue()

def printexp(tree):  # 从树改写为中缀表达式
    sval = ''
    if tree:
        sval = printexp(tree.getleftchild())
        sval = sval + str(tree.getrootvalue())
        sval = sval + printexp(tree.getrightchild())
        if len(sval) != 1:  # 取消单个数字上的括号
            sval = '(' + sval + ')'
    return sval

print(printexp(c))

class BinHeap:
    def __init__(self):
        self.heaplist = [0]  # 为了后续的下标可实现父节点是子节点的二分之一这一性质。
        self.currentsize = 0

    def percup(self, i):  # 数据上浮，若子节点的值小于父节点，则数据交换上浮
        while i // 2 > 0:
            if self.heaplist[i] < self.heaplist[i//2]:
                self.heaplist[i//2], self.heaplist[i] = self.heaplist[i], self.heaplist[i//2]
                i //= 2

    def insert(self, k):
        self.heaplist.append(k)
        self.currentsize += 1
        self.percup(self.currentsize)

    def percdown(self, i):  # 数据下沉，当删除最小值时，使用最后的值替换最小值，然后将其下沉至合适位置。
        while (i * 2) <= self.currentsize:
            mc = self.minchild(i)
            if self.heaplist[i] > self.heaplist[mc]:
                self.heaplist[i], self.heaplist[mc] = self.heaplist[mc], self.heaplist[i]
                i = mc

    def minchild(self, i):  # 取左右子节点当中较小的值
        if i * 2 + 1 > self.currentsize:
            return i * 2
        else:
            if self.heaplist[i*2] < self.heaplist[i*2+1]:
                return i * 2
            else:
                return i * 2 + 1

    def delmin(self):
        retval = self.heaplist[1]
        self.heaplist[1] = self.heaplist[self.currentsize]
        self.currentsize -= 1
        self.heaplist.pop()
        self.percdown(1)
        return retval

    def buildheap(self, alist):  # alist是key值的列表，根据其大小进行建堆
        i = len(alist) // 2
        self.currentsize = len(alist)
        self.heaplist = [0] + alist[:]
        print(len(self.heaplist), i)
        while i > 0:
            print(self.heaplist, i)
            self.percdown(i)
            i -= 1
        print(self.heaplist, i)