Cây là một trong những cấu trúc dữ liệu phổ biến nhất trong khoa học máy tính và cách tự nhiên để mô hình hóa các lĩnh vực chủ đề nhất định. Cây (như một cấu trúc dữ liệu) được tìm thấy bằng cách này hay cách khác bởi tất cả mọi người, ngay cả những người không chỉ lập trình mà còn từ các máy tính nói chung. Ví dụ rõ ràng nhất là cây gia đình, và cái chuyên dụng hơn là cây tập tin. Và, tất nhiên, HTML (cũng như JSON, XML và hơn thế nữa), nó cũng có cấu trúc cây. Bất kỳ hệ thống phân cấp là một cây theo định nghĩa.family tree , and the more specialized one is the file tree . And, of course, HTML (as well as json , xml and more), it also has a tree structure. Any hierarchy is a tree by definition. Show Có một khía cạnh rất thú vị đối với cây. Tôi thường quan sát mức độ hiểu biết về chủ đề của cây và khả năng làm việc với chúng có mối tương quan mạnh mẽ với mức độ của nhà phát triển. JS: Cây → Định nghĩaTính năng chính của cấu trúc cây là nó là đệ quy. Nói cách khác, một cây bao gồm các cây con, từ đó bao gồm các cây con, đến lượt cuối cùng, ở phía dưới, có những chiếc lá - và bây giờ chúng không có con cháu và không dẫn đến bất cứ nơi nào.recursive . In other words, a tree consists of subtrees, which in turn consist of subtrees, which in turn … In the end, at the very bottom, there are leaves — and now they have no descendants and do not lead anywhere. Một cây bao gồm các nút và cạnh giữa chúng. Các xương sườn trong thực tế không tồn tại, chúng chỉ cần để hình dung kết nối và, nếu cần thiết, để mô tả nó. Các nút được chia thành hai loại: bên trong (những người có hậu duệ) và các nút lá (những người không có hậu duệ). Trong trường hợp của một hệ thống tệp, các nút lá được thể hiện bằng các tệp và các nút nội bộ là các thư mục.nodes and edges between them. The ribs in reality do not exist, they are needed only to visualize the connection and, if necessary, to describe it. Nodes are divided into two types: internal (those that have descendants) and leaf nodes (those that have no descendants). In the case of a file system, leaf nodes are represented by files, and internal ones are directories. Trong cây, mỗi đỉnh có cha mẹ (hoặc tổ tiên). Ngoại lệ duy nhất là nút gốc - nó không có cha mẹ và cây bắt đầu với nó. Số lượng con cháu ở bất kỳ đỉnh bên trong nào, nói chung, có thể là bất kỳ. Ngoài ra, các cây làm nổi bật khái niệm độ sâu (độ sâu), xác định có bao nhiêu bước bạn cần đi dọc theo các đỉnh từ gốc để đạt được dòng điện (cái bạn đang nhìn). Các đỉnh ở cùng độ sâu với cha mẹ thông thường được gọi là anh em hoặc chị em.parent (or ancestor). The only exception is the root node — it has no parents, and the tree begins with it. The number of descendants at any internal vertex, in general, can be any. In addition, trees highlight the concept of depth (depth), which determines how many steps you need to go along the peaks from the root in order to reach the current (the one you are looking at). The peaks at the same depth with the common parent are called brotherly or sisterly. Sự định nghĩaSố lượng cách để mô tả cây là vô hạn. Ở đây chúng tôi chỉ xem xét những người dựa trên sự lặp lại của cấu trúc cây trong cấu trúc dữ liệu mô tả nó. Tùy chọn nguyên thủy nhất là các mảng lồng nhau: Trong các ví dụ trên, gốc là chính mảng và tất cả các yếu tố của nó là trẻ em. Nếu đứa trẻ không phải là một mảng, thì nó được coi là một nút lá, nếu không - như một nút bên trong. Các nút nội bộ, lần lượt, bao gồm trẻ em. Một cấu trúc như vậy có một giới hạn. Các nút nội bộ không thể lưu trữ dữ liệu, nhưng, nói chung, một sơ đồ như vậy có thể được sử dụng và gặp phải trong cuộc sống. Bạn có thể đi xa hơn và đạt được sự linh hoạt hơn. Hãy tưởng tượng mỗi phần tử của cây như một mảng trong đó phần tử đầu tiên là giá trị được lưu trữ trong nút và phần tử thứ hai là mảng của trẻ em. Nếu phần tử thứ hai bị thiếu, thì chúng tôi cho rằng nút hiện tại là lá. . Imagine each element of the tree as an array in which the first element is the value stored in the node, and the second element is the array of children. If the second element is missing, then we assume that the current node is leaf. Tùy chọn này là nhiều dòng hơn, nhưng cho phép bạn lưu trữ dữ liệu (tùy ý) trong bất kỳ nút nào, thậm chí không phải là một tờ. Bây giờ, tôi hy vọng bạn hiểu nguyên tắc của tổ chức và bạn có thể thực hành bản thân phát minh ra các cách để đóng gói cây thành một mảng. Nhân tiện, một chi tiết thú vị. Mã nguồn cho các ngôn ngữ cấp cao cũng có cấu trúc đệ quy. Nhìn vào mã: Đối số chức năng là các biểu thức, có nghĩa là chúng có thể là các cuộc gọi chức năng, gây ra đệ quy. Nếu mã trên được viết lại theo kiểu ngôn ngữ Lisp, thì chúng ta sẽ nhận được cây thật nhất bao gồm các danh sách: Thỏa thuận ở đây là: Yếu tố đầu tiên của danh sách là một hàm (bất kỳ hoạt động nào được coi là chức năng) và mọi thứ khác là đối số của nó. Một định nghĩa khác dựa trên các mảng kết hợp và cụ thể trong JavaScript - trên các đối tượng: Nhìn chung, rằng mảng, rằng chính đối tượng luôn có thể được coi là một cây, bất kể cấu trúc bên trong của nó và sự hiện diện của các yếu tố lồng nhau. Đó là bản chất của họ. Cấu trúc có mặt ở nơi bạn cần lưu trữ chính xác dữ liệu cây, ví dụ, hệ thống tệp. Để bắt đầu, tôi sẽ tiết lộ bí mật; Hầu hết các hệ thống tệp không chỉ có cấu trúc cây, mà còn được thể hiện ở cấp độ triển khai dưới dạng cấu trúc dữ liệu. Chúng tôi sẽ làm việc với cùng một cấu trúc, tạo ra các chức năng hỗ trợ khác nhau để tìm kiếm và sửa đổi nội dung. Dưới đây là mã tạo ra đối tượng cây bắt buộc: Do kết quả thực thi mã, kết quả sau đây đã thu được: Chế độ xem thư mục: Xem tập tin: Một số tuyên bố liên quan đến cây trên là:
Về phần cuối cùng tôi sẽ nói một vài từ. Chính sự hiểu biết về OOP, được nói đến rất nhiều, là mã được xem xét từ quan điểm của các loại, và bạn có thể thấy chúng. Điều quan trọng là phải phân bổ chúng một cách rõ ràng và không phân tích chúng bằng các dấu hiệu gián tiếp - ví dụ, xác định loại nút nào trước mặt chúng ta (loại nào!) của tài sản JS: Cây → TraversalMột liệt kê từng bước các yếu tố cây dọc theo các liên kết giữa các nút tổ tiên và các nút hậu duệ được gọi là đi bộ trên cây. Điều này được hiểu rằng trong quá trình thu thập dữ liệu, mỗi nút sẽ chỉ bị ảnh hưởng một lần. Nhìn chung, mọi thứ đều giống như bỏ qua bất kỳ bộ sưu tập nào bằng cách sử dụng vòng lặp hoặc đệ quy. Chỉ trong trường hợp của cây, mới có nhiều cách để đi xung quanh hơn là từ trái sang phải và phải sang trái. Một thứ tự truyền tải được sử dụng - đường vòng theo chiều sâu, vì nó có được tự nhiên bằng cách đi lại đệ quy. Về những cách khác, bạn có thể đọc trên Wikipedia hoặc trong các cuốn sách được đề xuất Heksleta.tree walk . It is understood that during the crawl process, each node will be affected only once. By and large, everything is the same as bypassing any collection using a loop or recursion. Only in the case of trees are there more ways to go around than just left to right and right to left. One traversal order is used — detour in depth , since it is naturally obtained by recursive traversal. On the other ways you can read on Wikipedia or in the recommended books Heksleta. Tìm kiếm chiều sâu đầu tiênMột trong những phương thức truyền tải cây (đồ thị nói chung). Chiến lược cho tìm kiếm này là đi xa nhất có thể thành một cây con. Thuật toán này tự nhiên rơi vào giải pháp đệ quy và tự xuất hiện. Hãy xem xét thuật toán này trên ví dụ về cây sau: Tôi đánh dấu mỗi đỉnh không lá bằng dấu hoa thị. Thu thập thông tin bắt đầu ở nút gốc.
Lặp lại logic của bước đầu tiên. Chúng tôi rơi xuống mức dưới đây.
Ở nơi này, như chúng ta nhớ, cuộc gọi đệ quy đã được đưa ra trên mỗi đứa trẻ. Vì đứa trẻ đầu tiên đã được viếng thăm, cuộc gọi đệ quy thứ hai vào nút JS: Cây → Bản đồMột ví dụ về bài học trước là cực kỳ đơn giản để khái quát hóa chức năng bậc cao JS: Cây → Bộ lọcNgược lại Tuy nhiên, đôi khi, nó được sử dụng, để hoàn thành bức tranh, nó đáng để trải qua tất cả các bước. Đầu tiên bạn cần quyết định những gì bạn cần quay lại trong một tình huống nếu nút không thỏa mãn vị ngữ. Nó là hợp lý khi sử dụng Tuy nhiên, đôi khi, nó được sử dụng, để hoàn thành bức tranh, nó đáng để trải qua tất cả các bước. Đầu tiên bạn cần quyết định những gì bạn cần quay lại trong một tình huống nếu nút không thỏa mãn vị ngữ. Nó là hợp lý khi sử dụng Nhìn vào việc triển khai bộ lọc, rõ ràng là nếu nút không thỏa mãn vị ngữ, thì con cái của nó hoàn toàn không được xem xét. Trong nút ví dụ trên b. Theo đó, con của cô ấy và giá vé thậm chí không được phân tích và lọc bằng giường và. Nó trông thú vị và mục này JS: Cây → giảm
Tính năng chính Trên đây là một thử nghiệm ví dụ được sử dụng Cũng như trong các chức năng khác có thứ tự cao hơn, nút được chuyển đến hàm xử lý nói chung, và không chỉ là tên. Điều thú vị nhất xảy ra khi xử lý trẻ em. Một cuộc gọi JS: Cây → Tìm kiếmTìm kiếm hệ thống tệp là một hoạt động được thực hiện cực kỳ thường xuyên. Nó mở ra rất nhiều nhiệm vụ thú vị. Hãy để chúng tôi kiểm tra một trong số họ với một số biến thể. Giả sử chúng tôi muốn liệt kê tất cả các thư mục trống. Sử dụng Cấu trúc này có hai thư mục trống:
Ví dụ này cho thấy vẻ đẹp của các chức năng bậc cao. Chúng tôi hoàn toàn bị che giấu khỏi cơ chế để bỏ qua cây, hơn nữa, bạn thậm chí không thể biết rằng chúng tôi làm việc với cây. Hãy để cố gắng làm phức tạp nhiệm vụ. Tìm tất cả các thư mục trống, nhưng với độ sâu tối đa của cấp độ tìm kiếm 2. nghĩa là một thư mục trống
Hãy để cố gắng giải quyết vấn đề này bằng phương pháp đầu tiên. Một vài điểm quan trọng:
Phần còn lại của mã giống như trong JS: Cây → Tập hợpHãy để thực hành với một biến thể khác của tập hợp dữ liệu trên các hệ thống tệp. Chúng tôi viết một chức năng lấy một thư mục làm đầu vào và trả về một danh sách các thư mục của cấp độ tổ đầu tiên và số lượng tệp trong đó, bao gồm tất cả các thư mục con. Hàm này sau đó có thể được sử dụng trong một tiện ích dòng lệnh thực hiện tác vụ tương ứng. Như có thể thấy từ câu lệnh, nhiệm vụ không thể được giải quyết bằng cách sử dụng nó trong hình thức thuần túy của nó, vì chúng ta không cần phải thu thập tất cả các nút, mặt khác, chúng ta cần thu thập dữ liệu để đếm số lượng tệp. Do đó, nhiệm vụ của chúng tôi rơi vào hai phần phụ: trích xuất các thư mục con của gốc hiện tại và gọi việc đếm các tệp bên trong mỗi đứa trẻ. Hãy bắt đầu bằng cách đếm số lượng tệp. Nhiệm vụ này chứa một
Đó là, chúng tôi đã chuyển sang trẻ em trực tiếp bằng cách đầu tiên lọc chúng, và sau đó thực hiện ánh xạ tới mảng cần thiết chứa cho mỗi thư mục của các tệp trong đó. Tài nguyên bổ sung
Một cây có ví dụ là gì?Một cây là một cấu trúc dữ liệu phân cấp được định nghĩa là một tập hợp các nút.Các nút đại diện cho giá trị và các nút được kết nối bởi các cạnh.Một cây có các thuộc tính sau: cây có một nút gọi là gốc.a hierarchical data structure defined as a collection of nodes. Nodes represent value and nodes are connected by edges. A tree has the following properties: The tree has one node called root.
Giải thích một cái cây là gì?Định nghĩa của cây Một cây là một cây cao có thể sống trong một thời gian rất dài.Nó có một thân cây hoặc thân cây và các nhánh hỗ trợ lá.Bên dưới mặt đất, một cái cây có một hệ thống rễ hoạt động như một mỏ neo và lưu trữ nước và các chất dinh dưỡng mà nhà máy cần để phát triển.a tall plant that can live for a very long time. It has a single stem or trunk and branches that support leaves. Beneath the ground, a tree has a root system that acts as an anchor and stores the water and nutrients the plant needs to grow.
Cây trong mã hóa là gì?Một cây là một tập hợp các thực thể gọi là các nút.Các nút được kết nối bởi các cạnh.Mỗi nút chứa một giá trị hoặc dữ liệu và nó có thể có hoặc không có nút con.Nút đầu tiên của cây được gọi là gốc.a collection of entities called nodes . Nodes are connected by edges . Each node contains a value or data , and it may or may not have a child node . The first node of the tree is called the root .
Biểu đồ cây vs là gì?Biểu đồ là một tập hợp các đỉnh/nút và cạnh.A cây là một tập hợp các nút và cạnh.Trong biểu đồ, không có nút duy nhất được gọi là gốc.Trong một cái cây, có một nút duy nhất được gọi là gốc. A tree is a set of nodes and edges. In the graph, there is no unique node which is known as root. In a tree, there is a unique node which is known as root. |
