时间戳

首页 > 解决方案 > 我怎样才能结束这个 BST 循环？

python - 我怎样才能结束这个 BST 循环？

问题描述

我正在求解一个给定数字 n 的 BST 算法，我需要返回小于 n 的最大值。不幸的是，一旦我找到了答案。我的代码没有返回它，而是继续循环。我错过了什么？谢谢。

class Node:

# Constructor to create a new node
  def __init__(self, key):
      self.key = key
      self.left = None
      self.right = None
      self.parent = None

# A binary search tree 
class BinarySearchTree:

  # Constructor to create a new BST
  def __init__(self):
      self.root = None

  def find_largest_smaller_key(self, num):
      largest = 0

      while self.root:

        if self.root.key < num and self.root.key > largest:
            largest = self.root.key

        if self.root.right:
          if self.root.right.key < num and self.root.right.key > largest:
            self.root = self.root.right

        if self.root.left:
            if self.root.left.key < num and self.root.left.key > largest:
              largest = self.root.left.key
              self.root = self.root.left
      return largest

标签： pythonalgorithmbinary-search-tree

解决方案

很酷的算法。

想想当不再有左或右时会发生什么：

这可能发生一次，但不再导致最大 == self.root.key 因此不在此处

 if self.root.key < num and self.root.key > largest:
            largest = self.root.key

这不会发生

if self.root.right:

这也不会

if self.root.left:

但

self.root 仍然是真的，所以

  while self.root:

将永远运行

推荐阅读