Em muốn duyệt cây theo mức
Cho em hỏi là em bị lỗi chỗ vậy ạ, em thấy lỗi truy cập vào phần tử ko được phép nhưng em ko biết ở đâu
Test case:
1
2
1 2 R 1 3 L
Cây nhị phân duyệt theo mức
Em muốn duyệt cây theo mức
Cho em hỏi là em bị lỗi chỗ vậy ạ, em thấy lỗi truy cập vào phần tử ko được phép nhưng em ko biết ở đâu
Test case:
1
2
1 2 R 1 3 L
à đoạn này là em duyệt theo kiểu preorder, e có nhầm lẫn chút, nhưng em vẫn muốn tìm lỗi sai về mặt truy cập vào phần tử ko được phép ạ
- Ở hàm insert node, cậu thiếu logic tìm kiếm node u để insert.
- Hàm make root lẽ ra nên là make node.
- Hàm level order cậu không có logic kiểm tra nếu root == null thì ignore.
Đó là lý do cậu sẽ dính đòn khi truy cập root->left với root == null - Đặt level order vào trong loop thì không ổn rồi
Nó nên ở ngoài loop.
À, mà đề bài của cậu là gì thế nhỉ?
4 Likes
Dạ đề bài em là: Cho cây nhị phân, nhiệm vụ của bạn là duyệt cây theo Level-order. Phép duyệt level-order trên cây là phép thăm node theo từng mức của cây. Ví dụ với cây dưới đây sẽ cho ta kết quả của phép duyệt level-order: 20 8 22 4 12 10 14.
- Dòng đầu tiên đưa vào số lượng test T.
- Những dòng tiếp theo đưa vào các bộ test. Mỗi bộ test gồm 2 dòng: dòng đầu tiên đưa vào số N là số lượng cạnh của cây; dòng tiếp theo đưa vào N bộ ba (u, v, x), trong đó u là node cha, v là node con, x= R nếu v là con phải, x=L nếu v là con trái; u, v, x được viết cách nhau một vài khoảng trống.
- T, N, u, v, thỏa mãn ràng buộc: 1≤T≤100; 1≤N≤103; 1≤u, v≤104;
1 Like
E cám ơn e hiểu r ạ. Còn đoạn level order e đặt vào loop là do t là số test case ạ, mỗi test e duyệt 1 lần ạ.
Cái này gồm hai giai đoạn là dựng cây và duyệt BFS trên cây 
Để dựng cây thì bạn phải tìm node u trước cho mỗi bộ ba. Có std::unordered_map rồi thì ko cần duyệt cây ở bước này (gán cho value là con trỏ).
2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?