bvd

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!

 | 
RR
  1. Câu này của bạn không biết trả lời như nào, vì thông thường người ta dùng 3 loại thứ tự trên cây:
    • Pre-order:
    • procedure preorder(x : PNode)
begin
  writeln(x^.value);
  if (x^.left != nilT) preorder(x^.left);
  if (x^.right != nilT) preorder(x^.right);
end;

       

    • Post-order
    • procedure postorder(x : PNode)
begin
  if (x^.left != nilT) preorder(x^.left);
  if (x^.right != nilT) preorder(x^.right);
  writeln(x^.value);
end;

       

    • In-order
    • procedure inorder(x : PNode)
begin
  if (x^.left != nilT) preorder(x^.left);
  writeln(x^.value);
  if (x^.right != nilT) preorder(x^.right);
end;

       

  2. Tùy cách cài đặt. Thông thường khi xóa nút x thì có thể thay nó bằng nút phải nhất của cây con trái, hoặc nút trái nhất của cây con phải.

  3.  

  4.  

  5. @@ ý bạn là đệ quy?

bvd
Trả lời RR
  Hiện bài gốc

1, Duyệt theo thứ tự giữa là duyệt theo kiểu in-order nhé

Rút kinh nghiệm lần sau chú thích thuật ngữ tiếng Anh bên cạnh để ai cũng hiểu

Các câu 3,4,5 cũng tự trả lời được rồi

Cảm ơn RR

© VNOI Team 2015