LISP-나무

목록 목록으로 cons 셀에서 트리 데이터 구조를 작성할 수 있습니다.

트리 구조를 구현하려면 이진 트리에 대한 사전 주문, 순서 및 사후 주문과 같이 특정 순서로 cons 셀을 통과하는 기능을 설계해야합니다.

목록 목록으로 트리

다음 목록 목록을 형성하는 cons 셀로 구성된 트리 구조를 고려해 보겠습니다.

((1 2) (3 4) (5 6)).

도식적으로 표현하면-

LISP의 트리 함수

대부분의 경우 특정 필요에 따라 자체 트리 기능을 작성해야하지만 LISP는 사용할 수있는 몇 가지 트리 기능을 제공합니다.

모든 목록 함수 외에도 다음 함수는 특히 트리 구조에서 작동합니다.

Sr. 아니.	기능 및 설명
1	copy-tree x 및 선택적 vecp 죄수 셀 x의 트리 복사본을 반환합니다. 자동차와 cdr 방향을 모두 반복적으로 복사합니다. x가 단점 셀이 아니면 함수는 변경되지 않은 x를 반환합니다. 선택적 vecp 인수가 참이면이 함수는 벡터 (재귀 적으로)와 cons 셀을 복사합니다.
2	tree-equal xy & key : test : test-not : key 그것은 죄수 세포의 두 트리를 비교합니다. x와 y가 모두 단점 셀이면 자동차와 cdr가 재귀 적으로 비교됩니다. x도 y도 cons 셀이 아니면 eql 또는 지정된 테스트에 따라 비교됩니다. : key 함수가 지정되면 두 트리의 요소에 적용됩니다.
삼	subst 새로운 오래된 트리 및 키 : test : test-not : key 그것은과 주어진 된 항목의 발생으로 대체 새 의 항목 트리 단점 세포의 나무입니다.
4	nsubst 새로운 오래된 트리 및 키 : test : test-not : key subst와 동일하게 작동하지만 원래 트리를 파괴합니다.
5	sublis alist tree & key : test : test-not : key 그것은 연관 목록 걸리는 것을 제외하고, SUBST처럼 작동 alist 된 새로운 쌍을. 트리의 각 요소 (: key 함수를 적용한 후)는 alist의 자동차와 비교됩니다. 일치하면 해당 cdr로 대체됩니다.
6	nsublis alist tree & key : test : test-not : key sublis와 동일하게 작동하지만 파괴적인 버전입니다.

예 1

main.lisp라는 새 소스 코드 파일을 만들고 그 안에 다음 코드를 입력합니다.

(setq lst (list '(1 2) '(3 4) '(5 6)))
(setq mylst (copy-list lst))
(setq tr (copy-tree lst))

(write lst)
(terpri)
(write mylst)
(terpri)
(write tr)

코드를 실행하면 다음 결과가 반환됩니다.

((1 2) (3 4) (5 6))
((1 2) (3 4) (5 6))
((1 2) (3 4) (5 6))

예 2

main.lisp라는 새 소스 코드 파일을 만들고 그 안에 다음 코드를 입력합니다.

(setq tr '((1 2 (3 4 5) ((7 8) (7 8 9)))))
(write tr)
(setq trs (subst 7 1 tr))
(terpri)
(write trs)

코드를 실행하면 다음 결과가 반환됩니다.

((1 2 (3 4 5) ((7 8) (7 8 9))))
((7 2 (3 4 5) ((7 8) (7 8 9))))

나만의 나무 만들기

LISP에서 사용할 수있는 목록 함수를 사용하여 자체 트리를 구축해 보겠습니다.

먼저 데이터가 포함 된 새 노드를 생성하겠습니다.

(defun make-tree (item)
   "it creates a new node with item."
   (cons (cons item nil) nil)
)

다음으로 트리에 자식 노드를 추가해 보겠습니다. 두 개의 트리 노드를 사용하고 두 번째 트리를 첫 번째 트리의 자식으로 추가합니다.

(defun add-child (tree child)
   (setf (car tree) (append (car tree) child))
   tree)

이 함수는 주어진 트리의 첫 번째 자식을 반환합니다. 트리 노드를 가져 와서 해당 노드의 첫 번째 자식을 반환하거나이 노드에 자식 노드가 없으면 nil을 반환합니다.

(defun first-child (tree)
   (if (null tree)
      nil
      (cdr (car tree))
   )
)

이 함수는 주어진 노드의 다음 형제를 반환합니다-트리 노드를 인수로 취하고 다음 형제 노드에 대한 참조를 반환하거나 노드에없는 경우 nil을 반환합니다.

(defun next-sibling (tree)
   (cdr tree)
)

마지막으로 노드에 정보를 반환하는 함수가 필요합니다.

(defun data (tree)
   (car (car tree))
)

예

이 예제는 위의 기능을 사용합니다-

main.lisp라는 새 소스 코드 파일을 만들고 그 안에 다음 코드를 입력합니다.

(defun make-tree (item)
   "it creates a new node with item."
   (cons (cons item nil) nil)
)
(defun first-child (tree)
   (if (null tree)
      nil
      (cdr (car tree))
   )
)

(defun next-sibling (tree)
   (cdr tree)
)
(defun data (tree)
   (car (car tree))
)
(defun add-child (tree child)
   (setf (car tree) (append (car tree) child))
   tree
)

(setq tr '((1 2 (3 4 5) ((7 8) (7 8 9)))))
(setq mytree (make-tree 10))

(write (data mytree))
(terpri)
(write (first-child tr))
(terpri)
(setq newtree (add-child tr mytree))
(terpri)
(write newtree)

코드를 실행하면 다음 결과가 반환됩니다.

10
(2 (3 4 5) ((7 8) (7 8 9)))

((1 2 (3 4 5) ((7 8) (7 8 9)) (10)))