7 days of WordPress plugins, themes & templates - for free!* Unlimited asset downloads! Start 7-Day Free Trial
Advertisement
  1. Code
  2. JavaScript

Cấu trúc dữ liệu với JavaScript: Tree

Read Time: 18 mins
This post is part of a series called Data Structures in JavaScript.
Data Structures With JavaScript: Singly-Linked List and Doubly-Linked List

Vietnamese (Tiếng Việt) translation by Andrea Ho (you can also view the original English article)

Final product imageFinal product imageFinal product image
What You'll Be Creating

Tree là một trong những cấu trúc dữ liệu được sử dụng phổ biến nhất trong phát triển web. Tuyên bố này đúng cho cả nhà phát triển và người dùng. Mỗi nhà phát triển web đã viết HTML và tải nó vào trình duyệt web đã tạo ra một tree, được gọi là Mô hình đối tượng tài liệu (DOM). Mỗi người dùng Internet, những người có, lần lượt, tiêu thụ thông tin trên Internet đã nhận được nó dưới dạng một tree - DOM.

Bây giờ, đây là đỉnh điểm: Bài viết mà bạn đang đọc tại thời điểm này được hiển thị trong trình duyệt của bạn dưới dạng tree! Đoạn mà bạn đang đọc được thể hiện dưới dạng văn bản trong phần tử ; phần tử được lồng trong phần tử ; và phần tử được lồng trong phần tử .

Việc lồng dữ liệu tương tự như một tree gia đình. Phần tử là một phần tử cha, phần tử là một phần tử con, và phần tử là một phần tử con của phần tử . Nếu sự tương tự của tree này có vẻ hữu ích đối với bạn, thì bạn sẽ thấy thoải mái khi biết rằng nhiều tương tự hơn sẽ được sử dụng trong quá trình thực hiện của chúng ta về một cái tree.

Trong bài viết này, chúng ta sẽ tạo ra một tree bằng cách sử dụng hai phương thức khác nhau của tree traversal: Depth-First Search (DFS) và Breadth-First Search (BFS). (Nếu từ traversal là không quen thuộc với bạn, hãy xem xét nó có nghĩa là truy cập vào mỗi nút của tree.) Cả hai loại traversals này đều nêu bật các cách tương tác khác nhau với một tree; cả hai di chuyển, hơn nữa, kết hợp việc sử dụng các cấu trúc dữ liệu mà chúng tôi đã trình bày trong loạt bài này. DFS sử dụng một ngăn xếp và BFS sử dụng một hàng đợi để truy cập các nút. Thật tuyệt!

Tree (Tìm kiếm đầu tiên và tìm kiếm theo chiều sâu)

Trong khoa học máy tính, tree là một cấu trúc dữ liệu mô phỏng dữ liệu phân cấp với các nút. Mỗi nút của tree chứa dữ liệu và con trỏ của riêng nó cho các nút khác.

Thuật ngữ của các nút và con trỏ có thể là mới đối với một số độc giả, vì vậy hãy mô tả chúng thêm một cách tương tự. Hãy so sánh một tree với một sơ đồ tổ chức. Biểu đồ có vị trí cấp cao nhất (nút gốc), chẳng hạn như Giám đốc điều hành. Ngay bên dưới vị trí này là các vị trí khác, chẳng hạn như phó chủ tịch (VP).

Để đại diện cho mối quan hệ này, chúng tôi sử dụng các mũi tên trỏ từ CEO đến VP. Một vị trí, chẳng hạn như CEO, là một nút; mối quan hệ chúng ta tạo ra từ một CEO đến VP là một con trỏ. Để tạo thêm các mối quan hệ trong biểu đồ tổ chức của chúng tôi, chúng tôi chỉ lặp lại quá trình này — chúng tôi có một điểm nút đến một nút khác.

Trên một mức độ khái niệm, tôi hy vọng rằng các nút và con trỏ có ý nghĩa. Trên một mức độ thực tế, chúng ta có thể hưởng lợi từ việc sử dụng một ví dụ kỹ thuật hơn. Hãy xem xét DOM. DOM có phần tử làm vị trí cấp cao nhất (nút gốc). Nút này trỏ đến phần tử và phần tử . Quá trình này được lặp lại cho tất cả các nút trong DOM.

Một trong những nét đẹp của thiết kế này là khả năng làm tổ các nút: một phần t ví dụ, có thể có nhiều phần tử Điều đó thật kỳ lạ, nhưng buồn cười và đúng sự thật!

Hoạt động của một tree

Vì mỗi tree có chứa các nút, có thể là một hàm tạo riêng biệt từ một tree, chúng ta sẽ phác thảo các hoạt động của cả hai hàm tạo: Node và Tree.

