简易Parser入门【一】:从树的递归开始

简易Parser入门【一】:从树的递归开始

首先我们从树类的简单解析开始,假设有一个树节点(它是一个二叉树节点):

class Tr:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

我们用这个树节点构造一棵树:

t_root = Tr(5, Tr(3, Tr(4), Tr(6)),
               Tr(1, Tr(2), Tr(7)))

它的结构如图所示,我们想打印从根节点到每个叶子节点的路径怎么办呢?遍历树一般都能想到用递归,但是递归到底递归什么东西呢?递归函数的参数如何选择?返回什么?

思考递归的时候,我们可以从问题点出发,先寻找停止递归的条件。我们需要打印从根节点到每个叶子节点的路径,所以停止条件就是到达叶子节点了。可以先用代码写出来:

def print_leaf(tr_in):
    # type: (Tr) -> None
    if tr_in.left is None and tr_in.right is None:
        # todo: stop here and do something

我们达到停止条件需要做什么呢?需要打印。打印什么?打印从根节点到叶子节点的路径。好了,我们现在达到了叶子节点,函数拥有该节点tr_in的val,但是之前路径的值我们还没有。我们需要有,那么先假设我们有一个,这个怎么来的呢,根据思考,之前路径的值当然是沿途遍历节点传进来的,那么自然需要当成函数输入传进来:

def print_leaf(tr_in, str_in):
    # type: (Tr, str) -> None
    if tr_in.left is None and tr_in.right is None:
        print(str_in + str(tr_in.val))

接着我们思考,我们没有到达叶子节点的时候,需要做什么。到达叶子节点是停止的标志,那么没有到达叶子节点就是递归的标志。我们构造左节点或右节点还有叶子的情况:

def print_leaf(tr_in, str_in=""):
    # type: (Tr, str) -> None
    if tr_in.left is not None:
        print_leaf(tr_in.left, str_in + str(tr_in.val))

    if tr_in.right is not None:
        print_leaf(tr_in.right, str_in + str(tr_in.val))

    if tr_in.left is None and tr_in.right is None:
        print(str_in + str(tr_in.val))

这样整个代码就写好了,我们实现了一个递归函数,它遇到有子节点的情况就递归调用自己,并一路把沿途的值存到str_in里边,到达最深层叶子的时候就停止,并把路径打印出来,完整代码如下:

class Tr:

    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def print_leaf(tr_in, str_in=""):
    # type: (Tr, str) -> None
    if tr_in.left is not None:
        print_leaf(tr_in.left, str_in + str(tr_in.val))

    if tr_in.right is not None:
        print_leaf(tr_in.right, str_in + str(tr_in.val))

    if tr_in.left is None and tr_in.right is None:
        print(str_in + str(tr_in.val))


if __name__ == "__main__":
    t_root = Tr(5, Tr(3, Tr(4), Tr(6)),
                   Tr(1, Tr(2), Tr(7)))
    print_leaf(t_root)

打印效果如下:

534
536
512
517