如何将解析树中跟踪父节点的方式从栈改为直接使用父字段

嘿，我帮你把这个解析树作业的内容整理清楚，并且完成了把栈跟踪父节点改成直接用父节点引用的修改，一起来看看吧～

作业背景 #

我有一项作业，要求接收完全括号化字符串后生成解析树并打印。其中核心修改点是：将跟踪父节点的方式从栈改为直接使用节点的父引用。所有代码都在同一文件中，无需处理导入。

解析树构建规则 #

构建解析树的算法规则如下：

• 若当前令牌为'('，为当前节点添加左子节点并下移至左子节点。
• 若当前令牌为['+','-', '^', '/','*']中的运算符，将当前节点根值设为该运算符，添加右子节点并下移至右子节点。
• 若当前令牌为数字，将当前节点根值设为该数字并返回父节点。
• 若当前令牌为')'，返回当前节点的父节点。

第一步：修改二叉树类（添加父节点引用） #

原来的BinaryTree类没有父节点属性，我们需要先给每个节点加上parent属性，并且在插入子节点时设置好父引用，这样才能直接跟踪父节点：

class BinaryTree:
    def __init__(self, rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None
        self.parent = None  # 新增父节点引用

    def insertLeft(self, newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
            self.leftChild.parent = self  # 给新左子节点绑定父节点
        else:
            t = BinaryTree(newNode)
            t.leftChild = self.leftChild
            t.leftChild.parent = t  # 更新原有左子节点的父引用
            self.leftChild = t
            t.parent = self  # 给新节点绑定父节点

    def insertRight(self, newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
            self.rightChild.parent = self  # 给新右子节点绑定父节点
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            t.rightChild.parent = t  # 更新原有右子节点的父引用
            self.rightChild = t
            t.parent = self  # 给新节点绑定父节点

    def getRightChild(self):
        return self.rightChild

    def getLeftChild(self):
        return self.leftChild

    def setRootVal(self, obj):
        self.key = obj

    def getRootVal(self):
        return self.key

    def getParent(self):  # 新增获取父节点的方法
        return self.parent

第二步：移除栈类（不再需要） #

原来的Stack类专门用于跟踪父节点，现在改用父节点直接引用，所以这个类可以直接删除，不需要保留了。

第三步：修改构建解析树的函数 #

移除所有栈相关的代码，改用节点的parent属性来切换当前节点，完全符合作业要求：

def buildParseTree(fpexp):
    fplist = fpexp.split()
    eTree = BinaryTree('')
    currentTree = eTree

    for i in fplist:
        if i == '(':
            currentTree.insertLeft('')
            currentTree = currentTree.getLeftChild()  # 下移到左子节点
        elif i not in ['+', '-', '^', '*', '/', ')']:
            currentTree.setRootVal(i)
            currentTree = currentTree.getParent()  # 返回父节点，替代栈的pop操作
        elif i in ['+', '-', '^', '*', '/']:
            currentTree.setRootVal(i)
            currentTree.insertRight('')
            currentTree = currentTree.getRightChild()  # 下移到右子节点
        elif i == ')':
            currentTree = currentTree.getParent()  # 返回父节点，替代栈的pop操作
        else:
            raise ValueError(f"Invalid token: {i}")
    return eTree

测试用的打印函数（可选） #

如果需要验证解析树的结构，可以用这个递归打印函数来直观查看：

def printTree(tree, level=0):
    if tree != None:
        printTree(tree.getRightChild(), level + 1)
        print(' ' * 4 * level + '->', tree.getRootVal())
        printTree(tree.getLeftChild(), level + 1)

# 测试示例
if __name__ == "__main__":
    exp = "( ( 3 + 4 ) * ( 5 - 2 ) )"
    pt = buildParseTree(exp)
    printTree(pt)

内容的提问来源于stack exchange，提问作者Jose Avalos