Nút

  • dữ liệu lưu trữ một giá trị.
  • cha mẹ trỏ đến cha mẹ của nút.
  • trẻ em trỏ đến nút tiếp theo trong danh sách.

Tree

  • _root trỏ đến nút gốc của tree.
  • traverseDF (gọi lại) đi qua các nút của tree bằng DFS.
  • traverseBF (gọi lại) đi qua các nút của tree bằng BFS.
  • chứa (dữ liệu, truyền tải) tìm kiếm một nút trong tree.
  • add (data, toData, traverse) thêm một nút vào một tree.
  • loại bỏ (con, cha mẹ) loại bỏ một nút trong một tree.

Thực hiện một tree

Bây giờ hãy viết mã cho một cái tree!

Thuộc tính của nút

Để thực hiện, trước tiên chúng ta sẽ định nghĩa một hàm có tên là Node và sau đó là một hàm tạo tên là Tree.

Mỗi thể hiện của Node chứa ba thuộc tính: dữ liệu, cha mẹ và con cái. Thuộc tính đầu tiên chứa dữ liệu được liên kết với một nút. Thuộc tính thứ hai trỏ đến một nút. Thuộc tính thứ ba trỏ đến nhiều nút con.

Thuộc tính của tree

Bây giờ, hãy định nghĩa hàm khởi tạo của chúng ta cho Tree, bao gồm hàm tạo Node trong định nghĩa của nó:

Tree chứa hai dòng mã. Dòng đầu tiên tạo ra một thể hiện mới của nút; dòng thứ hai gán nút làm gốc của tree.

Các định nghĩa của tree và nút chỉ yêu cầu một vài dòng mã. Tuy nhiên, những dòng này là đủ để giúp chúng tôi mô phỏng dữ liệu phân cấp. Để chứng minh điểm này, chúng ta hãy sử dụng một số dữ liệu ví dụ để tạo ra một thể hiện của Tree (và, gián tiếp, Node).

Nhờ sự tồn tại của cha mẹ và con cái, chúng ta có thể thêm các nút dưới dạng con của _root và cũng gán _root làm cha mẹ của các nút đó. Nói cách khác, chúng ta có thể mô phỏng việc tạo dữ liệu phân cấp.

Phương pháp của tree

Tiếp theo, chúng ta sẽ tạo ra năm phương thức sau:

Tree

  1. traverseDF (gọi lại)
  2. traverseBF (gọi lại)
  3. chứa (dữ liệu, truyền tải)
  4. thêm (con, cha mẹ)
  5. loại bỏ (nút, cha mẹ)

Vì mọi phương thức của tree đều yêu cầu chúng ta đi qua một cái tree, trước tiên chúng ta sẽ triển khai các phương thức xác định các kiểu đi qua tree khác nhau. (Traversing một tree là một cách chính thức của nói đến thăm mỗi nút của một tree.)

1/5: traverseDF (gọi lại)

Phương thức này đi qua một tree có tìm kiếm theo chiều sâu.

traverseDF (gọi lại) có một tham số có tên gọi lại. Nếu nó không rõ ràng từ tên, gọi lại được coi là một chức năng, mà sẽ được gọi sau này trong traverseDF (gọi lại).

Nội dung của traverseDF (gọi lại) bao gồm một hàm khác có tên là recurse. Hàm này là hàm đệ quy! Nói cách khác, nó tự gọi và tự chấm dứt. Sử dụng các bước được đề cập trong các ý kiến ​​của recurse, tôi sẽ mô tả quá trình chung mà recurse sử dụng để đi qua toàn bộ tree.

Dưới đây là các bước:

  1. Ngay lập tức gọi recurse với nút gốc của tree làm đối số của nó. Tại thời điểm này, currentNode trỏ đến nút hiện tại.
  2. Nhập một vòng lặp for và lặp lại một lần cho mỗi con của currentNode, bắt đầu với con đầu tiên.
  3. Bên trong phần thân của vòng lặp for, gọi recurse với một child của currentNode. Đứa trẻ chính xác phụ thuộc vào vòng lặp hiện tại của vòng lặp for.
  4. Khi currentNode không còn có con, chúng ta thoát khỏi vòng lặp for và gọi hàm gọi lại mà chúng ta đã truyền trong khi gọi traverseDF (gọi lại).

Các bước 2 (tự kết thúc), 3 (tự gọi) và 4 (gọi lại) lặp lại cho đến khi chúng ta đi qua mọi nút của tree.

