如果两个Tree具有相同的值节点,则使用set来计数

Question

在"def same_child_values"中.我试图比较两个树,看看另一棵树是否具有与主tree.children相同的值节点.在这种情况下,我使用一组来比较它们.但是在我的代码中,当树深度大于1时,我的代码无法正确地将节点添加到集合中.谁能帮我？

class Tree:
      '''Tree ADT; nodes may have any number of children'''

  def __init__(self: 'Tree',
               item: object =None, children: list =None):
    '''Create a node with item and any number of children'''

    self.item = item
    if not children:
      self.children = []
    else:
      self.children = children[:]

  def __repr__(self: 'Tree') -> str:
    '''Return representation of Tree as a string'''

    if self.children:
      return 'Tree({0}, {1})'.format(repr(self.item), repr(self.children))
    else:
      return 'Tree({})'.format(repr(self.item))

  def is_leaf(self: 'Tree') -> bool:
    '''Return True iff this Tree node is a leaf (has no children).'''

    return self.children == []

  def remove_equal(self: 'Tree') -> None:
    '''Remove every child that has the same item as its parent;
    any children of a removed node n become children of an ancestor of n.

    >>> t = Tree(1, [Tree(2, [Tree(1), Tree(2)]), Tree(1)])
    >>> t.remove_equal()
    >>> repr(t)
    'Tree(1, [Tree(2, [Tree(1)])])'
    >>> t = Tree(4, [Tree(4, [Tree(6)])]) 
    >>> t.remove_equal()
    >>> repr(t)
    'Tree(4, [Tree(6)])'
    >>> t = Tree(4, [Tree(4, [Tree(4, [Tree(4)])])])
    >>> t.remove_equal()
    >>> repr(t)
    'Tree(4)'
    >>> t = Tree(4, [Tree(4, [Tree(4, [Tree(6), Tree(7)]), Tree(8)]), Tree(9)])
    >>> t.remove_equal()
    >>> repr(t)
    'Tree(4, [Tree(6), Tree(7), Tree(8), Tree(9)])'
    '''
    new_children = []
    for c in self.children:
      c.remove_equal()
      if not c.item == self.item:
        new_children.append(c)
      else:
        new_children.extend(c.children)
    self.children = new_children



    # Q1: Complete this method (This was the last part of last week's lab.
    # If you did not have a chance to finish it last week, work on it today.)

这是我需要完成的功能

  def same_child_values(self: 'Tree', other: 'Tree') -> None:
    '''
    Return True iff the other tree node given has all the same values for its children.
    The values do not have to occur the same number of times.
    We are only looking at values of the immediate children, not the descendants.

    Hint: Use sets to compare a list of all children keys
    More on sets - https://www.programiz.com/python-programming/set

    >>> t = Tree(4, [Tree(6), Tree(7), Tree(8), Tree(9)])
    >>> t2 = Tree(5, [Tree(6), Tree(7, [Tree(8, [Tree(9)])])])
    >>> t3 = Tree(6, [Tree(7), Tree(8), Tree(6), Tree(6), Tree(9)])
    >>> t4 = Tree(7, [Tree(7), Tree(7), Tree(6)])
    >>> t.same_child_values(t2)
    False
    >>> t.same_child_values(t3)
    True
    >>> t4.same_child_values(t2)
    True
    '''
    a = set()
    b = set()

这是我的代码:

    for c in self.children:
      a.add(c.item)
      c.same_child_values(other)
    for d in other.children:
      b.add(d.item)
      self.same_child_values(d)
    return b

如果我的"其他"树是t3我希望在我的集合中看到()

my set() = {8, 9, 6, 7}

如果我的"其他"树是t2我希望在我的集合中看到()

my set() = {8, 9, 6, 7, 5}

但我的t2代码输出是

my set() = {6, 7}

(顺便说一句,python中的set()应该默认对值进行排序吗？)

请帮忙.

Answer 1

这就是你所追求的吗？

def same_child_values(self, other):
        return set([c.item for c in self.children]) == set([c.item for c in other.children])

关键元素在文档字符串中：“我们只查看直接子项的值，而不是后代的值。”