树和树的算法(三)

树的遍历

对一个数据集中的所有数据项进行访问的操作称为“遍历Traversal”，在线性数据结构中，对其所有数据项的访问比较简单，按照顺序依次进行即可。树的非线性特点，使得遍历操作较为复杂。

我们按照对节点访问次序的不同来区分3种遍历：

• 前序遍历(preorder):先访问根节点,再递归地前序访问左子树、最后前序访问右子树;

• 中序遍历(inorder):先递归地中序访问左子树,再访问根节点,最后中序访问右子树;

• 后序遍历(postorder):先递归地后序访问左子树,再后序访问右子树,最后访问根节点。

树遍历的代码非常简洁：

# 前序遍历
def preorder(tree):
    if tree:
        print(tree.getRootVal()) # 先访问根节点
        preorder(tree.getLeftChild()) # 递归访问左子树
        preorder(tree.getRightChild()) # 递归访问右子树

后序和中序遍历的代码仅需要调整顺序：

# 后序遍历
def postorder(tree):
    if tree:
        postorder(tree.getLeftChild()) # 递归访问左子树
        postorder(tree.getRightChild()) # 递归访问右子树
        print(tree.getRootVal()) # 访问根节点

# 中序遍历
def inorder(tree):
    if tree:
        inorder(tree.getLeftChild()) # 递归访问左子树
        print(tree.getRootVal()) # 访问根节点
        inorder(tree.getRightChild()) # 递归访问右子树

也可以在BinaryTree类中实现前序遍历的方法：

'''class BinaryTree'''
def preorder(self):
    print(self.key)
    if self.leftChild:
        self.leftChild.preorder()
    if self.rightChild:
        self.rightChild.preorder()

这种在类中实现遍历的方法我们基本不会使用，因为我们很少只是想纯粹的去遍历树。在大多数情况下，我们是使用其中一个基本的遍历模式来完成其他任务。

回顾我们之前实现的表达式解析树求值函数(evaluate),实际上也是一个后序遍历的过程，

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

采用后序遍历法重写表达式求值代码:

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