Cho cây sau:
Khi ta duyệt theo thứ tự giữa:
1, Nút liền trước của nút 3 là nút -4, nút liền trước của nút -4 là 2 phải không? (đã tự giải đáp được rồi :( )
2, Sau khi xóa nút 2 thì nút -4 sẽ lên thay thế nút 2 phải không?
3, Trong thuật toán tìm nút liền trước, không gặp nút nào chứa x trong nhánh con phải thì nó là nút cực trái phải không (câu này cũng đã dùng thực tế kiểm chứng được rồi)
4,
{
Dòng có // là những phần mình định thay thế, thêm vào.
Dòng {} {dùng để hỏi
Code gốc lấy từ quyển 2 "Tài liệu giáo khoa chuyên Tin"
}
function Predecessor(x: PNode): PNode;
// var y,yp: PNode;
begin
// y:=x;
if x^.left ≠ nilT then
Result := Maximum(x^.left)
else
repeat
//yp:=y;
Result := x^.parent; // thay thế bằng y:=y^.parent;
if (Result = nilT) or (x = Result^.right) then Break; // Đoạn này mình sẽ thay thế Result = y, x = yp
x := Result; {Lệnh này có sai không vậy, sao không cần var x: PNode mà vẫn chạy được?}
until False;
// Result:=y;
end;
5, Sao các thuật toán về cây trong sách "Tài liệu giáo khoa chuyên Tin" đều không dùng đệ quy vậy? (phải đặt lại bộ nhớ Stack chăng?)
Khi nào cần hỏi gì nữa thì mình sẽ hỏi tiếp ở topic này nhé :)
Xin cảm ơn trước!