薩姆在樹

Question

例如，像這樣的樹：

5 
/\ 
    3 6 
/\ 
7 2 

print(tree.branchLenSum()) 

將1+1+2+2=6

樹類：

class BinaryTree: 

    # Constructor, takes in new key value 
    def __init__(self, myKey): 
     self.key = myKey 
     self.leftChild = None 
     self.rightChild = None 

    # Returns root key value 
    def getRootValue(self): 
     return self.key 

    # Changes root key value 
    def setRootValue(self, newKey): 
     self.key = newKey 

    # Returns reference to left child 
    def getLeftChild(self): 
     value=None 
     if self.leftChild!=None: 
      value=self.leftChild 
     return value 

    # Returns reference to right child 
    def getRightChild(self): 
     value=None 
     if self.rightChild!=None: 
      value = self.rightChild 
     return value 

    def insertLeftChild(self, childKey): 
     newNode = BinaryTree(childKey) 
     newNode.leftChild = self.leftChild 
     self.leftChild = newNode 

    # Inserts key as right child. Existing right child becomes new right child 
    # of new key 
    def insertRightChild(self, childKey): 
     newNode = BinaryTree(childKey) 
     newNode.rightChild = self.rightChild 
     self.rightChild = newNode 

的我爲此構建的樹：

tree=BinaryTree(5) 
tree.insertLeftChild(3) 
tree.insertRightChild(6) 
nodeA=tree.getLeftChild() 
nodeA.insertLeftChild(7) 
nodeA.insertRightChild(2) 

我有什麼至今：

def branchLenSum(self): 
    rounds=0 
    if self.getLeftChild() ==None and self.getRightChild()==None: 
     return rounds+rounds+1 
    else: 
     rounds+=rounds+1 
     if self.getLeftChild()!=None: 
      rounds+=self.getLeftChild().branchLenSum() 
     if self.getRightChild()!=None: 
      rounds+=self.getRightChild().branchLenSum() 
     return rounds 

我的想法是，每一次旅行到下一個節點，計數器加1 +計數器本身。我想這會得到所有長度的總和。

Answer 1

好的，所以你只得到5的結果的原因很簡單：你在做什麼是計數節點。所以在你的情況下，你有5個節點，所以結果是5.

如果你想獲得內部路徑長度，那麼我相信你將不得不跟蹤當前深度，同時瀏覽樹。您只需使用可選參數即可完成此操作。

def branchLenSum(self, depth = 0): 
    rounds = depth 
    if self.leftChild: 
     rounds += self.leftChild.branchLenSum(depth + 1) 
    if self.rightChild: 
     rounds += self.rightChild.branchLenSum(depth + 1) 
    return rounds 

在這種情況下，當我們瀏覽到一個孩子，我們由一個增加當前深度。當計算節點的分支長度時，我們從深度開始。

Btw。注意，正式地，內部路徑長度被定義爲僅用於內部節點的長度，即不是葉子。上面的方法計算每個包含樹葉的節點。如果您想遵循官方定義，您必須在開始時添加葉檢查並將葉子返回0。

---

一些其他的事情：

• 的方法getLeftChild和getRightChild做有效一無所獲。您將None指定爲返回值，然後檢查左/右子項是否爲None，如果不是這種情況，則將子項分配給返回值並將其返回。

  所以，基本上，你正在返回​​/self.rightChild;沒有必要真正查看價值並檢查None。

• 在Python中，您通常不使用存取器或增變器方法（getter/setter）;你只需訪問底層屬性本身。這使得方法getLeftChild，getRightChild，getKey和setKey冗餘。

• 檢查None與!= None或== None是反模式。如果你想檢查，例如一個孩子是不是None，只需要if child。如果你想檢查它是否沒有設置（即不是None），只需要做if not child。