BST-類似結構元素遞回插入-有解無憂

我想知道為什么作者不會簡單地撰寫以下代碼而不是原始代碼。我進行了很多測驗，以免錯過任何一個案例。所以，它按預期作業。與時間復雜度有關嗎？我錯過了什么要點或細微差別？

將元素視為 [key,value,left-node,right-node]

// my simplification
def insert_binary_tree(x, T):
  if T == []:
      T.extend([x[0], x[1], [], []])
  else:
      if x[0] < T[0]:
          insert_binary_tree(x, T[2])
      else:
          insert_binary_tree(x, T[3])

原碼

def insert_binary_tree(x, T):
    if T == []:
        T.extend([x[0], x[1], [], []])
    else:
        if x[0] < T[0]:
            if T[2] == []:
                T[2] = [x[0], x[1], [], []]
            else:
                insert_binary_tree(x, T[2])
        else:
            if T[3] == []:
                T[3] = [x[0], x[1], [], []]
            else:
                insert_binary_tree(x, T[3])

示例運行，

t = ['Emma', '2002/08/23',
['Anna', '1999/12/03', [], []],
['Paul', '2000/01/13',
['Lara', '1987/08/23',
['John', '2006/05/08', [], []],
['Luke', '1976/07/31', [], []]],
['Sara', '1995/03/14', [], []]]]

def insert_binary_tree(x, T):
  if T == []:
      T.extend([x[0], x[1], [], []])
  else:
      if x[0] < T[0]:
          insert_binary_tree(x, T[2])
      else:
          insert_binary_tree(x, T[3])


print(t)
insert_binary_tree(['Abba', '1111/11/11', [], []], t)
print(t)

uj5u.com熱心網友回復：

唯一的原因可能是物件之間更大的獨立性。通過稍微更改輸入來比較兩個代碼：

empty = []

t = ['Emma', '2002/08/23',
['Anna', '1999/12/03', empty, empty],
['Paul', '2000/01/13',
['Lara', '1987/08/23',
['John', '2006/05/08', empty, empty],
['Luke', '1976/07/31', empty, empty]],
['Sara', '1995/03/14', empty, empty]]]

現在，原始代碼仍然有效，但您的無效。您仍然可以簡化它，同時保持對空串列的獨立參考：

def insert_binary_tree(x, T):
    if T == []:
        T.extend([x[0], x[1], [], []])
    else:
        child = 2   (x[0] >= T[0])
        if T[child]:
            insert_binary_tree(x, T[child])
        else:
            T[child] = x[:2]   [[], []]  
            # again trying to avoid mutable list references

轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/344911.html

標籤：Python 算法递归二叉搜索树

上一篇：Python-使用遞回實作二叉樹

下一篇：在PHP中加入至少一個普通用戶的帳戶的遞回函式