從二叉搜索樹中創建一個列表

我正在嘗試製作二叉搜索樹中所有項目的列表。我理解遞歸，但我不知道如何讓它返回每個值，然後將其附加到列表中。我想創建一個名爲makeList()的函數，它將返回我樹中所有項目的列表。除了makeList()函數之外，我的程序中的所有函數都可以工作，並且可以確保每個人都瞭解我設置樹的基本結構。我makeList()功能從二叉搜索樹中創建一個列表

class Node(object): 
    def __init__(self, data): 
     self.data = data 
     self.lChild = None 
     self.rChild = None 

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

    def __str__(self): 
     current = self.root 

    def isEmpty(self): 
     if self.root == None: 
      return True 
     else: 
      return False 

    def insert (self, item): 
     newNode = Node (item) 
     current = self.root 
     parent = self.root 

     if self.root == None: 
      self.root = newNode 
     else: 
      while current != None: 
       parent = current 
       if item < current.data: 
        current = current.lChild 
       else: 
        current = current.rChild 

      if item < parent.data: 
       parent.lChild = newNode 
      else: 
       parent.rChild = newNode 

    def inOrder(self, aNode): 
     if aNode == None: 
      pass 
     if aNode != None: 
      self.inOrder(aNode.lChild) 
      print aNode.data 
      self.inOrder(aNode.rChild) 

    def makeList(self, aNode): 
     a = [] 
     self.inOrder(aNode) 
     a += [aNode.data] 
     print a 

n = Tree() 
for i in [4,7,2,9,1]: 
    n.insert(i) 

n.makeList(n.root)

尋找我能看到爲什麼它不工作，但我不知道如何使它發揮作用。

編輯

好吧，我知道了！我甚至有兩個答案分別是：

def makeList(self, aNode, a = []): 
    if aNode != None: 
     self.makeList(aNode.lChild, a) 
     a += [aNode.data] 
     self.makeList(aNode.rChild, a) 
    return a

和

def makeList2(self, aNode): 
    if aNode is None: 
     return [] 
    return self.makeList2(aNode.lChild) + [aNode.data] + self.makeList2(aNode.rChild)

，回頭看看我可以看到，我不明白遞歸很好所以現在是時候用功讀書！任何人都有很好的遞歸資源？

另一個問題，所以說我打電話給我的makeList()函數。當Python通過makeList()時，當它到達self.makeList(aNode.lChild, a)時，它是否會開始再次運行該函數，同時它仍然完成了makeList()函數，或者一切都停止，並且它剛從新的aNode重新開始？

我希望這是有道理的。

來源

2011-04-05 crh878

你太親近了！ makeList可以很簡單：

def makeList(self, aNode): 
    if aNode is None: 
     # Stop recursing here 
     return [] 
    return self.makeList(aNode.lChild) + [aNode.data] + self.makeList(aNode.rChild)

基本上，確保你沒有試圖遞歸過去的空節點。然後返回左樹列表，當前節點和右樹列表。

來源

2011-04-05 02:15:46

哈哈你們讓我覺得！我會繼續努力一下，回到你們身邊！ – crh878 2011-04-05 02:21:16

inOrder打印的東西，但不返回任何東西，所以它是沒有用的建立一個列表。您需要一種方式，以便每個節點按順序返回。這可能是您的班級尚未涉及的內容，但請查看yield命令。

來源

2011-04-05 01:21:24

是的，一個迭代器可以很容易地打印樹並從中生成一個扁平化列表，而且對於該類的其他用戶來說通常也是有用的。迭代器++ – kindall 2011-04-05 13:54:55

的基本思路是這樣的：

def makeList(self): 
    return self.lChild.makeList() + [self.data] + self.rChild.makeList()

看看它是如何在本質上是一回事序？

你在程序中有不同的結構，這使得實現起來有點困難，但基本思想是一樣的。

來源

2011-04-05 01:43:31

現在我確實看到它是如何基本相同的。可視化很難。 – crh878 2011-04-05 02:46:41

從二叉搜索樹中創建一個列表

回答

相關問題