Chương trình C++ triển khai cây tìm kiếm nhị phân bằng danh sách liên kết

Dưới đây là chương trình C++ triển khai cây tìm kiếm nhị phân (Binary Search Tree) sử dụng danh sách liên kết (Linked Lists).

Hàm và mã giả

Thuật toán

Bắt đầu
  Nhập các nút của cây.
  Tạo cấu trúc nod nhận dữ liệu d, con trỏ trái l và phải r.
  Tạo hàm create() chèn nút vào cây:
    Khởi tạo c = 0 là số nút.
    Thực hiện vòng lặp while cho đến c < 6:
      Nhập gốc.
      Nhập giá trị nút, nếu lớn hơn gốc thì chèn phải ngược lại chèn trái.
  Tạo hàm inorder() duyệt nút theo inorder: Trái – Gốc – Phải.
  Tạo hàm preorder() duyệt nút theo preorder: Gốc – Trái – Phải.
  Tạo hàm postorder() duyệt nút theo postorder: Trái – Phải – Gốc.
  Từ main(), gọi các hàm và in kết quả.
Kết thúc

Mã ví dụ

#include <iostream>
using namespace std;

struct nod {
    nod *l, *r;
    int d;
}*r = NULL, *p = NULL, *np = NULL, *q;

void create() {
    int v, c = 0;
    while (c < 6) {
        if (r == NULL) {
            r = new nod;
            cout << "Nhập giá trị nút gốc:\n";
            cin >> r->d;
            r->r = NULL;
            r->l = NULL;
        } else {
            p = r;
            cout << "Nhập giá trị nút:\n";
            cin >> v;
            while(true) {
                if (v < p->d) {
                    if (p->l == NULL) {
                        p->l = new nod;
                        p = p->l;
                        p->d = v;
                        p->l = NULL;
                        p->r = NULL;
                        cout << "Giá trị nhập vào bên trái\n";
                        break;
                    } else if (p->l != NULL) {
                        p = p->l;
                    }
                } else if (v > p->d) {
                    if (p->r == NULL) {
                        p->r = new nod;
                        p = p->r;
                        p->d = v;
                        p->l = NULL;
                        p->r = NULL;
                        cout << "Giá trị nhập vào bên phải\n";
                        break;
                    } else if (p->r != NULL) {
                        p = p->r;
                    }
                }
            }
        }
        c++;
    }
}

void inorder(nod *p) {
    if (p != NULL) {
        inorder(p->l);
        cout << p->d << endl;
        inorder(p->r);
    }
}

void preorder(nod *p) {
    if (p != NULL) {
        cout << p->d << endl;
        preorder(p->l);
        preorder(p->r);
    }
}

void postorder(nod *p) {
    if (p != NULL) {
        postorder(p->l);
        postorder(p->r);
        cout << p->d << endl;
    }
}

int main() {
    create();
    cout << " Duyệt inorder:\n";
    inorder(r);
    cout << " Duyệt preorder:\n";
    preorder(r);
    cout << " Duyệt postorder:\n";
    postorder(r);
    return 0;
}

Kết quả đầu ra

Nhập giá trị nút gốc: 7
Nhập giá trị nút: 6
Giá trị nhập vào bên trái
Nhập giá trị nút: 4
Giá trị nhập vào bên trái
Nhập giá trị nút: 3
Giá trị nhập vào bên trái
Nhập giá trị nút: 2
Giá trị nhập vào bên trái
Nhập giá trị nút: 1
Giá trị nhập vào bên trái
Duyệt inorder:
1
2
3
4
6
7
Duyệt preorder:
7
6
4
3
2
1
Duyệt postorder:
1
2
3
4
6
7