如何为二叉树写括号？

Question

这里我尝试将二叉树组合成表达式。例如

b1 = 二叉树(3.0)

打印（括号（b1））

3.0

b2 = 二叉树(4.0)

b3 = 二叉树(7.0)

b4 = 二叉树("*", b1, b2)

b5 = 二叉树("+", b4, b3)

打印（括号（b5））`

((3.0 * 4.0) + 7.0)

我为parenthesize()写的代码在最下面，上面是二叉树基础代码。但是我的代码没有返回 "somenumber"，而是 returns ("somenumber")。当我删除“（”时，括号完全消失了。有人可以帮忙填写代码吗？

class BinaryTree:
"""
A Binary Tree, i.e. arity 2.

=== Attributes ===
@param object data: data for this binary tree node
@param BinaryTree|None left: left child of this binary tree node
@param BinaryTree|None right: right child of this binary tree node
"""

def __init__(self, data, left=None, right=None):
    """
    Create BinaryTree self with data and children left and right.

    @param BinaryTree self: this binary tree
    @param object data: data of this node
    @param BinaryTree|None left: left child
    @param BinaryTree|None right: right child
    @rtype: None
    """
    self.data, self.left, self.right = data, left, right

def __eq__(self, other):
    """
    Return whether BinaryTree self is equivalent to other.

    @param BinaryTree self: this binary tree
    @param Any other: object to check equivalence to self
    @rtype: bool

    >>> BinaryTree(7).__eq__("seven")
    False
    >>> b1 = BinaryTree(7, BinaryTree(5))
    >>> b1.__eq__(BinaryTree(7, BinaryTree(5), None))
    True
    """
    return (type(self) == type(other) and
            self.data == other.data and
            (self.left, self.right) == (other.left, other.right))

def __repr__(self):
    """
    Represent BinaryTree (self) as a string that can be evaluated to
    produce an equivalent BinaryTree.

    @param BinaryTree self: this binary tree
    @rtype: str

    >>> BinaryTree(1, BinaryTree(2), BinaryTree(3))
    BinaryTree(1, BinaryTree(2, None, None), BinaryTree(3, None, None))
    """
    return "BinaryTree({}, {}, {})".format(repr(self.data),
                                           repr(self.left),
                                           repr(self.right))

def __str__(self, indent=""):
    """
    Return a user-friendly string representing BinaryTree (self)
    inorder.  Indent by indent.

    >>> b = BinaryTree(1, BinaryTree(2, BinaryTree(3)), BinaryTree(4))
    >>> print(b)
        4
    1
        2
            3
    <BLANKLINE>
    """
    right_tree = (self.right.__str__(
        indent + "    ") if self.right else "")
    left_tree = self.left.__str__(indent + "    ") if self.left else ""
    return (right_tree + "{}{}\n".format(indent, str(self.data)) +
            left_tree)

def __contains__(self, value):
    """
    Return whether tree rooted at node contains value.

    @param BinaryTree self: binary tree to search for value
    @param object value: value to search for
    @rtype: bool

    >>> BinaryTree(5, BinaryTree(7), BinaryTree(9)).__contains__(7)
    True
    """
    return (self.data == value or
            (self.left and value in self.left) or
            (self.right and value in self.right))

def parenthesize(b):
"""
Return a parenthesized expression equivalent to the arithmetic
expression tree rooted at b.

Assume:  -- b is a binary tree
         -- interior nodes contain data in {'+', '-', '*', '/'}
         -- interior nodes always have two children
         -- leaves contain float data

@param BinaryTree b: arithmetic expression tree
@rtype: str

>>> b1 = BinaryTree(3.0)
>>> print(parenthesize(b1))
3.0
>>> b2 = BinaryTree(4.0)
>>> b3 = BinaryTree(7.0)
>>> b4 = BinaryTree("*", b1, b2)
>>> b5 = BinaryTree("+", b4, b3)
>>> print(parenthesize(b5))
((3.0 * 4.0) + 7.0)
"""
if b is None:
    return ''
else:
    return "("+parenthesize(b.left)+str(b.data)+parenthesize(b.right)+")"

Answer 1

您似乎希望您的代码只在附加了操作的节点（树）周围放置括号。在您的评论中，您说

b1 = BinaryTree(3.0)
print(parenthesize(b1))
# 3.0

但是当您运行您的代码时，情况并非如此。相反，输出是 (3.0) 当您的节点是较大表达式的一部分时，这会引入冗余括号。

为了更正这个问题，我在您的函数中添加了一个 elif 子句，如下所示。

def parenthesize(b):
    if b is None:
        return ''
    elif b.left is None and b.right is None:
        return str(b.data)
    else:
        return "("+ parenthesize(b.left)+str(b.data) + parenthesize(b.right)+")

这会产生以下输出：

b1 = BinaryTree(3.0)
b2 = BinaryTree(4.0)
b3 = BinaryTree(7.0)
b4 = BinaryTree("*", b1, b2)
b5 = BinaryTree("+", b4, b3)
print(parenthesize(b5))
# ((3.0*4.0)+7.0)

我想这就是你想要的。您可能想更改 elif 子句以仅检查单边是否为空而不是两边都为空，但我不知道您将如何使用您的代码。例如，是否要允许 3++ 等一元表达式？如果是，你想把它放在 () 中吗？

如何为二叉树写括号？

How to write parentheses for binary tree?

python

tree

binary-tree

python-3.x