Đệ quy là một chủ đề rất khó để dạy và yêu cầu toàn bộ một bài viết để giải thích đầy đủ nó. Vì lời giải thích của đệ quy không phải là trọng tâm của bài viết này - trọng tâm đang thực hiện một tree - tôi sẽ đề nghị rằng bất kỳ độc giả nào thiếu hiểu biết về đệ quy đều làm hai điều sau đây.

Trước tiên, hãy thử nghiệm với việc thực hiện traverseDF (gọi lại) hiện tại của chúng tôi và cố gắng hiểu mức độ hoạt động của nó. Thứ hai, nếu bạn muốn tôi viết một bài viết về đệ quy, sau đó xin vui lòng yêu cầu nó trong các ý kiến ​​của bài viết này.

Ví dụ sau minh họa cách tree sẽ được di chuyển ngang qua với traverseDF (gọi lại). Để đi qua một cái tree, tôi sẽ tạo một cái trong ví dụ dưới đây. Cách tiếp cận mà tôi sẽ sử dụng tại thời điểm này không phải là lý tưởng, nhưng nó hoạt động. Một cách tiếp cận tốt hơn là sử dụng add (value), mà chúng ta sẽ thực hiện trong bước 4 của 5.

Bây giờ, hãy gọi traverseDF (gọi lại).

2 trên 5: traverseBF (gọi lại)

Phương pháp này sử dụng tìm kiếm rộng đầu tiên để đi qua một tree.

Sự khác biệt giữa tìm kiếm chiều sâu và tìm kiếm theo chiều rộng đầu tiên liên quan đến trình tự các nút của lượt truy cập tree. Để minh họa điểm này, hãy sử dụng tree chúng ta đã tạo từ traverseDF (gọi lại).

Bây giờ, chúng ta hãy vượt qua traverseBF (gọi lại) cùng một cuộc gọi lại mà chúng ta đã sử dụng cho traverseDF (gọi lại).

Các bản ghi từ bảng điều khiển và sơ đồ tree của chúng tôi cho thấy một mô hình về tìm kiếm rộng đầu tiên. Bắt đầu với nút gốc; sau đó di chuyển một chiều sâu và ghé thăm mọi nút ở độ sâu đó từ trái sang phải. Lặp lại quá trình này cho đến khi không có thêm chiều sâu để di chuyển.

Vì chúng ta có một mô hình khái niệm về tìm kiếm rộng đầu tiên, bây giờ chúng ta hãy triển khai mã sẽ làm công việc ví dụ của chúng ta.

Định nghĩa của chúng ta về traverseBF (gọi lại) chứa rất nhiều logic. Vì lý do này, tôi sẽ giải thích logic trong các bước có thể quản lý được:

  1. Tạo một thể hiện của Hàng đợi.
  2. Thêm nút đã gọi traverseBF (gọi lại) đến thể hiện của Hàng đợi.
  3. Khai báo một biến có tên là currentNode và khởi tạo nó vào nút mà chúng ta vừa thêm vào hàng đợi của mình.
  4. Trong khi currentNode trỏ tới một nút, thực thi mã bên trong vòng lặp while.
  5. Sử dụng vòng lặp for để lặp lại trên con của currentNode.
  6. Bên trong phần thân của vòng lặp for, thêm mọi con vào hàng đợi.
  7. Hãy currentNode và vượt qua nó như một đối số của gọi lại.
  8. Gán lại currentNode cho nút đang được loại bỏ khỏi hàng đợi.
  9. Cho đến khi currentNode không trỏ đến một nút - mọi nút trong tree đã được truy cập — lặp lại các bước từ 4 đến 8.

3 trong 5: chứa (gọi lại, truyền tải)

Hãy định nghĩa một phương thức cho phép chúng ta tìm kiếm một giá trị cụ thể trong tree của chúng ta. Để sử dụng một trong hai phương thức duyệt tree của chúng tôi, tôi đã xác định có chứa (gọi lại, truyền tải) để chấp nhận hai đối số: dữ liệu cần tìm kiếm và loại truyền tải.

Trong phần thân chứa (callback, traversal), chúng ta sử dụng một phương thức có tên gọi để truyền nó và gọi lại. Đối số đầu tiên liên kết traversal với tree được gọi chứa (callback, traversal); đối số thứ hai là một hàm được gọi trên mỗi nút trong tree của chúng ta.

Hãy tưởng tượng rằng chúng ta muốn đăng nhập vào giao diện điều khiển bất kỳ nút nào có chứa dữ liệu với một số lẻ và duyệt qua mọi nút trong tree của chúng ta bằng BFS. Đây là mã chúng tôi viết:

4/5: thêm (dữ liệu, toData, traversal)

