二叉搜索树 - python中的BST问题

Question

class BST:
    """A Binary Search Tree."""
    def __init__(self: 'BST', container: list =None) -> None:
        """
        Initialize this BST by inserting the items from container (default [])
        one by one, in the order given.
        """
        # Initialize empty tree.
        self.root = None
        # Insert every item from container.
        if container:
            for item in container:
                self.insert(item)
   def insert(self: 'BST', item: object) -> None:
    """
    Insert item into this BST.
    """
    # Find the point of insertion.
    parent, current = None, self.root
    while current:
        if item < current.item:
            parent, current = current, current.left
        else:  # item > current.item
            parent, current = current, current.right
    # Create a new node and link it in appropriately.
    new_node = _BSTNode(item)
    if parent:
        if item < parent.item:
            parent.left = new_node
        else:  # item > parent.item
            parent.right = new_node
    else:
        self.root = new_node

这是我为 BST 类构建的代码，我想实现一个 max_node 函数，该函数可以在不使用递归的情况下找到最大节点，我应该怎么做？

Answer 1

在BST中，最大节点只是最右边的节点，所以从头部开始，继续采取正确的子节点，直到你遇到一个没有正确孩子的节点。这可以很容易地迭代完成（事实上，这可能是我无论如何都会这样做的方式）。

在伪代码中：

max_node = 头部而有右子（max_node）    max_node = max_node.right_child;