小鱼要学数据结构与算法（基于python)—Day19树的遍历、优先队列和二叉堆

树的遍历、优先队列和二叉堆

一、知识概览

本章主要讲树的遍历、优先队列和二叉堆及实现。

1.1 树的遍历

主要有前序遍历，后序遍历，中序遍历三种方法

1.2 优先队列和二叉堆

由优先队列引出二叉堆，最小堆，最大堆的概念。介绍二叉堆数据结构常用操作。

1.3二叉堆的实现

用非嵌套列表来实现二叉堆。另外，可以用二叉堆进行排序，给排序提供新思路。

二、代码实现

2.1 树的遍历

三种遍历方法：

# 树的遍历：递归算法
# 前序遍历
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

2.2 二叉堆操作实现

#二叉堆操作实现
class BinHeap:
    def __init__(self):
        self.heapList=[0]
        self.curentSize=0
#insert代码
    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 insert(self,k):
        self.heapList.append(k)
        self.curentSize=self.curentSize+1
        self.percUp(self.curentSize)#新key上浮
    def delMin(self):
        retval=self.heapList[1]
        self.heapList[1]=self.heapList[self.curentSize]
        self.curentSize=self.curentSize-1
        self.heapList.pop()#移除最后一个
        self.perDown(1)#新顶下沉
        return retval
    def perDown(self,i):
        while (i*2)<=self.curentSize:
            mc=self.minChild(i)#子节点中最小的那个key
            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.curentSize:#唯一子节点
            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.curentSize=len(alist)
        self.heapList=[0]+alist[:]
        print(len(self.heapList),i)
        while (i>0):
            print(self.heapList,i)
            self.perDown(i)
            i=i-1#
        print(self.heapList,i)