生成时将额外的分支添加到树中

Question

我已经实现了 CYK 解析算法，它使用自下而上的方法来构建解析树。当它遍历算法时，最终解决方案的路径存储在反向指针中。从反向指针，我们构建树。最后一步是我遇到的问题。

这是我用来存储树的数据结构：

class GrammarTree(object):
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insertLeft(self, new_node):
        self.left = GrammarTree(new_node)

    def insertRight(self, new_node):
        self.right = GrammarTree(new_node)

以下是我构建树的方式，其中back存储一个元组，其中split是用于拆分树的索引，left_rule和right_rule是由 int 表示的相应树的规则。如果到达叶节点，则没有元组，只有一个表示终端规则的 int。

def build_tree(start,end,idx,back):
    tree = GrammarTree(idx)
    node = back[start][end][idx]
    if isinstance(node,tuple):
        split,left_rule,right_rule = node
        tree.insertLeft(build_tree(start,split,left_rule,back))
        tree.insertRight(build_tree(split,end,right_rule,back))
        return tree
    else:
        tree.insertLeft(GrammarTree(node))
        return tree

问题是当函数完成构建树时，会添加额外的分支，即节点没有正确粘合在一起。

这是它的样子：

Lvl0                                root
                          /                            \
Lvl1                     L1                             R1
                  /       |    \             /           |       \
                 /        |     \           /            |        \
                /         |      \         /             |         \
               /          |       \       /              |          \
              /           |        \     /               |           \
Lvl2  L1.left=None L1.right=None L1.data R1.left=None R1.right=None R1.data
                                  /    \                            /    \
Lvl3                             L2     R2                         L3     R3

树之间不应该有 data 节点。

编辑：

问题不在于多了一个数据节点（上面的说法是错误的），而是在Lvl1之后，Lvl2上的L1.left/right和R1.left/right并没有增加新的分支，而是被添加到 L1 和 R1's data 字段。所以 L1/R1.data 最终成为一棵树，并且 L1.left/right 和 R1.left/right 没有被使用，因此 None。

它应该是这样的：

                  root
           /               \
          /                 \
   L1=root.left         R1=root.right
     /    \                 /   \
    /      \               /     \
   /        \             /       \
L2=L1.left  R2=L1.right L3=R1.left R3=R1.right

这是我调用构建树的地方：

back = [[[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 6, 0, 3, 0, 2], [0, 0, 0, (1, 6, 7), 0, 3, 0, (1, 7, 7)], [0, 0, 0, (1, 6, 7), 0, (1, 7, 3), 0, (1, 7, 7)], [0, 0, 0, (1, 6, 7), 0, (2, 7, 3), 0, (1, 7, 7)]],\ 
        [[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 6, 0, 3, 0, 2], [0, 0, 0, (2, 6, 7), 0, (2, 7, 3), 0, (2, 7, 7)], [0, 0, 0, (2, 6, 7), 0, (2, 7, 3), 0, (3, 7, 7)]],\
        [[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 6, 0, 3, 0, 2], [0, 0, 0, (3, 6, 7), 0, 3, 0, (3, 7, 7)]],\
        [[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 6, 0, 3, 0, 2]],\
        [[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]]]
build_tree(0,4,5,back)

Answer 1

问题出在 GrammarTree class 的 insertLeft() 和 insertRight() 方法中。您会发现我不是简单地连接分支，而是调用 GrammarTree 构造函数，因此我实际上是将一棵树包裹在另一棵树中。

我通过删除对构造函数的调用解决了这个问题。

class GrammarTree(object):
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insertLeft(self, new_node):
        self.left = new_node  ## <- NOT GrammarTree(new_node) 

    def insertRight(self, new_node):
        self.right = new_node ## <- NOT GrammarTree(new_node)

生成时将额外的分支添加到树中

Extra branches being added to tree when generated

python

algorithm

recursion

tree

cyk