嘗試從樹中按順序打印字符串時遇到問題

Question

我想將一棵樹變成一個字符串並獲取prestr的順序（以root開頭，然後沿着所有左邊的節點向右移動）例如：tree（root（左（a）（b））（右（c）（d）））將是「root left ab right cd」。

class TreeNode: 
def __init__(self, data = None): 
    self.data = data 
    self.children = [] 

class Tree: 
def __init__(self, string = None): 
    self.root = None 

def prestr(self): 
    string1 = "" 
    value = self.root 
    string1 += value.data 
    string1 += " " 
    while len(value.children) > 0: 
     for i in value.children: 
      string1 += i.data 
      string1 += " " 
      value = i 
    print(string1) 

這與

tree (root (left (a) (b)) (right (c) (d))) 

運行此代碼時，我得到："root left right c d"。我懷疑這是因爲它不會在value.children[0]上運行for i in value.children，當它被設置爲值但我不知道爲什麼。這裏有什麼問題？

Answer 1

您的代碼存在的問題是您在for循環中設置了value = i。當你這樣做時，你希望你的代碼回到while ...:，但它不是不是，而是它轉到for循環的下一次迭代。這樣做的結果是，在實際繼續此值之前，您將值設置爲for循環中節點的最後一個孩子。這會跳過每個節點的最後一個孩子，這就是爲什麼你看到了你的行爲。爲了保持儘可能接近，同時糾正你原來的解決方案，我會建議使用遞歸此代碼，而不是，因爲它是非常容易在這種情況下，來思考：

def prestr_helper(value): 
    if len(value.children) > 0: 
     return value.data + ' ' + \ 
      ' '.join(prestr_helper(child) for child in value.children) 
    else: 
     return value.data 

def prestr(self): 
    print(prestr_helper(self.root)) 

然而，這確實有問題Python的遞歸限制，因此會在深度爲1000或更多（大約）的樹上失敗。爲了規避這個限制，你必須實現一個迭代的解決方案，例如here。