如何将图转换为Common Lisp中的Binary-Search-Tree？

Question

有人可以帮忙吗？例如，我有这个graph：

(setq graf '((A (B)) (B (C D)) (C (G)) (D (F G)) (F (E)) (E ()) (G ())))

如何将其转换为tree，以便该函数返回以下内容？

((A (B C)) (B (D E)) (C (F G)) (D ()) (E ()) (F ()) (G ())))

---

这是我的代码，我尝试过这个：

cvorovi--> nodes
potomak--> successor
novi--> new
napravi-stablo--> make tree
izbaci--> delete or remove

首先，我具有遍历功能

(defun traversal (graf l cvorovi)
(cond ((null l) (napravi-stablo graf cvorovi))
        (t(let* ((cvorovi1 (append cvorovi (list (car l))))
                 (potomci1 (dodaj-potomke graf (car l) (append (cdr l) cvorovi1)))
                 (l1 (append (cdr l) potomci1)))
            (traversal graf l1 cvorovi1)))))

然后：

(defun dodaj-potomke (graf cvor cvorovi)
  (cond ((null graf) '())
        ((equal (caar graf) cvor)
         (novi-cvorovi (cadar graf) cvorovi))
        (t (dodaj-potomke (cdr graf) cvor cvorovi))))

(defun novi-cvorovi (potomci cvorovi)
  (cond ((null potomci) '())
        ((member (car potomci) cvorovi)
         (novi-cvorovi (cdr potomci) cvorovi))
        (t (cons (car potomci)
                 (novi-cvorovi (cdr potomci) cvorovi)))))

//然后制作一棵树：

(defun napravi-stablo (graf cvorovi)
  (cond ((null cvorovi) graf)
        (:else (let* ((graf1 (izbaci graf (car cvorovi))))
                 (napravi-stablo graf1 (cdr cvorovi))))))

(defun izbaci (graf cvor)
  (cond ((null graf) '())
        ((equal (caar graf) (cadr cvor)) (cons (car graf) (izbaci (cdr graf) cvor)))
        (:else (cons (list (caar graf) (izbaci-potomke (cadar graf) (car cvor))) (izbaci (cdr graf) cvor)))))

(defun izbaci-potomke (lista cvor)
  (cond ((null lista) '())`enter code here`
        ((equal (car lista) cvor) (cdr lista))
        (:else (cons (car lista) (izbaci-potomke (cdr lista) cvor)))))

我不必是二叉树。但是我没有正确的解决方案。。幸运的是，教授坚持使用这三个函数：Traversal，dodaj-potomke和novi-cvorovi ...而且我不知道出来。

Answer 1

这是我的代码，我尝试过这个：

cvorovi--> nodes
potomak--> successor
novi--> new
napravi-stablo--> make tree
izbaci--> delete or remove

首先，我具有遍历功能

(defun traversal (graf l cvorovi)
(cond ((null l) (napravi-stablo graf cvorovi))
        (t(let* ((cvorovi1 (append cvorovi (list (car l))))
                 (potomci1 (dodaj-potomke graf (car l) (append (cdr l) cvorovi1)))
                 (l1 (append (cdr l) potomci1)))
            (traversal graf l1 cvorovi1)))))

然后：

(defun dodaj-potomke (graf cvor cvorovi)
  (cond ((null graf) '())
        ((equal (caar graf) cvor)
         (novi-cvorovi (cadar graf) cvorovi))
        (t (dodaj-potomke (cdr graf) cvor cvorovi))))

(defun novi-cvorovi (potomci cvorovi)
  (cond ((null potomci) '())
        ((member (car potomci) cvorovi)
         (novi-cvorovi (cdr potomci) cvorovi))
        (t (cons (car potomci)
                 (novi-cvorovi (cdr potomci) cvorovi)))))

//然后制作一棵树：

(defun napravi-stablo (graf cvorovi)
  (cond ((null cvorovi) graf)
        (:else (let* ((graf1 (izbaci graf (car cvorovi))))
                 (napravi-stablo graf1 (cdr cvorovi))))))

(defun izbaci (graf cvor)
  (cond ((null graf) '())
        ((equal (caar graf) (cadr cvor)) (cons (car graf) (izbaci (cdr graf) cvor)))
        (:else (cons (list (caar graf) (izbaci-potomke (cadar graf) (car cvor))) (izbaci (cdr graf) cvor)))))

(defun izbaci-potomke (lista cvor)
  (cond ((null lista) '())`enter code here`
        ((equal (car lista) cvor) (cdr lista))
        (:else (cons (car lista) (izbaci-potomke (cdr lista) cvor)))))

我不必是二叉树。但是我没有正确的解决方案。。幸运的是，教授坚持使用这三个函数：Traversal，dodaj-potomke和novi-cvorovi ...而且我不知道出来。