序遍歷工作不正常

Question

我試圖寫一個序遍歷，而無需使用附加，這裏是我的代碼

(define inorder 
    (lambda (tree) 
     (define inorder-iter 
     (lambda (tree list) 
      (if (empty-tree? tree) 
       list 
       (cons (inorder-iter (left-subtree tree) 
        (root tree) 
        (inorder-iter (right-subtree tree) list))))) 

    (inorder-iter tree '()))) 

---

(define empty-tree? null?) 

    (define root car) 

    (define left-subtree cadr) 

    (define right-subtree caddr) 


tree-1 
(9 
(6 (5()())()) 
(18 (11() (13() (17()()))) (65 (52 (41 (39()())())()) (99()())))) 

當我打電話（序樹-1） 我得到（ （（5.6）9）（11 13 17。18）（（（39。41）。52）。65）99）看起來非常糟糕。我試圖得到的是'（5 6 9 11 13 17 18 39 41 52 65 99）。我究竟做錯了什麼？謝謝！

Answer 1

你的圓括號有幾個問題。另請注意，您沒有使用list參數 - 甚至更多，它的名稱很差，因爲它與內置過程衝突。

該問題要求我們不使用內置的append函數，但簡單的cons將不起作用。這裏是一個可能的解決方案：

(define inorder 
    (lambda (tree) 
    (define inorder-iter 
     (lambda (tree lst) 
     (if (empty-tree? tree) 
      lst 
      (inorder-iter (left-subtree tree) 
          (cons (root tree) 
           (inorder-iter (right-subtree tree) 
               lst)))))) 
    (inorder-iter tree '()))) 

它按預期工作：

(inorder tree-1) 
=> '(5 6 9 11 13 17 18 39 41 52 65 99)