刪除方案中的BST中的元素

我似乎無法弄清楚如何從BST中刪除元素。這是我的代碼刪除方案中的BST中的元素

(define remove (lambda (x t) 
     (if (< x (car t)) (list (car t) (remove x (cadr t)) (caddr t)) 
      (if (> x (car t)) (list (car t) (cadr t) (remove x (caddr t))) 
        (if (not(and (null? (cadr t)) (null? (caddr t)))) 
         (let ((r (minimum (caddr t)))) ((remove r t) (set-car! t r))) 
         (list '() (cadr t) (caddr t)))))))

最小值返回樹中的最小值。如果我嘗試刪除一個不是葉子的元素，它將進入無限循環。我該如何解決它？

來源

2010-12-11 user

看起來像[此問題]的副本（http://stackoverflow.com/questions/4374530/how-do-i-delete-from-a-binary-search-tree-in-lisp/4383580）。 – 2010-12-11 19:22:21

我覺得你最大的問題在於本節：

((remove r t) (set-car! t r))

您從t刪除r，但你確實應該從t右子樹移除r。我不確定你爲什麼使用可變性/設置;我認爲這會使事情變得複雜化，這很容易成爲一種無副作用的功能。我會嘗試這樣的：

(list r (cadr t) (remove r (caddr t)))

我也不得不承認，我有點困惑你的意圖與最後一行。你在用什麼空的名單？

來源

2010-12-11 17:00:11 ajduff574

只是爲了澄清，從t而不是其右側子樹中刪除r可能是導致無限遞歸的原因。 – ajduff574 2010-12-11 17:36:29

作爲替代方案，你可以在這裏看看在方案整個執行BST的：

http://en.literateprograms.org/Binary_tree_(Scheme)

這是很好的記錄，並會給你一些關於洞察力您可以構造代碼的方式易於閱讀和調試。特別是，它分別處理葉和節點（非葉）清除。

來源

2010-12-11 15:56:07

謝謝，我會研究它，但我真的很想聽聽有關爲什麼我的代碼無法正常工作的任何見解。特別是我剛剛開始學習Scheme，這有點令人沮喪。 – user 2010-12-11 16:17:19

同意 - 也許我想說的是：嘗試將你的代碼分離成更簡單的函數，以便測試它們是否正常工作。這與他們在我鏈接的頁面上完成的操作類似 - 您不必按照他們所做的方式進行操作，但可以將其分離爲「BST-remove」，它調用BST-leaf-remove '和'BST-node-remove'。這有助於理解代碼，然後找出問題，因爲這樣做更容易。 – 2010-12-11 16:43:43

刪除方案中的BST中的元素

回答

相關問題