数据结构和算法是计算机技术的基本功之一，北京大学的课程深入浅出，使用Python作为载体简化了编程难度。最近浏览了59-67，主要内容是树结构的介绍，二叉树结构及其实现（含完全二叉树定义与实现问题），二叉堆结构及其实现。并且以语法解析树为例探讨了树结构的应用。

非线性数据结构-树

树在计算机科学的各个领域中被广泛应用-操作系统，图形学，数据库系统，计算机网络。生物分类树：层次化-越接近顶层越普遍，越接近底层越独特。一个节点的子节点与另一个节点的子节点相互之间是隔离、独立的，如不同对象共同的属性。HTML文档的嵌套标记就是树结构的应用，域名体系也是树结构的应用。

树结构相关术语

节点Node:使用键值作为节点的名称，Node还保存额外数据项
边Edge:另一个基础部分，每条边恰好连接两个节点，表示节点之间具有关联，边具有出入方向
每个节点（除根节点）恰有一条来自另一节点的入边
每个节点可以有多条连到其他节点的出边
根Root：
路径Path：
子节点和父节点：入边均来自于同一个节点的若干节点，成为这个节点的子节点。
兄弟节点Sibling:同一个父节点的节点之间
子树Subtree：一个节点和其所有子孙节点，以及相关边的集合
层级：从根节点到某节点边的数量
树中所有节点最大层级成为树的高度
定义1：树由若干节点以及两两连接的边组成
定义2：树是-空集；或者根节点及0或多个子树构成，每个子数的根到根节点具有边相连

树的嵌套列表实现

首先使用列表类型实现二叉树类型
用递归的嵌套列表实现二叉树，由具有3个元素的列表实现：第1个元素为根节点的值，第2个元素是左子树，第三个元素是右子树-形如【root,left,right】
嵌套列表法：
myTree=['a',['b'],['c',['d'],['e']]]
子树的结构与树相同，是一种递归数据结构
很容易扩展成多叉树，只需要增加列表元素即可

"""
定义一系列函数来辅助操作嵌套列表
BinaryTree-创建仅有根节点的二叉树
inserLeft-将新节点插入树中作为直接的左右节点
get/setRootVal-取得返回根节点
getLeft/RightChild-返回左右子树
"""

def BinaryTree(r):
    return [r,[],[]]

def insertLeft(root,newBranch):
    t=root.pop(1)#左子树
    if len(t)>1:#如果原先左子树非空，插入后原左子树变成下一级左子树
        root.insert(1,[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,[],[]])
    return root

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)

节点链接法实现二叉树

每个节点保存根节点的数据项，以及指向左右子树的链接
定义一个binaryTree类-成员key保存根节点数据项，成员left/right保存指向左右子树的引用

class BinaryTree:
    def __init__(self,rootObj):
        self.key=rootObj
        self.rightChild=None#BinaryTree对象的引用
        self.leftChild=None
    
    def insertLeft(self,newNode):
        if self.leftChild==None:
            self.leftChild=BinaryTree(newNode)
        else:
            t=BinaryTree(newNode)
            t.leftChild=sekf.leftChild
            self.leftChild=t
        
    def insertRight(self,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.getLeftChild().setRootVal('c')

树结构的应用-语法树

将树用于表示语言中句子，可以分析句子的各种语法成分，对句子的各种成分进行处理
程序设计语言的编译-从语法树生成目标代码的编译过程
表达式表示为树结构，操作数叶节点，操作符内部节点，越底层的表达谁计算优先级越高
用全括号表达式构建表达式解析树
利用表达式解析树对表达式求职
从表达式解析树恢复原表达式的字符串形式

首先，全括号表达式要分解为单词Token列表，其单词分为括号”()“，操作符”+-/*“和操作数”0-9“这几类
创建流程，当前节点的移动-遇到左括号，创建左子节点，当前节点下降，右括号，上升到父节点
操作符-当前节点值设为操作符，创建右子节点并移动当前节点至右节点
"""
创建左右子树-insetLeft/Right
设置当前节点值-setRootVal
下降到左右子树-getLeft/RightChild
上升到父节点-没有方法支持？使用栈来记录父节点位置-每当下降，下降前的位置push入栈，反之pop
"""

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)#stack中的tree类值会随之改变
            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

对此二叉树求值，使用递归算法，定义求值递归函数evaluate
调用自身，左右子树求值，父节点操作符
"""
Python operator库,将操作符引入为函数对象，增加代码可读性
"""

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))
    else:
        return parseTree.getRootVal()

对此二叉树遍历
以递归的方式访问树。1 前序遍历 preorder：先访问根节点，再递归地前序访问左子树
最后前序访问右子树
2中序遍历,递归地访问左子树-根节点-右子树
后续遍历-递归访问左子树-右子树-根节点 postorder

def preorder(tree):
    if tree:
        print(tree.getRootVal())
        preorder(tree.getLeftChild())
        preorder(tree.getRightChild())

也可以在BinaryTree类中实现前序遍历算法

def preorder(self):
    print(self.key)
    if self.leftChild:
        self.leftChild.predorder()
    if self.rightChild:
        self.rightChild.preorder()

中序遍历递归算法生成全括号中缀表达式

def printexp(tree):
    sVal=""
    if tree:
        sVal='('+printexp(tree.getLeftChild())
        sVal=sVal+str(tree.getRootVal())
        sVal=sVal+printexp(tree.getRightChild())+')'
    return sVal

队列的变体-优先队列Priority Queue

VIP客户插队，操作系统中关键任务优先等
优先队列的出队和队列一样从队首出队，但在优先队列内部，数据项的次序由优先级决定
因此，优先队列的重点在于入队的时候确定正确的顺序，O(n)?
使用二叉堆数据结构是一种经典方案-将入队出队都保持在O(log n)
二叉堆逻辑上像二叉树，但却是用非嵌套的列表来实现的
"""
定义二叉堆对象的操作
BinaryHeap()空对象创建
insert(k)新key插入堆中
findMin()返回堆中最小项，最小项仍保留在堆中
delMin()返回堆中最小项并删除之
isEmpty()
size()
buildHeap(list)从一个key列表创建新堆
为了使堆操作能保持在对数水平上，就必须采用二叉树结构，且二叉树最好是平衡的-左右子树拥有相同数量的节点
定义【完全二叉树】：叶节点最多出现在最底层和次底层，而且最底层的叶节点都连续集中在最左边，每个内部节点都有两个子节点，最多可有1个节点例外
使用非嵌套列表实现，节点下标p，左子节点2p，右子节点2p+1，父节点p//2[1开始的下标]。
因此，任何一个节点，父节点的key值小于其key值，路径皆为已排序数列。这就是堆次序。
"""

二叉堆操作的实现

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

#新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 insert(self,k):
        self.heapList.append(k)
        self.currentSize=self.currentSize+1
        self.percUp(self.currentSize)
    
#delMin()将最后一个节点移动到根节点-再调整顺序，保持完全二叉树的性质-下沉方法
#左还是右？找更小的。
    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

#buildHeap(list)逐个insert的话O(nlogn),用下沉法可以O(n)
    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)