Bây giờ chúng ta có một phương pháp để tìm kiếm một nút cụ thể trong tree của chúng ta. Bây giờ chúng ta hãy định nghĩa một phương thức cho phép chúng ta thêm một nút vào một nút cụ thể.

add (dữ liệu, toData, traversal) định nghĩa ba tham số. Tham số đầu tiên, dữ liệu, được sử dụng để tạo một thể hiện mới của nút. Tham số thứ hai, toData, được sử dụng để so sánh với mọi nút trong tree. Tham số thứ ba, traversal, là kiểu traversal tree được sử dụng trong phương thức này.

Trong phần thân của add (dữ liệu, toData, traversal), chúng ta khai báo ba biến. Biến đầu tiên, con, được khởi tạo như một thể hiện mới của nút. Biến thứ hai, parent, được khởi tạo là null; nhưng sau đó nó sẽ trỏ đến bất kỳ nút nào trong một tree phù hợp với giá trị của toData. Việc bố trí lại phụ huynh xảy ra trong biến thứ ba mà chúng ta khai báo, đó là gọi lại.

callback là một hàm so sánh toData với thuộc tính dữ liệu của mỗi nút. Nếu câu lệnh if đánh giá là true, thì cha được gán cho nút khớp với phép so sánh trong câu lệnh if.

Sự so sánh thực tế của mỗi nút đến toData xảy ra trong chứa (callback, traversal). Loại truyền tải và cuộc gọi lại phải được chuyển làm đối số chứa (gọi lại, truyền tải).

Cuối cùng, nếu cha mẹ không tồn tại trong tree, chúng ta đẩy con vào parent.children; chúng tôi cũng chỉ định phụ huynh cho phụ huynh của trẻ. Khác, chúng tôi ném một lỗi.

Hãy sử dụng add (dữ liệu, toData, traversal) trong một ví dụ:

Dưới đây là một ví dụ phức tạp hơn về việc thêm (addData, toData, traversal):

5/5: xóa (dữ liệu, từData, traversal)

Để hoàn thành việc thực thi Tree, chúng ta sẽ thêm một phương thức có tên remove (data, fromData, traversal). Tương tự như việc loại bỏ một nút từ DOM, phương thức này sẽ loại bỏ một nút và tất cả các nút con của nó.

Tương tự như thêm (dữ liệu, toData, traversal), loại bỏ đi qua một tree để tìm một nút có chứa đối số thứ hai, mà bây giờ là từData. Nếu nút này được tìm thấy, thì cha mẹ trỏ đến nó.

Tại thời điểm này, chúng tôi đạt được tuyên bố đầu tiên của chúng tôi nếu. Nếu cha mẹ không tồn tại, chúng tôi ném một lỗi. Nếu cha mẹ không tồn tại, chúng ta gọi hàm findIndex () với parent.children và dữ liệu chúng ta muốn loại bỏ khỏi các nút con của cha mẹ. (findIndex () là một phương thức trợ giúp mà tôi đã định nghĩa bên dưới.)

Bên trong findIndex (), logic sau xảy ra. Nếu bất kỳ nút nào trong parent.children chứa dữ liệu khớp với dữ liệu, chỉ mục biến được gán một số nguyên. Nếu không có thuộc tính dữ liệu nào của con khớp với dữ liệu, thì chỉ mục sẽ giữ lại giá trị mặc định của nó là không xác định. Trên dòng cuối cùng của findIndex (), chúng tôi trả về chỉ mục.

Bây giờ chúng ta quay trở lại để loại bỏ (dữ liệu, fromData, traversal). Nếu chỉ mục là không xác định, một lỗi được ném. Nếu chỉ mục được xác định, chúng tôi sử dụng nó để tách nút mà chúng tôi muốn xóa khỏi con của cha mẹ; chúng tôi cũng chỉ định con đã xóa cho childToRemove.

Cuối cùng, chúng ta trả về childToRemove.

Hoàn thành thực hiện một tree

Việc thực hiện Tree của chúng ta đã hoàn tất. Hãy xem — chúng tôi đã hoàn thành rất nhiều:

Tổng kết

Tree mô phỏng dữ liệu phân cấp. Phần lớn thế giới xung quanh chúng ta giống với loại phân cấp này, chẳng hạn như các trang web và gia đình của chúng tôi. Bất cứ lúc nào bạn thấy mình cần cấu trúc dữ liệu với cấu trúc phân cấp, hãy xem xét sử dụng tree.

Advertisement
Did you find this post useful?
Want a weekly email summary?
Subscribe below and we’ll send you a weekly email summary of all new Code tutorials. Never miss out on learning about the next big thing.
Advertisement
Scroll to top
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.