12) Trình bày giải thuật tìm kiếm có bổ sung trên cây nhị phân tìm kiếm. Dựng cây nhị phân tìm kiếm với dãy khóa nhập vào là: 10, 7, 19, 11, 3, 16, 13, 4, 22, 5.

Bài làm:

Function BST(T,X);

P := null; q = T;

While q <> null do

Case

X <Key(q): p := q; //Lưu cha của q

                  q := P_Trai(q);

X = Key(q) : Return(q);

X > Key(q) : p := q;

                    q := P_Phai(q);

End Case; //Không tìm thấy, cần bổ sung

New(q);

Key(q) := X;

P_Trai(q) := null;

P_Phai(q) := null;

Case

T = null : T := q;

X < Key(P) : P_Trai(P) := q;

X > Key(P) : P_Phai(P) := q;

End Case;

Write(“Khong tim thay, da bo sung”);

Return (q);

Dựng cây nhị phân:

10: Gốc

7: Con trái của 10, 19: Con phải của 10

3: Con trái của 7, 11: Con trái của 19, 22: Con phải của 19

4: Con phải của 3, 16: Con phải của 11

5: Con phải của 4, 13: Con trái của 16