找到二叉搜索樹的深度時超出了最大遞回深度

這是我的代碼：

# increase the limit of recursion
import sys
sys.setrecursionlimit(100000)
import numpy as np

# make binary search tree from list
def bst_build(seq):
    binary_search_tree = [seq[0], None, None]
    seq.pop(0)

    def add_child(main, sub):
        if len(sub) != 0:
            if main[0] > sub[0]:
                if main[1] == None:
                    main.pop(1)
                    main.insert(1, [sub[0], None, None])
                    sub.pop(0)
                    add_child(binary_search_tree, sub)
                else:
                    add_child(main[1], sub)
            
            elif main[0] < sub[0]:
                if main[2] == None:
                    main.pop(2)
                    main.insert(2, [sub[0], None, None])
                    sub.pop(0)
                    add_child(binary_search_tree, sub)        
                else:
                    add_child(main[2], sub)
            else:
                sub.pop(0)         
        else:
            pass

    add_child(binary_search_tree, seq)

    return binary_search_tree

# check the correctness
def bst_check(b):
    if b is None: return True
    if b[1] is not None:
        if b[1][0] >= b[0]: return False
        if bst_check(b[1]) == False: return False
    if b[2] is not None:
        if b[2][0] <= b[0]: return False
        if bst_check(b[2]) == False: return False
    return True

# find depth of binary search tree
def bst_depth(b):
    maximum_depth = 0
    current_depth = 0

    def find_depth(tree):
        nonlocal maximum_depth
        nonlocal current_depth

        if len(tree) != 1:
            if tree[1] != None and len(tree[1]) != 1:
                current_depth  = 1
                find_depth(tree[1])
            else:
                tree.pop(1)
                if maximum_depth <= current_depth:
                    maximum_depth = current_depth
                current_depth = 0
                find_depth(b)
        else:
            pass  
    find_depth(b)      

    return maximum_depth

unsorted = list(np.random.randint(0,100,10))
sorted = unsorted.copy()
sorted.sort()

t1 = bst_build(unsorted)
t2 = bst_build(sorted)

print(t1)
print(t2)

print(bst_check(t1), bst_check(t2))
print( bst_depth(t1), bst_depth(t2) )

首先，我從一個串列中創建一個二叉搜索樹，并檢查它是否是二叉搜索樹。

給定串列的第一個元素是根節點，后面的元素成為子節點。None附加到葉節點。

例如呼叫的結果bst_build([4, 2, 1, 3, 6, 5, 7])是：

[4, 
  [2, 
    [1, None, None], 
    [3, None, None]
  ], 
  [6, 
    [5, None, None],
    [7, None, None]]
  ]
]

結果是二叉搜索樹，因為左子節點小于父節點，右子節點大于父節點。因此呼叫的結果bst_child是True。

然后我添加了查找二叉搜索樹深度的代碼。通過對第一個串列進行排序，我制作了兩個不同的二叉搜索樹。

在這種情況下，第一個串列是[4,2,1,3,6,5,7]，第二個串列是 [1,2,3,4,5,6,7]，這是已排序的。

從第一個串列構建的二叉搜索樹的深度是 2，而從排序串列構建的二叉搜索樹的深度是 6。

unsorted = [4,2,1,3,6,5,7]
sorted = unsorted.copy()
sorted.sort()

t1 = bst_build(unsorted)
t2 = bst_build(sorted)

print(t1)
print(t2)
print(bst_check(t1), bst_check(t2))
print( bst_depth(t1), bst_depth(t2) )

輸出是（在漂亮列印嵌套串列之后）：

[4, 
  [2, 
    [1, None, None], 
    [3, None, None]
  ], 
  [6, 
    [5, None, None],
    [7, None, None]]
  ]
]

[1, None, 
  [2, None, 
    [3, None,
      [4, None,
        [5, None,
          [6, None,
            [7, None, None]
          ]
        ]
      ]
    ]
  ]
]

True True
2 6

我認為我很好地制作了二叉搜索樹和代碼查找深度。但是當我嘗試使用長串列時，我的 vscode 無法列印正確的結果。

當我嘗試使用長度為 20 的串列時，它起作用了。

unsorted = list(np.random.randint(0,1000,20))
sorted = unsorted.copy()
sorted.sort()

t1 = bst_build(unsorted)
t2 = bst_build(sorted)

print(bst_check(t1), bst_check(t2))
print( bst_depth(t1), bst_depth(t2) )

輸出：

True True
5 19

但是，當串列的長度約為 30 時，它不起作用。排序串列的長度是 30，但結果不是 29 而是其他一些數字，比如 3，否則會出現遞回錯誤：

呼叫 Python 物件時超出最大遞回深度

所以我通過添加sys.setrecursionlimit.

然后我的代碼作業，直到串列的長度約為 40~50。

但是當串列的長度超過 50 時，這種方法仍然會遇到同樣的問題。我也嘗試過數sys.setrecursionlimit(1000000)百萬或數百萬，但沒有幫助。

甚至有時什么也沒有列印。

我怎么解決這個問題？

uj5u.com熱心網友回復：

在你的二叉樹相對平衡的情況下，遞回深度不應該那么大。盡管如此，即使您的二叉樹是退化的，就像您從排序序列 () 創建它時發生的那樣，sorted那么您仍然應該只需要 O(n) 堆疊空間。

bst_build但是你的代碼find_depth需要更多的堆疊空間。這是因為它們在到達葉子時不會回溯。相反，它們都從root重新開始遍歷，而不是先退出當前的遞回樹：

• bst_buildbst_build當它想要從 插入下一個輸入時再次呼叫來做到這一點seq。這應該發生在回圈中（遞回之外），而不是當您已經深入遞回樹時。
• find_depthfind_depth通過在到達葉子時再次呼叫來做到這一點。這應該通過首先回溯一步然后再次重復到兄弟節點來實作。相反，它會從根目錄重新開始搜索（這是浪費時間），并且這樣做并沒有首先退出遞回。

這使得這段代碼需要大量的堆疊空間，這在最壞（退化）的情況下就像 O(n2)。

與您的問題無關，但遺憾的是 - 并且完全沒有必要 -find_depth在遍歷樹時破壞了樹。

另一個與您的問題無關的問題：您bst_check的不正確。它將為以下樹回傳 True：

            2
           /
          1
           \
            3

然而，這棵樹不是一個有效的 BST。有效 BST 的要求不僅是左子節點小于其父節點，而且左子樹中的所有節點都小于該父節點。

這是所有這些問題的修復：

def bst_build(seq):
    if not seq:
        return None

    def add_child(main, value):
        if value == main[0]:
            return
        childindex = 1 if main[0] > value else 2
        if not main[childindex]:
            main[childindex] = [value, None, None]
        else:
            add_child(main[childindex], value)

    binary_search_tree = [seq[0], None, None]
    for value in seq[1:]:
        add_child(binary_search_tree, value)

    return binary_search_tree


def bst_depth(b):
    return 1   max(bst_depth(b[1]) if b[1] else -1, bst_depth(b[2]) if b[2] else -1)


def bst_check(b, low=float("-inf"), high=float("inf")):
    return not b or (low <= b[0] <= high and bst_check(b[1], low, b[0]) 
                                         and bst_check(b[2], b[0], high))

標籤：Python 递归 二叉搜索树

上一篇：VBA使用遞回獲取檔案（物件）

下一篇：通過haskell中的串列理解提取元組的第一個元素