【数据结构】【树及算法】二叉树的实现，树的应用：表达式解析，树的遍历，优先队列和二叉堆

用list实现二叉树

def BinaryTree(r):  # 创建二叉树
    return [r,[],[]]

def insertLeft(root,newBranch):  # 在原树上左子树插入新值
    t = root.pop(1)
    if len(t) > 1:
        root.insert(1,[newBranch,t,[]])  # [newBranch,t 为左子树,[] 为右子树 ]
    else:
        root.insert(1,[newBranch,[],[]])
    return root

def insertRight(root,newBranch):
    t = root.pop(2)
    if len(t) > 1:
        root.insert(2,[newBranch,[],t])
    else:
        root.insert(2,[newBranch,[],[]])

def getRootVal(root):
    return root[0]

def setRootVal(root,newVal):
    root[0] = newVal

def getLeftChild(root):
    return root[1]

def getRightChild(root):
    return root[2]


r = BinaryTree(3)
insertLeft(r,4)
insertLeft(r,5)
insertRight(r,6)
insertRight(r,7)
l = getLeftChild(r)
print(l)

setRootVal(1,9)
print(r)
insertLeft(1,11)
print(r)
print(getRightChild(getRightChild(r)))

树的链表实现

def BinaryTree(r):  # 创建二叉树
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

def insertLeft(self,newNode):  # 在原树上左子树插入新值
    if self.leftChild == None:
        self.leftChild = BinaryTree(newNode)
    else:# 若原来左子树不空，就把新值生成一个左子树
        t = BinaryTree(newNode)
        t.leftChild = self.leftChild  # 把新节点的左子树指向原来根的左子树
        self.leftChild = t

def insertRight(slef,newNode):
    if self.rightChild == None:
        self.rightChild = BinaryTree(newNode)
    else:
        t = BinaryTree(newNode)
        t.rightChild = self.rightChild
        self.rightChild = t 

def getRootVal(self):
    return self.key

def setRootVal(self,obj):
    self.key = obj

def getLeftChild(self):
    return self.leftChild

def getRightChild(self):
    return self.rightChild


r = BinaryTree('a')
r.insertLeft('b')
r.insertRight('c')
r.getRightChild().setRootVal('hello')
r.getLeftChild().insertRight('d')

def buildParseTree(fpexp):
    fplist = fpexp.split()
    pStack = Stack()
    eTree = 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.setRootVal(int(i))
            parent = pStack.pop()  # 出栈上升
            currentTree = parent
        elif i in ['+','-','*','/']:  # 操作符
            currentTree.setRootVal(i)
            currentTree.insertRight('')
            pStack.push(currentTree)
            currentTree = currentTree.getRightChild()
        elif i == ')':  # 表达式结束
            currentTree = pStack.pop()  # 出栈上升
        else:
            raise ValueError    
    return eTree

import operator

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.getRootVal()]
        return fn(evaluate(leftC),evaluate(rightC))  # 左子树的值和右子树的值作为fn这个操作数的两个操作数
    else:
        return parseTree.getRootVal()  # 基本结束条件

树的遍历

def preorder(tree):  # 前序遍历
    if tree:
        print(tree.getRootVal())
        preorder(tree.getLeftChild())
        preorder(tree.getRightChild())
    
def postorder(tree):  # 后序遍历
    if tree != None:
        postorder(tree.getLeftChild())
        postorder(tree.getRightChild())
        print(tree.getRootVal())

def inorder(tree):  # 中序遍历
    if tree != None:
        inorder(tree.getLeftChild())
        print(tree.getRootVal())
        inorder(tree.getRightChild())

# 采用后序遍历法重写表达式求值代码
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.getRootVal()](res1,res2)
        else:
            return tree.getRootVal()  # 根节点

# 采用中序遍历递归算法生成全括号中缀表达式
def printexp(tree):
    sVal = ""
    if tree:
        sVal = '(' + printexp(tree.getLeftChild())
        sVal = sVal + str(tree.getRootVal())
        sVal = sVal + printexp(tree.getRightChild()) + ')'
    return sVal

优先队列和二叉堆

from pythonds.trees.binheap import Binheap

bh = Binheap()
bh.insert(5)
bh.insert(7)
bh.insert(3)
bh.insert(11)

print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())

class Binheap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0

    # 根节点要从1开始放

    def insert(self,k):
        self.heapList.append(k)  # 添加到末尾
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)  # 新key上浮
    
    def percUp(self,i):
        while i // 2 > 0:
            if self.heapList[i] < self.heapList[i//2]:  # 若当前节点比父节点小
                tmp = self.heapList[i//2]  # 与父节点交换
                self.heapList[i//2] = self.heapList[i]
                self.heapList[i] = tmp
            i = i // 2  # 沿路径向上

def delMin(self):
        retVal = self.heapList[1]  # 移走堆项
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapList.pop()
        self.percDown(1)  # 新项下沉
        return retVal

    def percDown(self,i):
        while(i*2) <= self.currentSize:
            mc = self.minChild(i)
            if self.heapList[i] > self.heapList[mc]:
                tmp = self.heapList[i]  # 交换下沉
                self.heapList[i] = self.heapList[mc]
                self.heapList[mc] = tmp
            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 buildHeap(self,alist):
        # 从无序表生成“堆”
        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 = i - 1
        print(self.heapList, i)