29
4
Một tập hợp các đơn vị lưu trữ có địa chỉ liên tiếp được sử dụng để lưu trữ từng nút trong cây. Mỗi nút có một trường dữ liệu và trường con trỏ được sử dụng để lưu trữ giá trị của chính nút đó trong trường con trỏ khác. được sử dụng để lưu trữ giá trị của nút trong cây Thông tin vị trí của nút cha trong cấu trúc lưu trữ.
Sẽ thuận tiện hơn khi sử dụng phương pháp lưu trữ danh sách liên kết cha để tìm nút cha của một nút được chỉ định, nhưng rất khó tìm thấy nút con của một nút được chỉ định.
Một tập hợp các đơn vị lưu trữ có địa chỉ liên tiếp được dùng để lưu trữ mỗi nút trong cây. Mỗi nút có một trường dữ liệu và một trường con trỏ được dùng để lưu trữ giá trị của nút đó trong cây; được sử dụng để lưu trữ giá trị của nút. Biểu mẫu này hơi giống một bảng nhận để lưu trữ biểu đồ.
Việc sử dụng biểu diễn con giúp dễ dàng tìm thấy các nút con của một nút được chỉ định trong cây, nhưng rất khó tìm thấy các nút cha của một nút được chỉ định trong cây.
Biểu diễn anh chị em con là một cách để lưu trữ một cây theo cấu trúc xâu chuỗi. Mỗi nút chứa các trường con trỏ con và các trường con trỏ anh em. Chúng ta sử dụng firstchild và nextsibling tương ứng. Trường con trỏ con chỉ ra nút con đầu tiên trỏ đến nút hiện tại và nút anh chị em chỉ ra nút anh em tiếp theo trỏ đến nút hiện tại. Bản chất của nó trước tiên là chuyển đổi một cây thành cây nhị phân và sau đó lưu trữ nó trong cấu trúc chuỗi nhị phân.
Biểu diễn anh em con có thể chuyển đổi các phép toán trên cây thành các phép toán trên cây nhị phân. Phương pháp biểu diễn này được sử dụng rộng rãi trong các ứng dụng thực tế.
Do đó, mã để tạo cây bằng cách biểu diễn em trai được đưa ra ở đây. Phương pháp biểu diễn này cũng sẽ được sử dụng trong các bài viết sau.
Trung tâm cá nhân
Điều phát hành
từ bỏ
typedef char Elemtype; //Cây (biểu diễn anh chị em con) typedef struct CSNode{ Dữ liệu Elemtype; struct CSNode *firstchild; // struct con đầu tiên CSNode *nextsibling; // Anh chị em tiếp theo}CSSNode, *CSTree; ){ Dữ liệu kiểu Elemtype; CStree T; scanf("%c", &data); //Nhập dữ liệu nút getchar(); '#') //Enter - để dừng tạo cây con return NULL; T = (CSTree)malloc(sizeof(CSNode)); T->data = data printf("Nhập dữ liệu con đầu tiên của %c (# Stop) ): ", data); //Tạo đệ quy T->firstchild = Create_CSTree(); printf("Nhập dữ liệu anh em tiếp theo của %c (#Stop): ", data); T->nextsibling = Tạo_CSTree(); trả về T }
Cây nhị phân là cây có thứ tự với cấp độ nút không quá 2. Đây là cấu trúc dữ liệu quan trọng đơn giản nhưng được sử dụng rộng rãi.
//Cấu trúc cây nhị phân typedef struct BiNode{ Dữ liệu Elemtype; struct BiNode *leftchild; // Con trái struct BiNode *rightchild; // Con phải}BiNode, *BinaryTree;
Nói một cách dễ hiểu thì một khu rừng là tập hợp của nhiều cây.
// Cấu trúc rừng typedef struct { CSTree ct[MAX]; int n; // Số cây}rừng, *Rừng;
(1) Kết nối từng anh em liền kề trong cây; (2) Ngắt kết nối từng nút trừ nút con đầu tiên khỏi các nút anh em khác và các nút cha của chúng; (3) Xoay một cách thích hợp cây đã xử lý có dạng cây nhị phân.
Vì chúng ta đang sử dụng cách biểu diễn anh chị em con nên cây thực sự được lưu trữ trong một cấu trúc tương tự như cây nhị phân. Do đó, con đầu lòng của cây tương ứng với con trái của cây nhị phân cần chuyển đổi, còn con kế tiếp tương ứng với con bên phải của cây nhị phân cần chuyển đổi. Chúng ta chỉ cần thao tác đệ quy để làm cho sự tương ứng một-một bằng nhau.
//Cây được chuyển đổi thành cây nhị phân BinaryTree CSTree_Transform_to_BinaryTree(CSTree ct){ if(!ct) return NULL; BinaryTree T = (BinaryTree)malloc(sizeof(BiNode)); /Tương đương với việc chuyển đổi Left trở thành con đầu lòng, right trở thành anh chị em tiếp theo. Dạng cơ bản T->leftchild =. CSTree_Transform_to_BinaryTree(ct->firstchild); T->rightchild = CSTree_Transform_to_BinaryTree(ct->nextsibling return T;
(1) Trước tiên, điều chỉnh tất cả các nút con bên phải của cây nhị phân thành cùng một lớp; (2) Nếu một nút là nút con bên trái của nút cha, hãy kết nối các nút bên trái và bên phải ở bên phải của nút với nút cha của nó. (3) Xóa tất cả các nút trong cùng một lớp Kết nối ngang.
Chuyển đổi cây nhị phân thành cây thực chất là thao tác nghịch đảo của việc chuyển đổi cây thành cây nhị phân, về cơ bản là giống nhau. Nó cũng chỉ yêu cầu các phép toán đệ quy để làm cho con trái bằng con đầu lòng và con phải bằng con kế tiếp.
//Chuyển đổi cây nhị phân thành cây CSTree BinaryTree_Transform_to_CSTree(BinaryTree bt){ if(!bt) return NULL; CSTree T = (CSTree)malloc(sizeof(CSNode)); Tương đương với việc chuyển đổi con đầu lòng trở thành bên trái, anh chị em tiếp theo trở thành bên phải. BinaryTree_Transform_to_CSTree(bt->leftchild); T->nextsibling = BinaryTree_Transform_to_CSTree(bt->rightchild return T }
(1) Chuyển đổi từng cây trong rừng thành cây nhị phân; (2) Kết nối các nút gốc của từng cây nhị phân thông qua cây con bên phải theo thứ tự ban đầu để trở thành cây nhị phân hoàn chỉnh.
Forest sử dụng cấu trúc tuần tự để lưu trữ nhiều cây nên chúng ta chỉ cần đánh dấu chỉ số vị trí của cây hiện tại là thấp và dừng đệ quy khi hoạt động đệ quy đạt mức cao.
//Khu rừng được chuyển đổi thành cây nhị phân BinaryTree Forest_Transform_to_BinaryTree(CSTree ct[], int low, int high){ if(low > high) return NULL // Mỗi cây trở thành cây nhị phân BinaryTree T = CSTree_Transform_to_BinaryTree(ct[low ]); / /Kết nối nút gốc của mỗi cây nhị phân thông qua rightchild T->rightchild = Forest_Transform_to_BinaryTree(ct, low + 1, high); return T }
Trong quá trình chuyển đổi rừng thành cây nhị phân ở trên, chúng ta có thể thấy rằng tất cả các nút dọc theo phía dưới bên phải của cây nhị phân tính từ nút gốc đều tương ứng chính xác với nút gốc của mỗi cây trong rừng Bắt đầu từ điểm này. , chúng ta thực hiện thao tác nghịch đảo của việc chuyển đổi rừng thành cây nhị phân, Điều này hoàn thành việc chuyển đổi cây nhị phân thành rừng.
(1) Ngắt kết nối tất cả các kết nối khỏi nút gốc của cây nhị phân dọc theo nút con phía dưới bên phải và chia thành nhiều cây nhị phân; (2) Chuyển từng cây nhị phân thành một cây để tạo thành một rừng.
Chúng ta xác định một con trỏ p bắt đầu từ nút gốc của cây nhị phân và đi hết về bên phải, đồng thời, chúng ta xác định một q để ghi lại nút bị ngắt kết nối, nghĩa là p->phải và ngắt kết nối. lần lượt kết nối của con bên phải, từ đó chuyển đổi tất cả các cây nhị phân thành Cây.
//Chuyển đổi cây nhị phân thành rừng Forest BinaryTree_Transform_to_Forest(BinaryTree bt){ Forest F = (Forest)malloc(sizeof(forest)); BinaryTree p = bt; BinaryTree q = NULL int count = 0; q = p ->rightchild; //q trỏ tới nút tiếp theo bị cắt (tức là nút con phải của nó) p->rightchild = NULL; // Cắt kết nối để tạo thành một cây riêng biệt F->ct[count++] = BinaryTree_Transform_to_CSTree(p); // Cây nhị phân được chuyển đổi thành cây và được lưu trữ trong forest p = q; và lặp lại thao tác} F->n = count //Ghi số cây trong rừng return F }
Cuối cùng, bài viết này về việc chuyển đổi cây [cấu trúc dữ liệu], cây nhị phân và rừng kết thúc tại đây. Nếu bạn muốn biết thêm về việc chuyển đổi cây [cấu trúc dữ liệu], cây nhị phân và rừng, vui lòng tìm kiếm các bài viết của CFSDN hoặc tiếp tục. Duyệt các bài viết liên quan, tôi hy vọng bạn sẽ ủng hộ blog của tôi trong tương lai! .
29
4
0
Chúng tôi đang chạy cụm nút MarkLogic 9.0-11 phiên bản 3 và MarkLogic được cài đặt trong thư mục "/var/opt/MarkLogic/", chúng tôi đã tạo "/var/opt/MarkLogic/
Tôi có một rừng có chiều cao tùy ý, đại khái như thế này: let data = [ { "id": 2, "name": "AAA", "parent_id": null, "short_name": "A" },
Đã đóng cửa. Câu hỏi này không tuân thủ nguyên tắc Stack Overflow. Câu trả lời không được chấp nhận vào thời điểm này. Sự cố này dường như không liên quan đến việc lập trình trong phạm vi được xác định trong trung tâm trợ giúp. Đã đóng cửa 7 năm trước. Cải thiện
Tôi có một từ điển sâu khổng lồ đại diện cho một khu rừng (nhiều cây không nhị phân) và tôi muốn xử lý khu rừng và tạo một tệp văn bản chứa tất cả các mối quan hệ có thể có của khu rừng, ví dụ như đưa ra từ điển: {'a': {' b': {'c ': {}, 'd': {}}, 'g': {}}
Trong ứng dụng Android của tôi, tôi bao gồm Google Maps. Bây giờ tôi muốn lấy thông tin về khu vực xung quanh bạn. Ví dụ: bạn đang ở trong công viên/rừng/bãi biển...vì vậy về cơ bản tôi muốn câu trả lời bằng "nước" cho tọa độ đầu vào 53°33'40.9"N 10°00'
Nếu tôi có bảng sau: Member_Key Member_Name col1 Mem1 col2 Mem2 col3 Mem3 col4
Tiếp tục với câu hỏi cũ của tôi: Viết từ điển lồng nhau (rừng) có độ sâu rất lớn vào một tệp văn bản. Bây giờ tôi muốn viết quá trình duyệt rừng theo kiểu BFS: Tôi có độ sâu rất lớn
Tôi có môi trường nhiều miền (nhóm thư mục sự kiện), chẳng hạn như subdomain1.mydomain.com, subdomain2.mydomain.com trong đó mydomain.com là miền AD gốc (GC) và su
Tôi muốn biết liệu có thể khôi phục loại địa hình (núi, rừng, mặt nước, đồng bằng, v.v.) trên bản đồ Google hoặc bản đồ Bing Mag 2D/3D hay không. Để tạo bản đồ dựa trên vị trí của người chơi trong thế giới thực, tôi nghĩ AP đã có sẵn!
Tôi là một lập trình viên xuất sắc, rất giỏi!