Python 中的图形节点

Question

我正在尝试找出编码节点 Class（用于二叉树）的最佳方法，该节点将包含属性 key、left 和 right.

我想我会做类似的事情

class Node:
    def __init__(self, key):
        self.key= key
        self.left = None
        self.right = None

然后

a = Node('A')
b = Node('B') 
c = Node('C')   
a.left = b
a.right = c

在这里我有点困惑：（在引擎盖下）left 和 right 指针？还是 a 包含整棵树的副本？

如果我添加

d = Node('B') # same key as before, but an entirely different node
c.right = d

那么b和d即使属性相同，也是两个不同的对象吗？我会这么认为，因为他们不共享任何内存。

最后，如果我想对我的一个节点进行深拷贝，是

e = Node(a.key))

够了吗？

Answer 1

是的b和d属性相同，但是是两个独立的实例。要查看此内容：

print id(b) # one number
print id(d) # new number

这就证明了它们在内存中是两个不同的对象。要查看 a.right 是与 c 相同的对象，请使用相同的技术，检查等效的 id 值。

print id(a.right)
print id(c) # same

Answer 2

是的，这些只是对左侧或右侧对象的引用。每次执行 Node("some_str)，都会创建一个新对象。所以 b 和 d 会有所不同，并且会为 e = Node(a.key)) 创建一个新对象。 e = Node('E') 和 f = e 是一样的，f 和 e 指的是同一个对象。

Answer 3

Python是动态类型的，所以不能说left和right是引用。还可以存储整数或浮点数。您甚至可以先存储一个整数，然后存储一个对象的引用，然后在其中存储一个浮点数，因此类型可能会随时间变化。但是如果你对一个对象执行赋值。这确实会产生一个指针（这与您的问题在语义上存在巨大差异）。

你的第二个问题，要看你怎么看深拷贝了。如果您的节点包含对其他节点的引用，您是否也想复制这些节点？

如果您只对生成具有相同值但引用相同其他节点的新节点感兴趣，请使用：copy.copy, otherwise use copy.deepcopy.

区别是：

B <- A -> C       B' <- D -> C'
^         ^
|         |
 \-- S --/

使用 S 浅拷贝和 D 深拷贝。请注意，深拷贝会导致新节点 B' 和 C'。您可以想象，如果您深度复制一棵巨大的树，这会导致大量内存和 CPU 占用空间。

您的代码

e = Node(a.key))

不完全正确，因为您没有复制（潜在的）对左右节点的引用，而且它不是好的设计，因为您可以将更多项目附加到节点并且您需要修改复制功能（ s) 每次。因此使用 copy.copy 函数更安全。

Python 中的图形节点

Nodes of a graph in Python

python

class