在Python中計算二進制搜索樹中的節點

我對編程相當陌生，並且想要使用一些二叉搜索樹。我想做一個遞歸計算樹中節點數量的函數，但是，當我運行我的函數時，它似乎不起作用，它會一直返回'none'，就好像我的樹中沒有任何東西。任何人都可以幫我找到問題嗎？在Python中計算二進制搜索樹中的節點

這是我的樹節點類：

class TreeNode(object): 

    def __init__(self, data = None, left=None, right=None): 
     self.item = data 
     self.left = left 
     self.right = right 

    def __str__(self): 
     return str(self.item)

這是我的主要功能，我修剪大部分下跌只是讓我們可以得到執行參考節點的計數問題。

from TreeNode import TreeNode 


class BST(object): 

    #------------------------------------------------------------ 

    def __init__(self): 

     """create empty binary search tree 
     post: empty tree created""" 

     self.root = None 

def treeSize(self, root, size = 0): 

     if root is None: 
      return -1 

     if root is not None: 
      size += 1 
      if root.left is not None: 
       self.treeSize(root.left, size) 
      if root.right is not None: 
       self.treeSize(root.right, size)

這是我用它來測試我的函數的代碼：

from BinarySearchTree import BST 
from TreeNode import TreeNode 

tree = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode (7, TreeNode(6),TreeNode(8))) 

a = BST() 

print(a.postOrder(tree)) 
print(a.treeSize(tree))

當我稱之爲「印（a.treeSize（樹））」這只是返回「無」，而不是' 7'就像它應該。

來源

2015-03-30 Cooper

我明白了。你認爲大小將會在被調用函數中得到更新。它不會像每個功能的本地一樣。您可以撥打global，但這不是最佳選擇。

你可以將它設置爲一個成員變量（實際上並沒有這樣說）：

def __init__(self): 
    ... 
    self.size = 0 

def treeSize(self,...): 
    ... 
    self.size += 1 
    ... 
    return self.size

但明顯的bug是self.size將在每次的TreeSize被調用時的兩倍。你也可以解決這個問題，但讓我們使用我們所知道和喜歡的模式。像VHarisop寫的那樣，這是一種很好的舊遞歸方式。

來源

2015-03-30 22:28:18 Jonathan

是的，它現在的作品！非常感謝！我無法相信我忘了給我的功能添加self.size。你是最好的！ – Cooper 2015-03-30 22:31:50

你也可以做到這一點的好老遞歸的方式：

def treeSize(self, root): 

    if root is None: 
     return 0 

    if root is not None: 
     return 1 + self.treeSize(root.left) + self.treeSize(root.right)

喬納森的回答是很好的爲好。

來源

2015-03-30 22:31:01 VHarisop

在Python中計算二進制搜索樹中的節點

回答

相關問題