LISP - Cây

Bạn có thể xây dựng cấu trúc dữ liệu cây từ các ô khuyết điểm, dưới dạng danh sách các danh sách.

Để triển khai cấu trúc cây, bạn sẽ phải thiết kế các chức năng sẽ đi qua các ô khuyết điểm, theo thứ tự cụ thể, ví dụ, thứ tự trước, thứ tự và sau cho cây nhị phân.

Cây dưới dạng Danh sách Danh sách

Chúng ta hãy xem xét một cấu trúc cây được tạo thành từ các ô khuyết điểm tạo thành danh sách các danh sách sau:

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

Theo sơ đồ, nó có thể được biểu thị là -

Các chức năng của cây trong LISP

Mặc dù hầu hết bạn sẽ cần phải viết các chức năng cây của riêng mình theo nhu cầu cụ thể của bạn, nhưng LISP cung cấp một số chức năng cây mà bạn có thể sử dụng.

Ngoài tất cả các hàm trong danh sách, các hàm sau hoạt động đặc biệt trên cấu trúc cây:

Sr.No.	Mô tả chức năng
1	copy-tree x & vecp tùy chọn Nó trả về một bản sao của cây ô khuyết điểm x. Nó sao chép đệ quy cả hướng xe và cdr. Nếu x không phải là ô khuyết điểm, hàm chỉ trả về x không đổi. Nếu đối số vecp tùy chọn là true, hàm này sẽ sao chép các vectơ (một cách đệ quy) cũng như các ô khuyết điểm.
2	tree-equal xy & key: test: test-not: key Nó so sánh hai cây ô khuyết điểm. Nếu x và y đều là ô khuyết điểm, thì ô tô và mã của chúng được so sánh một cách đệ quy. Nếu cả x và y đều không phải là ô khuyết điểm, chúng được so sánh bằng eql hoặc theo thử nghiệm đã chỉ định. Hàm: key, nếu được chỉ định, được áp dụng cho các phần tử của cả hai cây.
3	subst cây cũ mới & key: test: test-not: key Nó thay thế các lần xuất hiện của mục cũ đã cho bằng mục mới , trong cây , là một cây gồm các ô khuyết điểm.
4	nsubst cây cũ mới & key: test: test-not: key Nó hoạt động giống như subst, nhưng nó phá hủy cây gốc.
5	sublis cây alist & key: test: test-not: key Nó hoạt động như subst, ngoại trừ việc nó có một danh sách liên kết alist các cặp cũ-mới. Mỗi phần tử của cây (sau khi áp dụng: chức năng chính, nếu có), được so sánh với các ô tô của alist; nếu khớp, nó được thay thế bằng cdr tương ứng.
6	nsublis cây alist & key: test: test-not: key Nó hoạt động giống như sublis, nhưng là một phiên bản hủy diệt.

ví dụ 1

Tạo một tệp mã nguồn mới có tên main.lisp và nhập mã sau vào đó.

(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)

Khi bạn thực thi mã, nó trả về kết quả sau:

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

Ví dụ 2

Tạo một tệp mã nguồn mới có tên main.lisp và nhập mã sau vào đó.

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

Khi bạn thực thi mã, nó trả về kết quả sau:

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

Xây dựng cây của riêng bạn

Hãy để chúng tôi cố gắng xây dựng cây của riêng mình, sử dụng các chức năng danh sách có sẵn trong LISP.

Trước tiên, hãy tạo một nút mới chứa một số dữ liệu

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

Tiếp theo, chúng ta hãy thêm một nút con vào cây - nó sẽ lấy hai nút cây và thêm cây thứ hai làm nút con của cây đầu tiên.

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

Hàm này sẽ trả về con đầu tiên của một cây nhất định - nó sẽ lấy một nút cây và trả về con đầu tiên của nút đó, hoặc nil, nếu nút này không có bất kỳ nút con nào.

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

Hàm này sẽ trả về nút anh em tiếp theo của một nút nhất định - nó lấy một nút cây làm đối số và trả về một tham chiếu đến nút anh em tiếp theo, hoặc nil, nếu nút không có nút nào.

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

Cuối cùng, chúng ta cần một hàm để trả về thông tin trong một nút -

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

Thí dụ

Ví dụ này sử dụng các chức năng trên -

Tạo một tệp mã nguồn mới có tên main.lisp và nhập mã sau vào đó.

(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)

Khi bạn thực thi mã, nó trả về kết quả sau:

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

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