python - Python 中的二叉树计数范围内的节点

Question

我有一个二叉树的简单实现:

class Node:
    def __init__(self, item, left = None, right = None):
        self.item = item
        self.left = left
        self.right = right

class BST:
    def __init__(self):
        self.root = None

    def add(self, item):
        if self.root == None:
            self.root = Node(item, None, None)
        else:
            child_tree = self.root
            while child_tree != None:
                parent = child_tree
                if item < child_tree.item:
                    child_tree = child_tree.left
                else:
                    child_tree = child_tree.right
            if item < parent.item:
                parent.left = Node(item, None, None)
            elif item > parent.item:
                parent.right = Node(item, None, None)

我想添加 count(lo,hi) 方法来计算 range(lo,hi) 中的所有节点(包括 hi)这是我目前所拥有的:

def count(self, lo, hi, ptr='lol', count=0):
    if ptr == 'lol':
        ptr = self.root
    if ptr.left != None:
        if ptr.item >= lo and ptr.item <= hi:
            count += 1
        ptr.left = self.count(lo, hi, ptr.left, count)
    if ptr.right != None:
        if ptr.item >= lo and ptr.item <= hi:
            count += 1
        ptr.right = self.count(lo, hi, ptr.right, count)
    return count

它似乎只在二叉树向右倾斜或向左倾斜时起作用。它不适用于平衡树，我不知道为什么。我的输入是:

bst = BST()
for ele in [10, 150, 80, 40, 20, 10, 30, 60, 50, 70, 120, 100, 90, 110, 140, 130, 150]:
    bst.add(ele)
print(bst.count(30, 100))

我的代码给了我 output: 0 但它应该是 output: 8。你能告诉我哪里出错了吗？

Answer 1

错误的部分:

   while child_tree != None:
        if child_tree.item >= lo and child_tree.item <= hi:
            count += 1
        if hi > child_tree.item:  # from here
            child_tree = child_tree.right
        else:
            child_tree = child_tree.left . # to here

如果 child_tree 介于 low 和 hi 之间，您应该递归地迭代两个 左右子节点 - 并且您只迭代正确的子节点。

提示:由于您需要同时检查左右 child ，因此应该进行递归调用...

更新

def count(self, lo, hi, ptr, count=0):
    if not ptr:
        return 0
    elif lo <= ptr.item <= hi:
        return 1 + self.count(lo, hi, ptr.left, count) + \
               self.count(lo, hi, ptr.right, count)
    elif ptr.item < lo:
        return self.count(lo, hi, ptr.right, count)
    elif ptr.item > hi:
        return self.count(lo, hi, ptr.left, count)