递归方法调用Python BST高度实现

Question

我正在用py实现一个BST类。不幸的是，我的身高方法没有提供正确的结果。尝试t1.height（）时，我得到的结果是3，而不是预期的4。 我怀疑部分问题可能是递归的终止条件，特别是self.right/left==None检查。但是，我必须这样做，因为在None叶上调用height（）将导致错误，因为None还不是Node的实例

class Node: 
    # Implement a node of the binary search tree.
    # Constructor for a node with key and a given parent
    # parent can be None for a root node.
    def __init__(self, key, parent = None): 
        self.key = key
        self.parent = parent 
        self.left = None # We will set left and right child to None
        self.right = None
        # Make sure that the parent's left/right pointer
        # will point to the newly created node.
        if parent != None:
            if key < parent.key:
                assert(parent.left == None), 'parent already has a left child -- unable to create node'
                parent.left = self
            else: 
                assert key > parent.key, 'key is same as parent.key. We do not allow duplicate keys in a BST since it breaks some of the algorithms.'
                assert(parent.right == None ), 'parent already has a right child -- unable to create node'
                parent.right = self
        
    # Utility function that keeps traversing left until it finds 
    # the leftmost descendant
    def get_leftmost_descendant(self):
        if self.left != None:
            return self.left.get_leftmost_descendant()
        else:
            return self
    
    # TODO: Complete the search algorithm below
    # You can call search recursively on left or right child
    # as appropriate.
    # If search succeeds: return a tuple True and the node in the tree
    # with the key we are searching for.
    # Also note that if the search fails to find the key 
    # you should return a tuple False and the node which would
    # be the parent if we were to insert the key subsequently.
    def search(self, key):
        #print("entering search key= ",key," from node= ",self.key)
        if self.key == key: 
            return (True, self)
        # your code here
        elif self.key == None:
            return (False, self)
        elif key < self.key:
            #print('searching left')
            if self.left == None:
                return (False, self)
            else:
                return self.left.search(key)
        elif key > self.key:
            #print('searching right')
            if self.right == None:
                return (False, self)
            else:
                return self.right.search(key)
            
    #TODO: Complete the insert algorithm below
    # To insert first search for it and find out
    # the parent whose child the currently inserted key will be.
    # Create a new node with that key and insert.
    # return None if key already exists in the tree.
    # return the new node corresponding to the inserted key otherwise.
    def insert(self, key):
        # your code here
        # search for the spot to insert to        
        if self.search(key)[0] == True:
            #print('key already exists')
            return None
        else:
            return Node(key, self.search(key)[1])
       
    # TODO: Complete algorithm to compute height of the tree
    # height of a node whose children are both None is defined
    # to be 1.
    # height of any other node is 1 + maximum of the height 
    # of its children.
    # Return a number that is th eheight.
    def height(self):
        # your code here
        if self == None:
            return 1
        elif self.right == None:
            return 1
        elif self.left == None:
            return 1

        leftheight = self.left.height()
        rightheight = self.right.height()
        
        return max(leftheight, rightheight) + 1

t1 = Node(25, None)
t2 = Node(12, t1)
t3 = Node(18, t2)
t4 = Node(40, t1)

print('-- Testing basic node construction (originally provided code) -- ')
assert(t1.left == t2), 'test 1 failed'
assert(t2.parent == t1),  'test 2 failed'
assert(t2.right == t3), 'test 3 failed'
assert (t3.parent == t2), 'test 4 failed'
assert(t1.right == t4), 'test 5 failed'
assert(t4.left == None), 'test 6 failed'
assert(t4.right == None), 'test 7 failed'
# The tree should be : 
#             25
#             /\
#         12     40
#         /\
#     None  18
#

print('-- Testing search -- ')
(b, found_node) = t1.search(18)
assert b and found_node.key == 18, 'test 8 failed'
(b, found_node) = t1.search(25)
assert b and found_node.key == 25, 'test 9 failed -- you should find the node with key 25 which is the root'
(b, found_node) = t1.search(26)
assert(not b), 'test 10 failed'
assert(found_node.key == 40), 'test 11 failed -- you should be returning the leaf node which would be the parent to the node you failed to find if it were to be inserted in the tree.'

print('-- Testing insert -- ')
ins_node = t1.insert(26)
assert ins_node.key == 26, ' test 12 failed '
assert ins_node.parent == t4,  ' test 13 failed '
assert t4.left == ins_node,  ' test 14 failed '

ins_node2 = t1.insert(33)
assert ins_node2.key == 33, 'test 15 failed'
assert ins_node2.parent == ins_node, 'test 16 failed'
assert ins_node.right == ins_node2, 'test 17 failed'



print('-- Testing height -- ')

print('height t1= ',t1.height())
assert t1.height() == 4, 'test 18 failed'
assert t4.height() == 3, 'test 19 failed'
assert t2.height() == 2, 'test 20 failed'

Answer 1

def height(self):
    # your code here
    if self == None:
        return 0
    elif self.right == None and self.left == None:
        return 1
    elif self.left == None:
        return 1 + self.right.height()
    elif self.right == None:
        return 1 + self.left.height()

    leftheight = self.left.height()
    rightheight = self.right.height()
    
    return max(leftheight, rightheight) + 1

Answer 2

高度的标准定义（作为函数，而不是方法）是

def height(node):
    if node == None:
       return 0
    else:
       return 1 + max(height(node.left), height(node.right))

请注意node是一个参数，因此您可以轻松处理“空”情况

在您的代码中，如果node.left是None，那么您希望返回1 + height(node.right)。同样，对于ifnode.right也是无的