Python樹操作

Question

我需要實現（或只是使用）我可以執行的樹數據結構：
1.在任何指定位置添加子項。新的孩子本身可以是一棵大樹（不必是單身人士）
2.子樹刪除和移動（到同一樹中的另一個節點）
3.常見的遍歷操作。
4.從子節點訪問父級。

首先，有沒有我可以使用的任何模塊？第二，如果我自己實現這個，我有這個問題：

當我做樹操作像移動子樹，刪除子樹或添加新的子樹時，我只希望將「引用」移動到這些樹節點。例如，在C/C++中，這些操作可以通過指針操作來執行，我可以保證只有引用被移動。
同樣，當我做樹「動作」時，我只需要移動參考 - 又名，樹的新副本而不是將在目的地創建。

我還處於一個「指針」思維框架，因此也是一個問題。可能是，我不需要做這一切？

Answer 1

您可以使用操作符重載輕鬆地創建自己的樹。例如，這裏是__add__一個基本的類實現：

class Node(object): 
    def __init__(self, value): 
     self.value = value 
     self.child = [] 
    def add_child(self, child): 
     self.child.append(child) 
    def __add__(self, element): 
     if type(element) != Node: 
       raise NotImplementedError("Addition is possible only between 2 nodes") 
     self.value += element.value # i didn't get if you have to add also childs 
     return self # return the NODE object 

因此，要回答你的第二個問題，這裏有一個蟒蛇把戲。在__add__您返回self。然後，該返回True：

a = Node(1) 
b = Node(2) 
print a is a + b 

如果使用a + b，這將修改值a。實際上，指針是a和b。然後，如果您將它作爲函數中的參數傳遞，並且您在函數中修改它們，則將修改a和b實例。有兩種不同的方式來避免這種（也許更多，但是這是兩個我使用）：

第一種是直接修改的__add__定義：

def __add__(self, element): 
    # .../... 
    value = self.value + element.value 
    return Node(value) # you may add rows in order to copy childs 

第二個是增加一個copy方法：

def copy(self): 
    # .../... 
    n = Node(self.value) 
    n.child = self.child[:] # Copy the list, in order to have 2 different instance of this list. 
    return n 

這將允許你做這樣的事情c = a.copy() + b和斷言c is a將是錯誤的。

希望我回答你的問題。

Answer 2

氏是一個例子：

類二叉樹：

def __init__(self,rootObj): 
     self.key = rootObj 
     self.leftChild = None 
     self.rightChild = None 

    def insertLeft(self,newNode): 
     if self.leftChild == None: 
      self.leftChild = BinaryTree(newNode) 
     else: 
      t = BinaryTree(newNode) 
      t.leftChild = self.leftChild 
      self.leftChild = t 

    def insertRight(self,newNode): 
     if self.rightChild == None: 
      self.rightChild = BinaryTree(newNode) 
     else: 
      t = BinaryTree(newNode) 
      t.rightChild = self.rightChild 
      self.rightChild = t 


    def getRightChild(self): 
     return self.rightChild 

    def getLeftChild(self): 
     return self.leftChild 

    def setRootVal(self,obj): 
     self.key = obj 

    def getRootVal(self): 
     return self.key