Cây n-ary C++
|
N-ary tree là cấu trúc dữ liệu dạng cây cho phép chúng ta có tối đa n nút con cho mỗi nút, khác với cây nhị phân chuẩn chỉ cho phép tối đa 2 nút con cho mỗi nút. Show
 Cách tiếp cận tối ưu cho biểu diễn cây N-aryNhư thể hiện trong hình trên, chúng ta có thể thử chuyển đổi cây n-ary thành cây nhị phân bằng cách xóa liên kết từ nút cha đến từng nút con. Chúng tôi chỉ có thể giữ hai liên kết cho mỗi nút. một liên kết đến nút con đầu tiên và nút anh chị em tiếp theo. Các nút anh chị em là các nút ở cấp độ có cùng cha mẹ. Chúng ta có thể chuyển đổi một cây n-ary thành biểu diễn này bằng các bước sau
Chúng ta có thể thấy rằng vì không cần thêm liên kết nào nên phương pháp này tiết kiệm không gian. Ngoài ra, tất cả các nút có kích thước không đổi và chúng tôi không cần mảng động để lưu trữ thông tin về trẻ em. Với cách biểu diễn trên, tất cả các nút n-ary có thể xem như cây nhị phân, dễ hình dung và thao tác trên Phương pháp này được thảo luận chi tiết dưới đây. Chúng ta sẽ thảo luận về tất cả các hoạt động trên cây n-ary khi xem xét biểu diễn thứ hai của một nút (sử dụng mảng động). Trước khi xem xét các hoạt động khác nhau của cây n-ary, hãy xem xét các loại cây n-ary khác nhau Các loại cây n-aryCây n-ary đầy đủCây n-ary đầy đủ là cây n-ary cho phép mỗi nút có 0 hoặc n nút con. Hình ảnh sau đây cho thấy một đại diện bằng hình ảnh của một cây n-ary đầy đủ Trong hình trên, tất cả các nút có 0 hoặc 3 nút con Cây n-ary hoàn chỉnhCây n-ary đầy đủ là cây n-ary trong đó các nút ở mỗi cấp độ cây phải có chính xác n con (chúng đầy đủ), ngoại trừ các nút ở cấp độ cuối cùng. Nếu các nút ở cấp độ cuối cùng không hoàn thành, các nút phải được để lại càng tốt. Hình ảnh sau đây cho thấy một đại diện bằng hình ảnh của một cây n-ary hoàn chỉnh Trong hình trên, tất cả các nút (ngoại trừ cấp cuối cùng) đều có ba nút con và các nút không đầy đủ càng nhiều càng tốt Cây n-ary hoàn hảoCây n-ary hoàn hảo là cây n-ary đầy đủ, nhưng mức của các nút lá phải giống nhau. Hình ảnh sau đây cho thấy một đại diện bằng hình ảnh của một cây n-ary hoàn hảo Cây n-ary sau đây sẽ được xem xét để thảo luận về các ví dụ cho các thao tác khác nhau trên cây n-ary Trình duyệt đặt hàng trước của cây n-aryTrong một lần duyệt theo thứ tự trước của cây n-ary, nút gốc được thăm; . Khi nút gốc được duyệt trước (hoặc trước) bất kỳ cây con nào, nó được gọi là duyệt theo thứ tự trước đầu ra ví dụ. [A, B, E, F, C, D] Duyệt theo thứ tự của cây n-aryTruyền tải theo thứ tự sau là một truyền tải trong đó trước tiên chúng ta duyệt qua các cây con theo cách đệ quy trong truyền tải theo thứ tự sau và truy cập nút gốc ở cuối đầu ra ví dụ. [E, F, B, C, D, A] Duyệt thứ tự cấp của cây n-aryTrong quá trình truyền tải thứ tự cấp độ, chúng tôi xử lý tất cả các nút cây theo độ sâu. đầu tiên là gốc, sau đó là con của gốc, v.v. Quá trình này tương đương với tìm kiếm theo chiều rộng từ gốc đầu ra ví dụ. [[A], [B, C, D], [E, F]] Độ sâu tối đa của cây n-aryĐộ sâu tối đa của cây n-ary còn được gọi là chiều cao của cây n-ary. Độ sâu tối đa là số nút dọc theo con đường dài nhất từ nút gốc xuống nút lá xa nhất đầu ra ví dụ. 3 Chuyển đổi cây n-ary thành cây nhị phânChúng ta đã thấy rằng chỉ lưu trữ hai thứ, nút con đầu tiên và nút anh chị em tiếp theo của một nút trong cây n-ary, dẫn đến cách biểu diễn nút cây n-ary tiết kiệm không gian nhất. Chúng tôi đang chuyển đổi cây n-ary thành cây nhị phân bằng cách sử dụng biểu diễn này Chuyển đổi cây n-ary tùy ý thành cây nhị phân sẽ chỉ làm tăng chiều cao của cây. Hãy xem chiều cao tăng bao nhiêu. Giả sử chúng ta có một cây n-ary hoàn hảo với m nút. Chúng ta biết rằng trong một cây n-ary hoàn hảo, tất cả các nút đều có 0 hoặc n con, với mức cuối cùng là như nhau. Gọi chiều cao của cây là h. Điều kiện sau đây đúng cho một cây n-ary hoàn hảo với m nút có chiều cao h Điều này đơn giản hóa để Ta có kết quả sau, trong đó D là độ sâu của cây n-ary Bây giờ, nếu chúng ta chuyển đổi cây n-ary thành cây nhị phân, số nút, m, sẽ giữ nguyên. Độ sâu, trong trường hợp đó, sẽ là O(log2 m) Từ các tính toán trên, chúng ta có thể kết luận rằng chiều cao của cây tăng theo hệ số không đổi và sẽ không ảnh hưởng đến độ phức tạp thời gian trong trường hợp xấu nhất Để chuyển đổi cây n-ary thành cây nhị phân, đầu tiên, chúng ta sẽ liên kết tất cả các nút con trực tiếp của nút cha đã cho với nhau để tạo thành một danh sách liên kết. Sau đó, chúng tôi giữ liên kết từ cha mẹ đến con đầu tiên (con ngoài cùng bên trái) và xóa tất cả các liên kết khác với phần còn lại của con. Lặp lại quy trình này cho tất cả các nút con cho đến khi chúng tôi xử lý xong tất cả các nút bên trong và xoay cây 45 độ theo chiều kim đồng hồ. Cây thu được là biểu diễn cây nhị phân mong muốn của cây n-ary đã cho đầy đủ là gìCây n-ary đầy đủ là cây trong đó mỗi nút có n nút con hoặc không có nút con nào .
N trong n là gìN-ary trees là cấu trúc dữ liệu dạng cây cho phép chúng ta có tối đa n nút con cho mỗi nút , khác với . Hình trên cho thấy một ví dụ về cây n-ary.
Cây nhị phân trong C là gì?Cây nhị phân là một loại cấu trúc dữ liệu trong đó mỗi nút có tối đa hai nút con (con trái và con phải) . Cây nhị phân được sử dụng để triển khai cây tìm kiếm nhị phân và đống nhị phân, đồng thời được sử dụng để tìm kiếm và sắp xếp hiệu quả. Cây nhị phân là trường hợp đặc biệt của cây K-ary, trong đó k là 2.
chiều cao của n là bao nhiêuChiều cao của một cây m-ary hoàn chỉnh có n nút là trần(log m n . tất cả các nút trừ nút gốc và nút lá có ít nhất m/2 nút con và nhiều nhất là m nút con. Root có ít nhất 2 con và nhiều nhất m con. . all nodes except for the root and the leaves have at least m/2 children and at most m children. The root has at least 2 children and at most m children. |
