Chương trình C++ thực hiện các thao tác trên cây BST

Cây tìm kiếm nhị phân (BST) là cây nhị phân có thứ tự: khóa con phải > khóa cha, khóa con trái < khóa cha, khóa phân biệt, mỗi nút tối đa 2 con.

Mô tả lớp

Bắt đầu
  lớp BST khai báo:
    search() = Tìm mục trong BST.
    insert() = Chèn mục: nếu rỗng làm gốc, nếu dữ liệu < gốc chèn trái, ngược lại chèn phải.
    del() = Xóa mục.
    casea(), caseb(), casec() = Xử lý xóa theo trường hợp con.
    inorder() = Duyệt inorder (trái - gốc - phải).
    preorder() = Duyệt preorder (gốc - trái - phải).
    postorder() = Duyệt postorder (trái - phải - gốc).
Kết thúc

Ví dụ

#include <iostream>
#include <cstdlib>
using namespace std;

struct nod {
    int info;
    struct nod *l;
    struct nod *r;
} *r;

class BST {
public:
    void search(nod *, int);
    void find(int, nod **, nod **);
    void insert(nod *, nod *);
    void del(int);
    void casea(nod *, nod *);
    void caseb(nod *, nod *);
    void casec(nod *, nod *);
    void preorder(nod *);
    void inorder(nod *);
    void postorder(nod *);
    void show(nod *, int);
    BST() { r = NULL; }
};
// ... (các định nghĩa hàm thành viên như trong nguồn)
int main() {
    int c, n, item;
    BST bst;
    nod *t;
    while (1) {
        cout << "1.Insert Element\n2.Delete Element\n3.Search Element\n4.Inorder Traversal\n5.Preorder Traversal\n6.Postorder Traversal\n7.Display the tree\n8.Quit\nEnter your choice: ";
        cin >> c;
        switch (c) {
            case 1: t = new nod; cout << "Enter number: "; cin >> t->info; bst.insert(r, t); break;
            case 2: if (r == NULL) { cout << "Tree empty\n"; continue; } cout << "Enter number to delete: "; cin >> n; bst.del(n); break;
            case 3: cout << "Search:" << endl; cin >> item; bst.search(r, item); break;
            case 4: cout << "Inorder Traversal:" << endl; bst.inorder(r); cout << endl; break;
            case 5: cout << "Preorder Traversal:" << endl; bst.preorder(r); cout << endl; break;
            case 6: cout << "Postorder Traversal:" << endl; bst.postorder(r); cout << endl; break;
            case 7: cout << "Display BST:" << endl; bst.show(r, 1); cout << endl; break;
            case 8: exit(1);
            default: cout << "Wrong choice" << endl;
        }
    }
    return 0;
}

Kết quả (mẫu)

1.Insert Element
...
Enter your choice : 1
Enter the number to be inserted : 6
Root Node is Added
...
Inorder Traversal of BST:
4 5 6 7
Preorder Traversal of BST:
6 5 4 7
Postorder Traversal of BST:
4 5 7 6
Display BST:
        7
Root->: 6
        5
        4