Skip to main content
 首页 » 编程设计

python之递归二叉搜索树 Python

2024年12月31日10zhengyun_ustc

我想在 python 中实现一个包含元素、左右子节点和父节点的二叉搜索树。

class BSTNode: 
""" An internal node for a BST .    """ 
 
def __init__(self, item): 
    """ Initialise a BSTNode on creation, with value==item. """ 
    self._element = item 
    self._leftchild = None 
    self._rightchild = None 
    self._parent = None 
 
 
 
def __str__(self): 
    node = self 
 
    if node != None: 
        s = str(node._element) 
        if node._leftchild:  
            node._leftchild.__str__() 
            s = str(node._element) 
            s+= ' ' 
        elif node._rightchild: 
            node._rightchild.__str__() 
            s += str(node._element) 
        else: 
            return s 
    else: 
        return '' 
 
 
def add(self, item): 
    node = self 
    if node: 
        if item <node._element : 
            if node._leftchild is None: 
                node._leftchild = BSTNode(item) 
                node._leftchild._parent = node 
            else: 
                node._leftchild.add(item) 
        elif item > node._element: 
            if node._rightchild is None: 
                node._rightchild = BSTNode(item) 
                node._rightchild._parent = node 
            else: 
                node._rightchild.add(item) 
 
 
tree = BSTNode(3); 
tree.add(7); 
 print(tree.__str__()); 

我写了这个程序,但是当我运行它时,它没有输出,但它应该输出 3 7(顺序是中序遍历)。有谁知道我做错了什么?

请您参考如下方法:

您的__str__ 方法不正确。具体来说,您调用左右 child 的 __str__() 但不对结果做任何事情。另请注意,一个节点可以有两个 左右子节点(if...elif 将只检查一个)。如果您点击了您的 if 或 elif block 之一,您也不会不返回 s。

您可以将其简化为:

def __str__(self): 
    node = self 
    if node != None: 
        s = str(node._element) 
        if node._leftchild:  
            s = node._leftchild.__str__() + s 
        if node._rightchild: 
            s += ' ' + node._rightchild.__str__() 
        return s 
    return ''