0

这是一个具有额外功能的堆节点；基于模2的“负载平衡”：

#! /usr/bin/env python
class Lifo:
  def __init__(self):
    # repr using tuple
    self.lifo = ()
  def push(self, data):
    # pack data using tuple
    self.lifo = (data, self.lifo)
  def pop(self): 
    # unpack data using tuple
    # raise ValueError when empty
    data, self.lifo = self.lifo
    return data
  def __len__(self):
    return len(self.lifo)
  def __repr__(self):
    return str(self.lifo)


class HeapNode:
  def __init__(self, value, left=None, right=None):
    self.data = value
    self.left = left
    self.right = right

  def __repr__(self):
    if self.left is None and self.right is None:
        return '(%s)'%(self.data)
    repr_left = '*' if self.left is None else repr(self.left)
    repr_right = '*' if self.right is None else repr(self.right)
    return '(%s L%s R%s)'%(self.data, repr_left, repr_right)

  def add(self,data,count):
    # do traversal with stack
    lifo = Lifo()
    lifo.push(self)
    print 'push\'d self is %s, lifo is %s'%(self,lifo)
    while len(lifo) > 0 :
        # self's modified here
        self = lifo.pop()
        print 'popp\'d self is %s, lifo is %s'%(self,lifo)
        if count % 2 == 0 :
            if self.right is None:
                self.right = HeapNode(data)
            else:
                lifo.push(self.right)
        else:
            if self.left is None:
                self.left = HeapNode(data)
            else:
                lifo.push(self.left)
    print 'returning self is %s'%(self,)
    return self

if __name__ == '__main__':
    heap = HeapNode(11)
    heap.add(7,0).add(4,1).add(10,2)

输出：

push'd self is (11), lifo is ((11), ())
popp'd self is (11), lifo is ()
returning self is (11 L* R(7))
heap [(11 L* R(7))]
push'd self is (11 L* R(7)), lifo is ((11 L* R(7)), ())
popp'd self is (11 L* R(7)), lifo is ()
returning self is (11 L(4) R(7))
heap [(11 L(4) R(7))]
push'd self is (11 L(4) R(7)), lifo is ((11 L(4) R(7)), ())
popp'd self is (11 L(4) R(7)), lifo is ()
popp'd self is (7), lifo is ()
returning self is (7 L* R(10))
heap [(11 L(4) R(7 L* R(10)))]

上述情况是如何发生的，即self（在 add 函数内）是(7 L* R(10)但引用了堆(11 L(4) R(7 L* R(10)))？

我明白，如果它是主要的：heap = heap.add_stack(10,2)那么，返回值是堆。

但我不明白的是什么是添加元素11 L(4)，(7 L* R(10))是不是一些引用和值传递导致了这个？

有人可以解释清楚吗？

4

1 回答 1

0

您的add方法似乎等同于这个递归版本：

def add(self, data, count):
    if count % 2:
        if self.right is None:
            self.right = HeapNode(data)
            return self # note, returning the node before the new leaf
        else:
            return self.right.add(data, count) # recurse
    else:
        if self.left is None:
            self.left = HeapNode(data)
            return self
        else:
            return self.left.add(data, count) # recurse

由于那是“尾递归”，它可以很容易地转换成一个迭代版本，它看起来很像你已经拥有的。请注意，尽管不需要堆栈，因为current在任何给定时间都只有一个值（您永远不会在没有中间的情况下调用push两次pop）：

def add(self, data, count):
    current = self # lets use a different variable name rather than rewriting self
    while True: # loop until broken by a return
        if count % 2:
            if current.right is None:
                current.right = HeapNode(data)
                return current
            else:
                current = current.right
        else:
            if current.left is None:
                current.left = HeapNode(data)
                return current
            else:
                current = current.left

我已经避免了您的代码中重新绑定self变量名的陷阱，这可能会非常令人困惑。self将调用该方法的对象保留为对象，并为我们当前正在处理的对象使用不同的名称，这是一个更好的主意。

我怀疑这个实现中存在一个潜伏的错误，并且您想count在每个递归步骤上进行修改（也许除以二？），但是如果没有更好地了解您的代码应该做什么，我真的不知道当然。

我认为您感到困惑的是返回值如何与链式调用交互。返回的值始终是到达的最后一个非叶节点。因此，如果您先调用node.add(a, b)，然后单独调用node.add(c, d)，您可能会得到与一次性调用不同的结果node.add(a, b).add(c, d)。原因是在第一种情况下node变量不会改变，而add被调用的对象在链式版本中的两个调用之间可能不同。第二个版本等价于：

temp = node.add(a, b)
temp.add(c, d)
del temp

如果您希望链式调用的结果与对根节点上函数的重复调用相同，那么您需要更改代码以始终返回根元素，而不是递归或迭代遍历的结果。在代码的递归版本中，只返回self而不是返回递归调用的结果。在迭代版本中，返回self而不是current.

或者你可以取消所有链接而不返回任何东西（这在 Python 中等同于返回None）。这可能是最“Pythonic”的解决方案（类似的方法list.append不set.add返回任何东西）。

编辑：这是输出的解释。

您从单个节点开始(11)。第一步是你add用参数7和0. 该调用负责输出的前三行：

push'd self is (11), lifo is ((11), ())
popp'd self is (11), lifo is ()
returning self is (11 L* R(7))

根节点将自己推送到您的堆栈上，然后再次弹出。创建了一个新节点(7)，并将其添加为(11)将其转换为的右子节点(11 L* R(7))。

我不确定你的输出的下一行来自哪里：

heap [(11 L* R(7))]

您显示的任何代码都不会打印它，因此我将忽略它（以及稍后的类似行）。

第一个add调用返回被调用的 on，然后你调用 nextadd就可以了。它仍然是同一个节点，所以链接还没有做任何棘手的事情。该add调用有参数4，1并产生另外三行输出：

push'd self is (11 L* R(7)), lifo is ((11 L* R(7)), ())
popp'd self is (11 L* R(7)), lifo is ()
returning self is (11 L(4) R(7))

这次它将新节点添加为根节点(4)的左子节点。否则同上。第三个 add 再次在同一个节点上调用，但这次它做了更多的工作。我将逐行解释这次发生的事情。

push'd self is (11 L(4) R(7)), lifo is ((11 L(4) R(7)), ())
popp'd self is (11 L(4) R(7)), lifo is ()

前两行与我们目前看到的相同，因为根节点被推送然后从堆栈中弹出。但是，这一次代码看到self节点上已经有一个正确的孩子，所以它推送那个孩子并再次循环。请注意，这一秒push没有任何print关联的语句，因此看起来您没有相同数量的推送和弹出。但是，如果您通过逻辑工作，每次通过循环时总会有一个。

popp'd self is (7), lifo is ()
returning self is (7 L* R(10))

弹出下一个节点后，self现在是该(7)节点，而不是每隔一次运行时的根节点。添加一个新(10)节点作为其右子节点，并且该节点（现在(7 L* R(10))返回。此时您的链接可能会开始表现得很奇怪。如果您链接了另一个添加，它将应用于返回的节点，而不是root 像以前一样。因此，如果您从(0)变量中的节点开始heap，则heap.add(1,0).add(2,1).add(3,2).add(4,3)行为会很奇怪：heap会变成(0 L(2) R(1 L(4) R(3)))，而不是(0 L(2 L(4) R*) R(1 L* R(3)))如果您没有链接调用会得到什么。

于 2013-05-28T23:31:06.213 回答