树

快速总结：

映射的不同实现间的性能对比：

	有序列表	散列表	二叉搜索树	AVL 树
put	$O(n)$	$O(1)$	$O(n)$	$O(\log_2{n})$
get	$O(\log_2{n})$	$O(1)$	$O(n)$	$O(\log_2{n})$
in	$O(\log_2{n})$	$O(1)$	$O(n)$	$O(\log_2{n})$
del	$O(n)$	$O(1)$	$O(n)$	$O(\log_2{n})$

树的属性

1. 可以从树的顶部开始，沿着由椭圆和箭头构成的路径，一直到底部。
2. 一个节点的所有子节点都与另一个节点的所有子节点无关。
3. 叶子节点都是独一无二的。

一个常见的树状结构是文件系统。在文件系统中，目录或文件夹呈树状结构。

下图展示了 Unix 文件系统的一小部分，

树的构成

节点
节点是树的基础部分。它可以有自己的名字，我们称作“键”。节点也可以带有附加信息，我们称作“有效载荷”。有效载荷信息对于很多树算法来说不是重点，但它常常在使用树的应用中很重要。

边
边是树的另一个基础部分。两个节点通过一条边相连，表示它们之间存在关系。除了根节点以外，其他每个节点都仅有一条入边，出边则可能有多条。

根节点
根节点是树中唯一没有入边的节点。在上图中， /就是根节点。

路径
路径是由边连接的有序节点列表。比如，哺乳纲$\rightarrow$食肉目$\rightarrow$猫科$\rightarrow$猫属$\rightarrow$家猫就是一条路径。

子节点
一个节点通过出边与子节点相连。在上图中， log/、 spool/和 yp/都是 var/的子节点。

父节点
一个节点是其所有子节点的父节点。在上图中， var/是 log/、 spool/和 yp/的父节点。

兄弟节点
具有同一父节点的节点互称为兄弟节点。文件系统树中的 etc/和 usr/就是兄弟节点。

子树
一个父节点及其所有后代的节点和边构成一棵子树。

叶子节点
叶子节点没有子节点。

层数
节点 n 的层数是从根节点到 n 的唯一路径长度。由定义可知，根节点的层数是 0。

高度
树的高度是其中节点层数的最大值。上图中的树高度为 2。

树的定义

这里提供两种定义，其中一种涉及节点和边，另一种涉及递归。

定义一：树由节点及连接节点的边构成。

树有以下属性：

• 有一个根节点；
• 除根节点外，其他每个节点都与其唯一的父节点相连；
• 从根节点到其他每个节点都有且仅有一条路径；
• 如果每个节点最多有两个子节点，我们就称这样的树为二叉树。

定义二：一棵树要么为空，要么由一个根节点和零棵或多棵子树构成，子树本身也是一棵树。每棵子树的根节点通过一条边连到父树的根节点。

树的实现

可以使用以下函数创建并操作二叉树：

• BinaryTree() 创建一个二叉树实例。
• getLeftChild() 返回当前节点的左子节点所对应的二叉树。
• getRightChild() 返回当前节点的右子节点所对应的二叉树。
• setRootVal(val) 在当前节点中存储参数 val 中的对象。
• getRootVal() 返回当前节点存储的对象。
• insertLeft(val) 新建一棵二叉树，并将其作为当前节点的左子节点。
• insertRight(val) 新建一棵二叉树，并将其作为当前节点的右子节点。

实现树的关键在于选择一个好的内部存储技巧。 Python 提供两种有意思的方式，第一种称作“列表之列表”，第二种称作“节点与引用”。

列表之列表

用“列表之列表”表示树时，先从 Python 的列表数据结构开始，编写前面定义的函数。在“列表之列表”的树中，我们将根节点的值作为列表的第一个元素；第二个元素是代表左子树的列表；第三个元素是代表右子树的列表。

一棵简单的树：

对应的列表实现：

myTree = ['a',   #root
      ['b',  #left subtree
       ['d', [], []],
       ['e', [], []] ],
      ['c',  #right subtree
       ['f', [], []],
       [] ]
     ]

接下来提供一些便于将列表作为树使用的函数，以正式定义树数据结构。注意，我们不是要定义二叉树类，而是要创建可用于标准列表的函数。

列表函数 BinaryTree：

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

BinaryTree 函数构造一个简单的列表，它仅有一个根节点和两个作为子节点的空列表。

要给树添加左子树，需要在列表的第二个位置加入一个新列表。请务必当心：如果列表的第二个位置上已经有内容了，我们要保留已有内容，并将它作为新列表的左子树。

插入左子树：

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

在插入左子树时，先获取当前的左子树所对应的列表（可能为空），然后加入新的左子树，将旧的左子树作为新节点的左子树。这样一来，就可以在树的任意位置插入新节点 。

insertRight 与 insertLeft 类似：

插入右子树：

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]

节点与引用

树的第二种表示法是利用节点与引用。我们将定义一个类，其中有根节点和左右子树的属性。这种表示法遵循面向对象编程范式。

采用“节点与引用”表示法时，可以将树想象成如下图的结构：

节点与引用”表示法的要点是，属性 left 和 right 会指向 BinaryTree 类的其他实例。举例来说，在向树中插入新的左子树时，我们会创建另一个 BinaryTree 实例，并将根节点的 self.leftChild 改为指向新树。

