Bài giảng Cấu trúc dữ liệu và giải thuật (đầy đủ)

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (501040)Giới thiệuMôn học giới thiệu:Các cấu trúc dữ liệu cơ bảnCác giải thuật điển hình trên các cấu trúc dữ liệu đóDùng phương pháp hướng đối tượng. Ngôn ngữ lập trình minh hoạ:Mã giả (pseudocode)C++ (không được giảng dạy chính thức trong môn học)Nội dungChương 1. Tổng quanChương 2. StackChương 3. QueueChương 4. Đệ quiChương 5. List và StringChương 6. Cây nhị phânChương 7. Tìm kiếmChương 8. Sắp xếpProgramming Fundamentals*Một số thuật ngữ căn bảnMột chương trình máy tính (computer program) là tập các câu lệnh để điều khiển một máy tính sinh ra một kết quả cụ thểViết các chương trình máy tính gọi là lập trình máy tính (computer programming)Ngôn ngữ để tạo các chương trình máy tính gọi là ngôn ngữ lập trìnhSoftware là một chương trình hay tập hợp các chương trìnhProgramming Fundamentals*Ngôn ngữ máyCấp thấp nhất. Các chương trình bao gồm 0, 1.Lập trình bằng ngôn ngữ máy có thể điều khiển trực tiếp đến phần cứng máy tínhVí dụ  00101010 000000000001 000000000010 10011001 000000000010 000000000011  Instruction part (opcode – tác vụ được thực hiện)address parts (địa chỉ bộ nhớ của dữ liệuProgramming Fundamentals*Assembly languagesThực hiện cùng nhiệm vụ ngôn ngữ máy nhưng sử dụng tên tượng trưng cho opcode và các toán tử thay vì 1, 0 LOAD BASEPAY ADD OVERPAY STORE GROSSPAYChương trình ngôn ngữ assembly phải được dịch sang ngôn ngữ máy trước khi có thể thực thi bởi máy tínhProgramming Fundamentals*AssemblerTranslation program (assembler)AssemblylanguageprogramMachine language programProgramming Fundamentals*Ngôn ngữ lập trình cấp caoSử dụng các câu lệnh dễ hiểu hơn.Các chương trình sử dụng ngônn ngữ cấp cao phải được dịch sang ngôn ngữ cấp thấp bằng cách sử dụng một chương trình gọi là compilerProgramming Fundamentals*High-level Programming Languages (cont.)Cho phép người lập trình viết các câu lệnh như câu tiếng Anh và các kí hiệu toán học thông dụngMỗi dòng trong chương trình ngôn ngữ mức cao gọi là câu lệnhExample: Result = (First + Second)*ThirdProgramming Fundamentals*Phần mềm ứng dụng và phần mềm hệ thống2 loại chương trình máy tínhApplication software bao gồm những chương trình được viết để thực thi các nhiệm vụ cụ thể được yêu cầu bởi userSystem software là tập các chươg trình phải luôn được sẵn sàng đến bất kì hệ thống máy tính cho nó vận hành (hệ điều hành, bộ chuyển đổi ngôn ngữ)Programming Fundamentals*PROGRAMMING LANGUAGES Một số ngôn ngữ thông dụng FORTRAN 1957 COBOL 1960s BASIC 1960s PASCAL 1971 Structure programming C C++ Object-oriented programming JavaCú pháp (syntax) Cú pháp của một ngôn ngữ lập trình là tập các luật để viết các câu lệnh chính xácProgramming Fundamentals*The C Programming Language In the 1970s, at Bell Laboratories, Dennis Ritchie and Brian Kernighan designed the C programming language.C was used exclusively on UNIX and on mini-computers. During the 1980s, C compilers were written for other flatforms, including PCs. To provide a level of standardization for C language, in 1989, ANSI created a standard version of C, called ANSI C.One main benefit of C : it is much closer to assembly language other than other high-level programming languages.The programs written in C often run faster and more efficiently than programs written in other high-level programming language.Programming Fundamentals*The C++ Programming Language In 1985, at Bell Laboratories, Bjarne Stroutrup created C++ based on the C language. C++ is an extension of C that adds object-oriented programming capabilities.C++ is now the most popular programming language for writing programs that run on Windows and Macintosh. The standardized version of C++ is referred to as ANSI C++.  The ANSI standards also define run-time libraries, which contains useful functions, variables, constants, and other programming items that you can add to your programs. The ANSI C++ run-time library is called Standard Template Library or Standard C++ Library Programming Fundamentals*Giải thuậtDùng C++ để diễn tả?  có vấn đềCó thể diễn tả giải thuật bằng cách sử dụng flowchartFlow chart thể hiện nét phát thảo cấu trúc căn bản và tính logic của chương trìnhMột cách khác để diễn tả giải thuật là sử dụng mã giả pseudocodeGiả lập, thường là dễ hiểu, không chi tiết đến các kỹ thuật lập trìnhỞ cấp độ hết sức tổng quát: gần ngôn ngữ tự nhiênHoặc rất chi tiết: như dùng ngôn ngữ tựa Pascal, tựa C++Các tính chất quan trọng của giải thuật là: 􀂾 Hữu hạn (finiteness): giải thuật phải luôn luôn kết thúc sau một số hữu hạn bước. 􀂾 Xác định (definiteness): mỗi bước của giải thuật phải được xác định rõ ràng và phải được thực hiện chính xác, nhất quán. 􀂾 Hiệu quả (effectiveness): các thao tác trong giải thuật phải được thực hiện trong một lượng thời gian hữu hạn. Ngoài ra một giải thuật còn phải có đầu vào (input) và đầu ra (output). Giải thuật (Algorithm)*Programming Fundamentals*Flowchart symbolsTerminal Input/output   Process  Flowlines   Decision Connector Predefined processProgramming Fundamentals*ExampleNote: Name, Hours and Pay are variables in the program.Programming Fundamentals*Algorithms in pseudo-code Sử dụng các cụm từ như tiếng Anh để mô tả pseudocode. Example:  Input the three values into the variables Name, Hours, Rate. Calculate Pay = Hours  Rate. Display Name and Pay.Programming Fundamentals*LoopsNote:1.   Loop is a very important concept in programming.2.   NUM  NUM + 1 meansold value of NUM + 1 becomes new value of NUM. The algorithm can be described in pseudocode as follows:NUM  4do SQNUM NUM2 Print NUM, SQNUM NUM  NUM + 1while (NUM được A:Lấy ra một => được Q và stack rỗng:QQAQAQỨng dụng: Đảo ngược danh sáchYêu cầu: Đảo ngược một danh sách nhập vàoGiải thuật:1. Lặp lại n lần 1.1. Nhập vào một giá trị 1.2. Đẩy nó vào stack2. Lặp khi stack chưa rỗng 2.1. Lấy một giá trị từ stack 2.2. In raĐảo ngược danh sách – Ví dụCần nhập 4 số vàoBan đầuNhập 11Nhập 515Nhập 7157Nhập 31573Lấy ra => 31573Lấy ra => 7157Lấy ra => 515Lấy ra => 11Stack đã rỗngNgừngĐảo ngược danh sách – Mã C++#include using namespace std;int main( ) { int n; double item; stack numbers; cout > n; for (int i = 0; i > item; numbers.push(item); } while (!numbers.empty( )) { cout =1): bộ thứ tự (Sn-1, t)Sn-1: dãy có chiều dài n-1 thuộc kiểu T t là một giá trị thuộc kiểu T.Stack trừu tượngMột stack kiểu T:Một dãy hữu hạn kiểu TMột số tác vụ:1. Khởi tạo stack rỗng (create)2. Kiểm tra rỗng (empty)3. Đẩy một giá trị vào trên đỉnh của stack (push)4. Bỏ giá trị đang có trên đỉnh của stack (pop)5. Lấy giá trị trên đỉnh của stack, stack không đổi (top)Thiết kế stackenum Error_code {fail, success, overflow, underflow};template class Stack {public: Stack(); //constructor bool empty() const; //kiểm tra rỗng Error_code push(const Entry &item); //đẩy item vào Error_code pop(); //bỏ phần tử trên đỉnh Error_code top(Entry &item); //lấy giá trị trên đỉnh //khai báo một số phương thức cần thiết khácprivate: //khai báo dữ liệu và hàm phụ trợ chỗ này};Thiết kế các phương thứctemplate bool Stack::empty() const;Pre: Không cóPost: Trả về giá trị true nếu stack hiện tại là rỗng, ngược lại thì trả về falsetemplate Error_code Stack::push(const Entry &item);Pre: Không cóPost: Nếu stack hiện tại không đầy, item sẽ được thêm vào đỉnh của stack. Ngược lại trả về giá trị overflow của kiểu Error_code và stack không đổi.template Error_code Stack::pop() const;Pre: Không cóPost: Nếu stack hiện tại không rỗng, đỉnh của stack hiện tại sẽ bị hủy bỏ. Ngược lại trả về giá trị underflow của kiểu Error_code và stack không đổi.template Error_code Stack::top(Entry &item) const;Pre: Không cóPost: Nếu stack hiện tại không rỗng, đỉnh của stack hiện tại sẽ được chép vào tham biến item. Ngược lại trả về giá trị fail của kiểu Error_code.Hiện thực stack liên tụcKhai báo stack liên tụcconst int maxstack = 10; //small number for testingtemplate class Stack {public: Stack( ); bool empty( ) const; Error_code pop( ); Error_code top(Entry &item) const; Error_code push(const Entry &item);private: int count; Entry entry[maxstack];};Đẩy một phần tử vào stackGiải thuật: 1. Nếu còn chỗ trống trong stack 1.1. Tăng vị trí đỉnh lên 1 1.2. Chứa giá trị vào vị trí đỉnh của stack 1.3. Tăng số phần tử lên 1top157count=2count=3Bỏ phần tử trên đỉnh stackGiải thuật: 1. Nếu còn phần tử trong stack 1.1. Giảm vị trí đỉnh đi 1 1.2. Giảm số phần tử đi 1top157count=3count=2Thêm/Bỏ phần tử - Mã C++template Error_code Stack:: push(const Entry &item) { if (count >= maxstack) return overflow; else entry[count++] = item; return success;}template Error_code Stack:: pop() { if (count == 0) return underflow; else count--; return success;}Lấy giá trị trên đỉnh stackGiải thuật: 1. Nếu còn phần tử trong stack 1.1. Trả về giá trị tại vị trí đỉnhMã C++: template Error_code Stack:: top(Entry &item) { if (count == 0) return underflow; else item = entry[count - 1]; return success; }Reverse Polish CalculatorMô tả bài toán:Các toán hạng được đọc vào trước và đẩy vào stackKhi đọc vào toán tử, lấy hai toán hạng ra từ stack, tính toán với toán tử này, rồi đẩy kết quả vào stackThiết kế phần mềm:Cần một stack để chứa toán hạngCần hàm get_command để nhận lệnh từ người dùngCần hàm do_command để thực hiện lệnhReverse Polish Calculator – Thiết kế chức năngTập lệnh:‘?’: đọc một giá trị rồi đẩy vào stackToán tử ‘+’, ‘-’, ‘*’, ‘/’: lấy 2 giá trị trong stack, tính toán và đẩy kết quả vào stackToán tử ‘=’: in đỉnh của stack ra‘q’: kết thúc chương trìnhReverse Polish Calculator – Ví dụBan đầuTính toán biểu thức: 3 5 + 2 * =Toán tử ?Nhập vào 33Toán tử ?Nhập vào 535Toán tử +Lấy ra 5 và 3Tính 3 + 5 => 835Đẩy 8 vào8Toán tử *Lấy ra 2 và 8Tính 8 * 2 => 168Đẩy vào 1616Toán tử =In ra 1616Toán tử ?Nhập vào 282216Reverse Polish Calculator –Hàm get_commandchar get command( ) { char command; bool waiting = true; cout :"; while (waiting) { cin >> command; command = tolower(command); if (command == ‘?’ || command == ‘=‘ || command == ‘+’ || command == ‘−’|| command == ‘*’ || command == ‘/’ || command == ‘q’) waiting = false; else { cout &numbers);int main( ) { Stack stored_numbers; introduction( ); instructions( ); while (do_command(get_command( ), stored_numbers));}//implementationReverse Polish Calculator –Hàm do_commandbool do_command(char command, Stack &numbers) { double p, q; switch (command) { case '?’: cout > p; if (numbers.push(p) == overflow) cout class Queue {public: Queue(); //constructor bool empty() const; //kiểm tra rỗng Error_code append(const Entry &item); //đẩy item vào Error_code serve(); //bỏ 1 phần tử ở đầu Error_code retrieve(Entry &item); //lấy giá trị ở đầu //khai báo một số phương thức cần thiết khácprivate: //khai báo dữ liệu và hàm phụ trợ chỗ này};Thiết kế các phương thứctemplate bool Queue::empty() const;Pre: Không cóPost: Trả về giá trị true nếu queue hiện tại là rỗng, ngược lại thì trả về falsetemplate Error_code Queue::append(const Entry &item);Pre: Không cóPost: Nếu queue hiện tại không đầy, item sẽ được thêm vào cuối của queue. Ngược lại trả về giá trị overflow của kiểu Error_code và queue không đổi.template Error_code Queue::serve() const;Pre: Không cóPost: Nếu queue hiện tại không rỗng, đầu của queue hiện tại sẽ bị hủy bỏ. Ngược lại trả về giá trị underflow của kiểu Error_code và queue không đổi.template Error_code Queue::retrieve(Entry &item) const;Pre: Không cóPost: Nếu queue hiện tại không rỗng, đầu của queue hiện tại sẽ được chép vào tham biến item. Ngược lại trả về giá trị underflow của kiểu Error_code.Mở rộng queueCó thêm các tác vụ:Kiểm tra đầy (full)Tính kích thước (size)Giải phóng queue (clear)Lấy giá trị ở đầu và bỏ ra khỏi queue (serve_and_retrieve)Mã C++:template class Extended_queue: public Queue {public: bool full( ) const; int size( ) const; void clear( ); Error_code serve_and_retrieve(Entry &item);};Có các khả năng public, protected, privateTính thừa hưởngDùng tính thừa hưởng:Extended_queue có đầy đủ các thành phần của QueueThêm vào đó các thành phần riêng của mìnhQueue liên tụcDùng một array: Có xu hướng dời về cuối arrayHai cách hiện thực đầu tiên:Khi lấy một phần tử ra thì đồng thời dời hàng lên một vị trí.Chỉ dời hàng về đầu khi cuối hàng không còn chỗABCDBCDBCDEBan đầuLấy ra 1 phần tử:dời tất cả về trướcThêm vào 1 phần tửABCDBCDBCDEBan đầuLấy ra 1 phần tửThêm vào 1 phần tử: dời tất cả về trước để trống chỗ thêm vàoQueue là array vòng (circular array)Array vòng với ngôn ngữ C++Xem array như là một vòng: phần tử cuối của array nối với phần tử đầu của arrayTính toán vị trí kề:i = ((i + 1) == max) ? 0 : (i + 1);if ((i + 1) == max) i = 0; else i = i + 1;i = (i + 1)%max;Điều kiện biên của queue vòngMột số cách hiện thực queue liên tụcMột array với front là phần tử đầu và tất cả các phần tử sẽ được dời lên khi lấy ra một phần tử.Một array có hai chỉ mục luôn tăng chỉ đến phần tử đầu và cuối.Một array vòng có chỉ mục front và rear và một ô luôn trống.Một array vòng có chỉ mục front và rear và một cờ (flag) cho biết queue là đầy (rỗng) chưa.Một array vòng với chỉ mục front và rear có các giá trị đặc biệt cho biết queue đang rỗng.Một array vòng với chỉ mục front và rear và một số chứa số phần tử của queue.Hiện thực queue liên tụcconst int maxqueue = 10; // small value for testingtemplate class Queue {public: Queue( ); bool empty( ) const; Error_code serve( ); Error_code append(const Entry &item); Error_code retrieve(Entry &item) const;protected: int count; int front, rear; Entry entry[maxqueue];};Khởi tạo và kiểm tra rỗngKhởi tạo:template Queue::Queue( ) {count = 0;rear = maxqueue − 1;front = 0;}Kiểm tra rỗng:template bool Queue::empty( ) const {return count == 0;}Dùng biến count để biết số phần tử trong queueThêm một giá trị vào queueGiải thuật:1. Nếu hàng đầy1.1. Báo lỗi overflow2. Tính toán vị trí cuối mới theo array vòng3. Gán giá trị vào vị trí cuối mới này4. Tăng số phần tử lên 14. Báo successABCfrontrearDLoại một giá trị khỏi queueGiải thuật:1. Nếu hàng rỗng1.1. Báo lỗi underflow2. Tính toán vị trí đầu mới theo array vòng3. Giảm số phần tử đi 13. Báo successABCDfrontrearThêm/loại một giá trị – Mã C++template Error_code Queue::append(const Entry &item) { if (count >= maxqueue) return overflow; count++; rear = ((rear + 1) == maxqueue) ? 0 : (rear + 1); entry[rear] = item; return success; }template Error_code Queue::serve() { if (count 0Quá trình đệ qui gồm 2 phần:Trường hợp cơ sở (base case)Trường hợp đệ qui: cố gắng tiến về trường hợp cơ sởVí dụ trên:Giai thừa của n là 1 nếu n là 0Giai thừa của n là n * (giai thừa của n-1) nếu n>0Tính giai thừaĐịnh nghĩa không đệ qui:n! = n * (n-1) * * 1Định nghĩa đệ qui:n! = 1 nếu n=0 n * (n-1)! nếu n>0Mã C++:int factorial(int n) { if (n==0) return 1; else return (n * factorial(n - 1));}Thi hành hàm tính giai thừan=2 2*factorial(1)factorial (2)n=1 1*factorial(0)factorial (1)n=0 return 1;factorial (0)1162n=3 3*factorial(2)factorial (3)Trạng thái hệ thống khi thi hành hàm tính giai thừafactorial(3)factorial(3)factorial(2)factorial(3)factorial(2)factorial(1)factorial(3)factorial(2)factorial(1)factorial(0)factorial(3)factorial(2)factorial(1)factorial(3)factorial(2)factorial(3)tGọi hàmfactorial(3)Gọi hàmfactorial(2)Gọi hàmfactorial(1)Gọi hàmfactorial(0)Trả về từ hàmfactorial(0)Trả về từ hàmfactorial(1)Trả về từ hàmfactorial(2)Trả về từ hàmfactorial(3)Stack hệ thốngThời gian hệ thốngtBài toán Tháp Hà nộiLuật:Di chuyển mỗi lần một đĩaKhông được đặt đĩa lớn lên trên đĩa nhỏBài toán Tháp Hà nội – Thiết kế hàmHàm đệ qui:Chuyển (count-1) đĩa trên đỉnh của cột start sang cột tempChuyển 1 đĩa (cuối cùng) của cột start sang cột finishChuyển count-1 đĩa từ cột temp sang cột finishmagicBài toán Tháp Hà nội – Mã C++void move(int count, int start, int finish, int temp) { if (count > 0) { move(count − 1, start, temp, finish); cout 2Ví dụ: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, Hàm đệ qui:int fibonacci (int n) {if (n alist; alist.traverse(print_int); alist.traverse(increase_int); }Khi gọi tham số hàm, chương trình dịch phải nhìn thấy hàm được gọi.Tùy theo mục đích mà gọicác hàm khác nhau.Hiện thực danh sách liên tụctemplate class List {public: // methods of the List ADT List( ); int size( ) const; bool full( ) const; bool empty( ) const; void clear( ); void traverse(void (*visit)(List_entry &)); Error_code retrieve(int position, List_entry &x) const; Error_code replace(int position, const List_entry &x); Error_code remove(int position, List_entry &x); Error_code insert(int position, const List_entry &x);protected: // data members for a contiguous list implementation int count; List_entry entry[max_list];};Thêm vào một danh sách liên tụcinsert(3, ‘z’)dabc0123456789efghdefghzcount=8count=9Giải thuật thêm vào một danh sách liên tụcAlgorithm Insert Input: position là vị trí cần thêm vào, x là giá trị cần thêm vào Output: danh sách đã thêm vào x1. if list đầy 1.1. return overflow2. if position nằm ngoài khoảng [0..count] 2.1. return range_error //Dời tất cả các phần tử từ position về sau 1 vị trí3. for index = count-1 down to position 3.1. entry[index+1] = entry[index]4. entry[position] = x //Gán x vào vị trí position5. count++ //Tăng số phần tử lên 16. return success;End InsertMã C++ thêm vào một danh sách liên tụctemplate Error_code List :: insert(int position, const List_entry &x) { if (full( )) return overflow; if (position count) return range_error; for (int i = count − 1; i >= position; i−−) entry[i + 1] = entry[i]; entry[position] = x; count++; return success;}Xóa từ một danh sách liên tụcxremove(3, x)dabc0123456789efghdefghcount=8count=7Giải thuật xóa từ một danh sách liên tụcAlgorithm Remove Input: position là vị trí cần xóa bỏ, x là giá trị lấy ra được Output: danh sách đã xóa bỏ phần tử tại position1. if list rỗng 1.1. return underflow2. if position nằm ngoài khoảng [0..count-1] 2.1. return range_error3. x = entry[position] //Lấy x tại vị trí position ra4. count-- //Giảm số phần tử đi 1 //Dời tất cả các phần tử từ position về trước 1 vị trí5. for index = position to count-1 5.1. entry[index] = entry[index+1]6. return success;End RemoveGiải thuật duyệt một danh sách liên tụcAlgorithm Traverse Input: hàm visit dùng để tác động vào từng phần tử Output: danh sách được cập nhật bằng hàm visit //Quét qua tất cả các phần tử trong list1. for index = 0 to count-1 1.1. Thi hành hàm visit để duyệt phần tử entry[index]End TraverseMã C++ duyệt một danh sách liên tụctemplate void List :: traverse(void (*visit)(List_entry &))/* Post: Tác vụ cho bởi hàm visit sẽ được thi hành tại mỗi thành phần của list bắt đầu từ vị trí 0 trở đi. */{ for (int i = 0; i < count; i++) (*visit)(entry[i]);}Chuỗi (string)Chuỗi là một dãy các ký tựVí dụ:“This is a string” là 1 chuỗi có 16 ký tự“” là một chuỗi rỗng (có 0 ký tự)Chuỗi trừu tượng:Có thể xem là danh sáchCó các tác vụ thường dùng:Sao chép (strcpy)Nối kết (strcat)Tính chiều dài (strlen)So sánh 2 chuỗi (strcmp)Tìm một chuỗi trong chuỗi khác (strstr)Cây nhị phânCây nhị phânCây rỗngHoặc có một node gọi là gốc (root) và 2 cây con gọi là cây con trái và cây con phảiVí dụ:Cây rỗng:Cây có 1 node: là node gốcCây có 2 node:Các định nghĩa khácMức:Node gốc ở mức 0.Node gốc của các cây con của một node ở mức m là m+1.Chiều cao:Cây rỗng là 0.Chiều cao lớn nhất của 2 cây con cộng 1(Hoặc: mức lớn nhất của các node cộng 1)Đường đi (path)Tên các node của quá trình đi từ node gốc theo các cây con đến một node nào đó.Các định nghĩa khác (tt.)Node trước, sau, cha, con:Node x là trước node y (node y là sau node x), nếu trên đường đi đến y có x.Node x là cha node y (node y là con node x), nếu trên đường đi đến y node x nằm ngay trước node y.Node lá, trung gian:Node lá là node không có cây con nào.Node trung gian không là node gốc hay node lá.Các tính chất khácCây nhị phân đầy đủ, gần đầy đủ:Đầy đủ: các node lá luôn nằm ở mức cao nhất và các nút không là nút lá có đầy đủ 2 nhánh con.Gần đầy đủ: Giống như trên nhưng các node lá nằm ở mức cao nhất (hoặc trước đó một mức) và lấp đầy từ bên trái sang bên phải ở mức cao nhất.Chiều cao của cây có n node:Trung bình h = [lg n] + 1Đầy đủ h = lg (n + 1)Suy biến h = nSố phần tử tại mức i nhiều nhất là 2iPhép duyệt câyDuyệt qua từng node của cây (mỗi node 1 lần)Cách duyệt:Chính thức: NLR, LNR, LRN, NRL, RNL, RLNChuẩn: NLR (preorder), LNR (inorder), LRN (postorder)Ví dụ về phép duyệt cây NLRABDHINEJKOCFLPGMAKết quả:BDHINEJOKCFLPGMVí dụ về phép duyệt cây LNRABDHINEJKOCFLPGMHKết quả:DNIBJOEKAFPLCMGVí dụ về phép duyệt cây LRNABDHINEJKOCFLPGMHKết quả:NIDOJKEBPLFMGCACây liên kếtGiải thuật duyệt cây inorderAlgorithm recursive_inorder Input: subroot là con trỏ node gốc và hàm visit Output: kết quả phép duyệt1. if (cây con không rỗng) 1.1. Call recursive_inorder với nhánh trái của subroot 1.2. Duyệt node subroot bằng hàm visit 1.3. Call recursive_inorder với nhánh phải của subrootEnd recursive_inorderCây nhị phân tìm kiếm – Binary search tree (BST)Một cây nhị phân tìm kiếm (BST) là một cây nhị phân rỗng hoặc mỗi node của cây này có các đặc tính sau:1. Khóa của node gốc lớn (hay nhỏ) hơn khóa của tất cả các node của cây con bên trái (hay bên phải)2. Các cây con (bên trái, phải) là BSTTính chất:Chỉ cần đặc tính 1 là đủDuyệt inorder sẽ được danh sách có thứ tựVí dụ BST2510316518122013372935325041Duyệt inorder: 1 3 5 6 10 12 13 18 20 25 29 32 35 37 41 50Các tính chất khác của BSTNode cực trái (hay phải):Xuất phát từ node gốcĐi sang trái (hay phải) đến khi không đi được nữaKhóa của node cực trái (hay phải) là nhỏ nhất (hay lớn nhất) trong BSTBST là cây nhị phân có tính chất:Khóa của node gốc lớn (hay nhỏ) hơn khóa của node cực trái (hay cực phải)Tìm kiếm trên BSTChọn hướng tìm theo tính chất của BST:So sánh với node gốc, nếu đúng thì tìm thấyTìm bên nhánh trái (hay phải) nếu khóa cần tìm nhỏ hơn (hay lớn hơn) khóa của node gốcGiống phương pháp tìm kiếm nhị phânThời gian tìm kiếmTốt nhất và trung bình: O(lg n)Tệ nhất: O(n)Giải thuật tìm kiếm trên BSTAlgorithm BST_search Input: subroot là node gốc và target là khóa cần tìm Output: node tìm thấy1. if (cây rỗng) 1.1. return not_found2. if (target trùng khóa với subroot) 2.1. return subroot3. if (target có khóa nhỏ hơn khóa của subroot) 3.1. Tìm bên nhánh trái của subroot4. else 4.1. Tìm bên nhánh phải của subrootEnd BST_searchVí dụ tìm kiếm trên BST2510316518122013372935325041Tìm kiếm 13Khác nhauGiống nhauNode gốc nhỏ hơnNode gốc lớn hơnTìm thấySố node duyệt: 5Số lần so sánh: 9Ví dụ tìm kiếm trên BST2510316518122013372935325041Tìm kiếm 14Khác nhauNode gốc nhỏ hơnNode gốc lớn hơnKhông tìm thấySố node duyệt: 5Số lần so sánh: 10