[C++] Sort trong cây nhị phân

[13520797]

Có 1 cây nhị phân vs phần data là tổ hợp 1 số thuộc tính .v.v và việc xây dựng cây chỉ dựa trên 1 thuộc tính A nào đó thì bây h nếu có yêu cầu in ra 1 cách thứ tự của 1 thuộc tính B khác A của tree này thì có thuật toán hay giải pháp nào làm cho quá trình sort này nhanh hơn là sẽ duỗi thẳng cây ra thành dạng dãy hay list để sort rùi show kq?
vd: 1 cây vs data: mssv (ko trùng nhau) / điểm / tên /....blah vs việc xây dựng lấy mssv .thì sort theo điểm in ra full 1 sv thì làm sao cho lợi ?

[13520336]

theo tui nghĩ thì ko thể.
vì cây nhị phân sắp xếp theo MSSV rồi thì thuộc tính điểm nó tùm lum ngẫu nhiên trong cây rồi, ko biến cây thành ds để sắp xếp sao được.
Tui có ý tưởng là, duyệt cây sắp xếp theo MSSV, lấy giá trị điểm của từng cái tạo thành 1 cây mới sắp xếp theo điểm. Tại 1 nút điểm có 2 người trùng điểm thì tại đó tạo thành 1 dslk chứa những người trùng điểm. Hoặc tạo 1 cây sắp xếp theo MSSV hoặc thuộc tính khác tại nút đó

[13520797]

nói vậy thì cũng phải tốn thêm bộ nhớ thôi.duỗi thẳng em nó ra nghĩa là dựng thằng khác rồi chép qua thôi.làm như ông anh thì có vẻ phù du rắc rối hơn

[truonganpn]

Duỗi thẳng cây ra là chuyện dĩ nhiên phải làm. Còn việc sort lại thì phải chọn thuật toán có khả năng sắp xếp ngay khi duỗi chứ không phải duỗi hết rồi mới sắp, những thuật toán như vậy gọi chung là online algorithm, insertion sort và merge sort là những ví dụ tốt.

[13520797]

Duỗi thẳng cây ra là chuyện dĩ nhiên phải làm. Còn việc sort lại thì phải chọn thuật toán có khả năng sắp xếp ngay khi duỗi chứ không phải duỗi hết rồi mới sắp, những thuật toán như vậy gọi chung là online algorithm, insertion sort và merge sort là những ví dụ tốt.

thế ko duỗi ko được hả thầy.vậy thì tốn kém loài

[09520200]

thế ko duỗi ko được hả thầy.vậy thì tốn kém loài

Ko hẳn gọi là duỗi...cứ duyệt cây như bình thường....rồi với từng nút duyệt được thì thực hiện chèn vào mảng rồi sort trực tiếp bằng insertion hoặc merge sort. Như thế khi vừa duyệt hết cây thì mảng kết quả cũng đã sort xong.
Tiết kiệm hơn so với duỗi ra mảng rồi sort mảng đó

[13520336]

nói vậy thì cũng phải tốn thêm bộ nhớ thôi.duỗi thẳng em nó ra nghĩa là dựng thằng khác rồi chép qua thôi.làm như ông anh thì có vẻ phù du rắc rối hơn

sao lại rắc rối, nếu tạo 1 cây mới thì giá trị điểm trùng nhau thì s sắp xếp lên cây nhị phân?
không thì cứ sort theo a ở trên

[09520147]

Ko hẳn gọi là duỗi...cứ duyệt cây như bình thường....rồi với từng nút duyệt được thì thực hiện chèn vào mảng rồi sort trực tiếp bằng insertion hoặc merge sort. Như thế khi vừa duyệt hết cây thì mảng kết quả cũng đã sort xong.
Tiết kiệm hơn so với duỗi ra mảng rồi sort mảng đó

Quá chuẩn ông anh! Rõ ràng duỗi ra rồi sắp xếp là trường hợp xấu nhất!