BinaryTree 类：

class BinaryTree:
    def __init__(self,rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

上述构造方法接受一个对象，并将其存储到根节点中。正如能在列表中存储任何对象，根节点对象也可以成为任何对象的引用。

为了给树添加左子树，我们新建一个二叉树对象，将根节点的 left 属性指向新对象。

插入左子节点：

def insertLeft(self,newNode):
    if self.leftChild == None:
        self.leftChild = BinaryTree(newNode)
    else:
        t = BinaryTree(newNode)
        t.leftChild = self.leftChild
        self.leftChild = t

在插入左子树时，必须考虑两种情况。第一种情况是原本没有左子节点。此时，只需往树中添加一个节点即可。第二种情况是已经存在左子节点。此时，插入一个节点，并将已有的左子节点降一层。

insertRight 函数也要考虑相应的两种情况：要么原本没有右子节点，要么必须在根节点和已有的右子节点之间插入一个节点。

插入右子节点：

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

为了完成对二叉树数据结构的定义，我们需要编写一些访问左右子节点与根节点的函数。

二叉树的访问函数：

def getRightChild(self):
    return self.rightChild

def getLeftChild(self):
    return self.leftChild

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

def getRootVal(self):
    return self.key

---

二叉树的应用

解析树

我们可以将 ((7 + 3) ∗ (5 − 2)) 这样的数学表达式表示成解析树：

下面需要仔细考察解析树，重点如下：

• 如何根据完全括号表达式构建解析树；
• 如何计算解析树中的表达式；
• 如何将解析树还原成最初的数学表达式。

构建解析树的第一步是将表达式字符串拆分成标记列表。需要考虑 4 种标记：左括号、右括号、运算符和操作数。

• 左括号代表新表达式的起点，所以应该创建一棵对应该表达式的新树。
• 反之，遇到右括号则意味着到达该表达式的终点。
• 操作数既是叶子节点，也是其运算符的子节点。
• 每个运算符都有左右子节点。

根据上述信息，便可以定义以下 4 条规则：

1. 如果当前标记是(，就为当前节点添加一个左子节点，并下沉至该子节点；
2. 如果当前标记在列表['+', '-', '/', '*']中，就将当前节点的值设为当前标记对应的运算符；为当前节点添加一个右子节点，并下沉至该子节点；
3. 如果当前标记是数字，就将当前节点的值设为这个数并返回至父节点；
4. 如果当前标记是)，就跳到当前节点的父节点。

我们可以通过 getLeftChild 与 getRightChild 获取子节点，但如何追踪父节点呢？一个简单的办法就是在遍历这棵树时使用栈记录父节点。每当要下沉至当前节点的子节点时，先将当前节点压到栈中。当要返回到当前节点的父节点时，就将父节点从栈中弹出来。

解析树构建器：

from pythonds.basic import Stack
from pythonds.trees import BinaryTree

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 in ['+', '-', '*', '/']:
            currentTree.setRootVal(i)
            currentTree.insertRight('')
            pStack.push(currentTree)
            currentTree = currentTree.getRightChild()

        elif i == ')':
            currentTree = pStack.pop()

        elif i not in ['+', '-', '*', '/', ')']:
            try:
                currentTree.setRootVal(int(i))
                parent = pStack.pop()
                currentTree = parent

            except ValueError:
                raise ValueError("token '{}' is not a valid integer".format(i))

    return eTree

接下来，我们写一个递归计算函数计算解析树，并返回计算结果。

针对树进行操作的递归算法而言，一个很自然的基本情况就是检查叶子节点。解析树的叶子节点必定是操作数。

首先，获取指向当前节点的左右子节点的引用。如果左右子节点的值都是 None，就说明当前节点确实是叶子节点。如果当前节点不是叶子节点，则查看当前节点中存储的运算符，并将其应用于左右子节点的递归计算结果。

计算二叉解析树的递归函数：

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()

树的遍历

我们将对所有节点的访问称为“遍历”，共有 3 种遍历方式，分别为前序遍历、 中序遍历和后序遍历。

前序遍历
在前序遍历中，先访问根节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树。

中序遍历
在中序遍历中，先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。

后序遍历
在后序遍历中，先递归地后序遍历右子树，然后递归地后序遍历左子树，最后访问根节点。

将前序遍历算法实现为外部函数：

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.preorder()
    if self.rightChild:
        self.rightChild.preorder()

将代码从外部移到内部后有何变化，不仅需要用 self 代替 tree，还需要修改基本情况。内部方法必须在递归调用 preorder 前，检查左右子节点是否存在。

后序遍历函数：

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

后序遍历函数 postorder 与前序遍历函数 preorder 几乎相同，只不过对 print 的调用被移到了函数的末尾。

后序遍历的一个常见用途，就是计算解析树。

后序求值函数：

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 inorder(tree):
  if tree != None:
      inorder(tree.getLeftChild())
      print(tree.getRootVal())
      inorder(tree.getRightChild())

中序遍历解析树，可以还原不带括号的表达式。唯一要做的修改是：在递归调用左子树前打印一个左括号，在递归调用右子树后打印一个右括号。

修改后能还原完全括号表达式的中序遍历函数：

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

---