二叉树的应用（解析树，及树的的前序，中序，后序遍历）

1.解析树
1.1解析树构建器

我们的目标是构建一个如上图所示的二叉树实现的方法如下

from 数据结构与算法.栈.Queue import Stack
from 数据结构与算法.树.二叉树.二叉树 import BinaryTree


def buildParesTree(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 not in '+-*/':
            currentTree.setRootVal(eval(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('Unknown Operator'+i)

    return eTree

三种遍历方法代码如下：

# 前序遍历算法
print('前序遍历算法')
def preorder(tree):
    if tree:
        print(tree.getRootVal())
        preorder(tree.getLeftChild())
        preorder(tree.getRightChild())
tree=buildParesTree('( 3 + ( 4 * 5 ) )')
preorder(tree)

# 后序遍历算法
print('后序遍历算法')
def postorder(tree):
    if tree!=None:
        postorder(tree.getLeftChild())
        postorder(tree.getRightChild())
        print(tree.getRootVal())
postorder(tree)

# 中序遍历函数
print('中序遍历函数')

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

inorder(tree)