我試圖理解二元函式中的遞回呼叫is_bst。該函式的目標是檢查一棵樹是否是二叉搜索樹。請注意，這只是完整功能的摘錄。我試圖了解函式中這段代碼is_bst_l, min_l, max_l = is_bst(node.left)中發生了什么is_bst。該is_bst函式回傳(True, None, None)，我試圖找出函式如何通過該函式去遞回地回傳值上來。該is_bst函式將函式中的二叉樹節點作為輸入 parse_tuple。例如，當我嘗試is_bst_l, min_l, max_l = node.left在is_bst函式外解壓這行代碼時，我得到了TypeError: cannot unpack non-iterable TreeNode object，但在函式內，我沒有收到錯誤訊息。我的問題是
is_bst函式內遞回發生的事情。- 我怎么能在
is_bst函式中沒有解包 TypeError 。
`
#Tree Class
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
#function converts a turble to a binary tree
def parse_tuple(data):
# print(data)
if isinstance(data, tuple) and len(data) == 3:
node = TreeNode(data[1])
node.left = parse_tuple(data[0])
node.right = parse_tuple(data[2])
elif data is None:
node = None
else:
node = TreeNode(data)
return node
函式 檢查一棵樹是否是二叉搜索樹。
def remove_none(nums):
return [x for x in nums if x is not None]
def is_bst(node):
if node is None:
return True, None, None
is_bst_l, min_l, max_l = is_bst(node.left)
is_bst_r, min_r, max_r = is_bst(node.right)
is_bst_node = (is_bst_l and is_bst_r and
(max_l is None or node.key > max_l) and
(min_r is None or node.key < min_r))
# print('Minkey left: ', min_l, 'Nodekey :', node.key, 'Maxkey left: ',min_r)
# print('Minkey left: ', max_l, 'Nodekey :', node.key, 'Maxkey left: ',max_r)
min_key = min(remove_none([min_l, node.key, min_r]))
max_key = max(remove_none([max_l, node.key, max_r]))
# print(node.key, min_key, max_key, is_bst_node)
return is_bst_node, min_key, max_key
#函式呼叫
my_tuple= ((None,3,None),2,(None,5,None))
node = parse_tuple(my_tuple)
uj5u.com熱心網友回復：
如果對每個節點遞回，樹是 BST：
- 如果它存在，它的左樹是一個 BST
- 如果它存在，它的右樹是一個 BST
- 左樹的最大值，如果存在，必須小于節點的值
- 右樹的最小值，如果存在，必須大于節點的值
因此，對于三個值的元組的回傳值是有意義的：
- 我是 BST 嗎？
- 我的子樹中最小的節點是什么
- 我的子樹中最大的節點是什么。
uj5u.com熱心網友回復：
該函式正在回傳當前節點左右兩側的最大和最小鍵（除了檢查的真/假結果）。它的遞回從左節點和右節點組裝這些鍵/有效性狀態，從而創建管理（即排除）來自子節點回傳值的 None 結果的需要。
這過于復雜，可能不值得您花時間分析和理解。
我想你會發現這個更簡單一點：
def is_bst(node,minKey=None,maxKey=None):
if node is None: return True
if minKey is not None and node.key<=minKey: return False
if maxKey is not None and node.key>=maxKey: return False
if not is_bst(node.left,minKey,self.key): return False
if not is_bst(node.right,self.key,maxKey): return False
return True
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/344889.html
上一篇：不理解C中的遞回函式
下一篇：如何在APL中進行相互遞回？