}else{ TOP = -1; //khởi tạo STACK rỗng P = TREE; //P dùng để duyệt cây, gán thành gốc cây while(TOP > -1 || P != NULL){ while(P != NULL){ PUSH(STACK, TOP, P); //lưu địa chỉ gốc.. P = P->P_L; //..rồi chuyển đến con trái } //sau cái while này mình sẽ ở nút NULL trái nhất của cây (hoặc cây con) //...và P sẽ là NULL P = POP(STACK, TOP); printf(P->DATA); //in thông tin P = P->P_R; //chuyển qua bên phải (có thể chuyển thành NULL) }}} 7. Trình bày (bằng ngôn ngữ tựa C) giải thuật tìm kiếm nhị phân. Đánh giá thời gian thực hiện giải thuật với dãy có n phần tử. TK_NP(K, size, x){ int t = 0; //vị trí phần từ đầu tiên trog mảng int p = size - 1; //vt phần từ cuối while(t <= p){ int g = (t + p) / 2; //vt pt giữa trái và phải if(K[g] == x){ return g; } if(x < K[g]){ p = g - 1; }else{ t = g + 1; } } printf("Không tìm thấy!"); return -1; } Xét giải thuật nêu trên, ta thấy: - Trường hợp tốt nhất là khi phần từ giữa mảng ban đầu là giá trị cần tìm, trong trường hợp này độ phức tạp là O(1) - Trường hợp xấu nhất là khi phần tử cuối cùng bằng x hoặc không tìm thấy, khi đó dãy phải tiếp tục chia đôi đến khi còn 1 phần tử
Ta có w(n) biểu thị số lượng phép tính cần thiết:
w(n) = 1 + w(n/2) //cần 1 phép tính để chia đôi mảng = 1 + 1 + w(n/2^2) ... = k + w(n/2^k);
Vì chương trình chỉ dừng khi dãy có độ dài = 1 --> n/2^k = 1 --> 2^k = n --> log2(n) = k w(n) = log2(n) + w(1) = log2(n) + 1
