基本上......我试图让我的“计数”方法来计算树中有多少个节点......但是递归不起作用......我该怎么做？
'''
Created on Jul 11, 2013
To practice building native recursion things
@author: bailey
'''
class AllWords :
def __init__(self):
self.my_tree = Tree()
def add(self, fresh_word):
self.my_tree.insert(fresh_word)
def __str__(self):
return str(self.my_tree)
class Tree :
def __init__(self):
self.root = Blob()
self.size = 0 # initialising size to be zero
self.tutti = "" # to hold all content data
self.left_edges = 0
self.right_edges = 0
self.x = 0
self.b = 0
def __str__(self):
if self.is_empty() :
return "This tree is empty"
else : # so the tree at least has something in the root
self.tutti += "This tree has depth = " + str(self.get_depth())
self.tutti += ", and contains the " + str(self.size) + " objects:\n"
self.tutti += ", and has " + str(self.x) + " nodes \n"
self.tutti += "This tree has " + str(self.left_edges) + " edges on left.\n"
self.tutti += "This tree has " + str(self.right_edges) + " edges on right.\n"
self.tutti += "This tree has " + str(self.edge_stats()) + " edges in total.\n"
self.grab_everything(self.root) # start at the root
return self.tutti
def grab_everything(self, my_blob):
if not my_blob.left_is_empty() : # if there's something on the left
self.grab_everything(my_blob.left)
self.tutti = self.tutti + str(my_blob.data) + ", " # update tutti
if not my_blob.right_is_empty() : # if there's something on the right
self.grab_everything(my_blob.right)
def is_empty(self):
return self.size == 0
def insert(self, something):
if self.is_empty() : # put the something at the root
self.root = Blob(something)
self.size = 1
else : # find where to put it by starting search at the root
self.insert_at_blob(something, self.root)
self.size += 1
def insert_at_blob(self, something, blob):
if something < blob.data : # look left
if blob.left_is_empty() :
blob.set_left( Blob(something) )
else : # keep looking to the left
self.insert_at_blob(something, blob.left)
else : # look right
if blob.right_is_empty() :
blob.set_right( Blob(something) )
else : # keep looking to the right
self.insert_at_blob(something, blob.right)
def get_depth(self): # depth is max number of edges from root outwards
if self.is_empty() :
return -1 # my choice of answer if there's nothing there
else : # note: will define a root-only tree to have depth 0
return self.get_subdepth(self.root)
def get_subdepth(self, blob):
if not blob.left_is_empty() :
left_depth = self.get_subdepth(blob.left)
else :
left_depth = -1 # since that node is empty
if not blob.right_is_empty() :
right_depth = self.get_subdepth(blob.right)
else :
right_depth = -1 # since that node is empty
return max(left_depth, right_depth) + 1
def count_left_only(self):
if not self.root.left_is_empty():
self._count_left_only(self.root.left)
else :
print("There are no left edges.")
def _count_left_only(self, blob):
if not blob.left_is_empty():
self._count_left_only(blob.left)
self.left_edges += 1
def count_right_only(self):
if not self.root.right_is_empty():
self._count_right_only(self.root.right)
else :
print("There are no right edges.")
def _count_right_only(self, blob):
if not blob.right_is_empty():
self._count_right_only(blob.right)
self.right_edges += 1
def edge_stats(self):
return self.left_edges + self.right_edges
def count(self, blob):
if blob == None:
return(0)
if not blob.left_is_empty()and not blob.right_is_empty():
self.x = self.x + 1
else:
return (1 + self.count(blob.left) + self.count(blob.right))
class Blob : # a node class to hold data in a binary tree
def __init__(self, data=None, left=None, right=None):
self.data = data
self.left = left
self.right = right
def set_data(self, thing):
self.data = thing
def set_left(self, blob):
self.left = blob
def set_right(self, blob):
self.right = blob
def left_is_empty(self):
return self.left is None
def right_is_empty(self):
return self.right is None
def __str__(self):
return str(self.data)
import Searching
tout = Searching.AllWords()
tout.add(20)
tout.add(15)
tout.add(35)
tout.add(17)
tout.add(33)
tout.add(12)
tout.add(43)
tout.my_tree.count(tout)
tout.my_tree.count_right_only()
tout.my_tree.count_left_only()
print( str(tout) )
我得到 0 但我应该得到 7