python数据结构教程 Day12

本章内容

1. 基本术语
2. 树的定义
3. 树的实现
4. 构建解析树
5. 前中后序遍历

一、基本术语

树

区别于之前讨论的树形结构，属于非线性结构。节点与其子节点相互独立、隔离。

节点

每个节点具有名称，或“键值”，节点还可以保 存额外数据项，数据项根据不同的应用而变。

边

每条边恰好连接两个节点，表示节点之间具有关联，边具有出入方向； 每个节点（除根节点）恰有一条来自另一节点的 入边； 每个节点可以有多条连到其它节点的出边。

根

树中唯一一个没有入边的节点

路径

由边依次连接在一起的节点的有序列表。

子节点

入边均来自于同一个节 点的若干节点，称为这个节点的子节点

父节点

一个节点是其所有出边所连接节点的父节点

兄弟节点

具有同一个父节点的节点之间称为兄弟节点

子树

一个节点和其所有子孙节点，以及相关边的集合

叶节点

没有子节点的节点称为叶节点

层级

从根节点开始到达一个节点的路径， 所包含的边的数量，称为这个节点的层级。

高度

树中所有节点的最大层级称为树的高度

二、树的定义

1、定义一

• 树由若干节点，以及两两连接节点的边组成，并有如下性质。
• 其中一个节点被设定为根；
• 每个节点n(除根节点)，都恰连接一 条来自节点p的边，p是n的父节点；
• 每个节点从根开始的路径是唯一的
• 如果每个节点最多有两个子节点， 这样的树称为“二叉树”

2、递归定义

• 空集；
• 或者由根节点及0或多个子树构成（其中子树也是树），每个子树的根到根节点具有边相连。

三、树的实现

1、嵌套列表法

根是myTree[0]，左子树myTree[1]，右子树 myTree[2]。子树的结构与树相同，是一种递归数据结构 很容易扩展到多叉树，仅需要增加列表元素即可。

定义函数来操作嵌套列表：

• BinaryTree创建仅有根节点的二叉树
• insertLeft/insertRight将新节点插入树中作为其直接的左/右子节点
• get/setRootVal则取得或返回根节点
• getLeft/RightChild返回左/右子树

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

def insertLeft(root, newbranch):
    t = root.pop(1)
    if len(t):
        root.insert(1,[newbranch,t,[]])
    else:
        root.insert(1,[newbranch,[],[]])
    return root

def insertRight(root, newbranch):
    t = root.pop(2)
    if len(t):
        root.insert(2,[newbranch,[],t])
    else:
        root.insert(2,[newbranch,[],[]])
    return root

def setRootValue(root, val):
    root[0] = val

def getRootValue(root):
    return root[0]

def getLeftChild(root):
    return root[1]

def getRightChild(root):
    return root[2]    

2、列表法（常用）

每个节点保存根节点的数据项，以及指向左右子树的链接。

定义一个类来实现

class BinaryTree:
    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(self,newNode):
        if self.rightchild == None:
            self.rightchild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.rightchild = self.rightchild
            self.rightchild = t

    def getLeftChild(self):
        return self.leftchild
    
    def getRightChild(self):
        return self.rightchild

    def setRootValue(self,newValue):
        self.key = newValue

    def getRootValue(self):
        return self.key

    def preorder(self):
        '''
        可以在类中实现前序遍历
        '''
        print(self.getRootValue())
        if self.leftchild:
            self.leftchild.preorder()
        if self.rightchild:
            self.rightchild.preorder()

四、构建解析树

思路：利用全括号表达式

如：3+4*5的全括号表达式为(3+(4*5))

从左到右按照如下规则进行解析树建立:

# 伪代码思路
# 注意“上升至父节点的操作没有对应的方法实现”，我们可以手动维护一个栈来完成这个操作
# 即：当前节点下降时，将下降前的节点push入栈。当前节点需要上升到父节点时，上升到pop出栈
# 的节点即可
if 当前单词是"("：
    为当前节点添加一个新节点作为其左子节点
    当前节点下降为这个新节点
elif 当前单词是操作符"+,-,/,*"：
    将当前节点的值设为此符号
    为当前节点添加一个新节点作为其右子节点，
    当前节点下降为这个新节点
elif 如果当前单词是操作数：
    将当前节点的值设为此数，
    当前节点上升到父节点
elif 当前单词是")"：
    则当前节点上升到父节点
else:
    raise ValueError

整个构建的过程如下：

建立解析树代码实现：

def buildParserTree(question):
    question_list = question.split()
    pstack = Stack()
    root = BinaryTree('')
    pstack.push(root)
    currentTree = root
    for i in question_list:
        if i == '(':
            currentTree.insertLeft('')
            pstack.push(currentTree)
            currentTree = currentTree.getLeftChild()
        elif i in ['+','-','*','/']:
            currentTree.setRootValue(i)
            currentTree.insertRight('')
            pstack.push(currentTree)
            currentTree = currentTree.getRightChild()
        elif i in ['0','1','2','3','4','5','6','7','8','9']:
            currentTree.setRootValue(int(i))
            parent = pstack.pop()
            currentTree = parent
        elif i==')':
            currentTree = pstack.pop()
        else:
            raise ValueError
    return root

对构建好的解析树进行求值

采用递归方法实现，先求出各个子树的值。

1、基本结束条件：

叶节点是最简单的子树，没有左右子节点，其根节点的数据项即为子表达式树的值

2、缩小规模：

将表达式树分为左子树、右子树，即为缩小规模

3、调用自身：

分别调用evaluate计算左子树和右子树的值，然后将左右子树的值依根节点的操作符进行计算，从而得到表达式的值。

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.getRootValue()]
        return fn(evaluate(leftC),evaluate(rightC))
    else:
        return parseTree.getRootValue()

五、前中后序遍历

这里给出递归写法，打印树中的每个元素：

def preorder(tree):
    if tree!=None:
        print(tree.getRootValue())
        preorder(tree.getLeftChild())
        preorder(tree.getRightChild())

def inorder(tree):
    if tree!=None:
        inorder(tree.getLeftChild())
        print(tree.getRootValue())
        inorder(tree.getRightChild())

def postorder(tree):
    if tree!=None:
        postorder(tree.getLeftChild())
        postorder(tree.getRightChild())
        print(tree.getRootValue())

采用终序遍历的方式生成全括号表达式：

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