二叉搜索树查找最小值不清楚

Question

我试过的逻辑：

 def min_tree_value(self):
        
       while self.left:
            self.left = self.left.left
        
        return self.data

实际Python程序逻辑：

def min_tree_value(self):
        if self.left is None:
            return self.data
        
        return self.left.min_tree_value()

实际的Python程序逻辑是递归形式。我在 While loop()

中尝试了相同的逻辑

我不确定我的逻辑是否正确。帮我找出不正确的逻辑并指出我错的地方。

Answer 1

你的逻辑差不多了，但不完全是：

def min_tree_value(self):
    node = self
    while node.left:
        # don't change the structure by rebinding node.left,
        # but iterate the tree by moving along nodes!
        node = node.left  
    return node.data

请注意，在原始代码中，您从未在返回其值之前重新分配 self，因此您始终返回根值。

Answer 2

首先，题目问的是求二叉树中的最小元素

您使用的算法将找到二叉搜索树中的最小元素（因为最左边的元素是最小元素）。

要在简单二叉树中找到最小元素，请使用以下算法：

# Returns the min value in a binary tree 

def find_min_in_BT(root): 
    if root is None: 
        return float('inf') 
    res = root.data 
    lres = find_min_in_BT(root.leftChild) 
    rres = find_min_in_BT(root.rightChild) 
    if lres < res: 
        res = lres 
    if rres < res: 
        res = rres 
    return res

OP改题后答案补充：

您尝试的算法的逻辑是正确的，在实现中有一个小的修正：self = self.data。他们都找到了最左边的元素。

我也测试了return相同输出的两个函数：

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data


    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def findval(self, lkpval):
        if lkpval < self.data:
            if self.left is None:
                return str(lkpval)+" Not Found"
            return self.left.findval(lkpval)
        elif lkpval > self.data:
            if self.right is None:
                return str(lkpval)+" Not Found"
            return self.right.findval(lkpval)
        else:
            print(str(self.data) + ' is found')

    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

    def min_tree_value_original(self):
        if self.left is None:
            return self.data
        return self.left.min_tree_value_original()

    def min_tree_value_custom(self):
        
        while self.left:
            self = self.left
        return self.data 
    
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
root.insert(3)
root.insert(1)
root.insert(0)
root.insert(-1)
root.insert(-2)

print(root.min_tree_value_original())
print(root.min_tree_value_custom())

输出：

-2
-2

这里-2是BST中最小最左边的元素

二叉搜索树查找最小值不清楚

Binary Search Tree Find minimum not clear

python

algorithm

data-structures

binary-search-tree

我试过的逻辑：

实际Python程序逻辑：