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

Question

我已经实现了CYK解析算法，它使用自底向上的方法来构建一个解析树。当它遍历算法时，最终解决方案的路径存储在backpointer中。从后指针开始，我们构造树。这最后一步是我所面临的问题。在

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

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和{}是由int表示的各自树的规则。如果到达叶节点，则没有元组，只有表示终端规则的int。在

^{pr2}$

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

它看起来是这样的：

^{3}$

树之间不应该有data节点。在

编辑：

问题不在于有一个额外的数据节点（上面的语句是错误的），而是在Lvl1之后，新的分支不是添加到Lvl2上的L1.left/right和{}，而是添加到L1和{}data字段。因此L1/R1.data本身就是一棵树，L1.left/right和{}没有使用，因此{}。在

应该是这样的：

                  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类的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)