python - 如果两个 Tree 具有相同的值节点，则使用 set 计数

问题描述

在“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 我希望在我的 set() 中看到

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

如果我的“其他”树是 t2 我希望在我的 set() 中看到

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

但我的 t2 代码输出是

my set() = {6, 7}

（顺便说一下，python 中的 set() 是否应该默认对值进行排序？）

请帮忙。

标签： pythonpython-3.x

python - 如果两个 Tree 具有相同的值节点，则使用 set 计数

问题描述

解决方案

推荐阅读