bst.cpp

Bài viết đang được chỉnh sửa

Binary Searched Tree

Bài toán

Lưu trữ dữ liệu theo tổ chức cây tìm kiếm, in ra cây theo các thứ tự preorder, inorder hoặc postorder.

Độ phức tạp

chèn : O(h) (với h là độ cao cây)

#include <stdio.h>

#include <vector>

using namespace std;

const int oo = 1000111000;

class bst {

public:

    struct node {

        int left, right, value;

        node(int p) { left=right=0; value=p; }

    };

    vector <node*> a;

    int makenew(int p){

        a.push_back(new node(p));

        return a.size()-1;

    }

    void push(int p, int u){

        if (p>a[u]->value){

            if (a[u]->right==0) a[u]->right = makenew(p);

            else push(p, a[u]->right);

        }

        else {

            if (a[u]->left==0) a[u]->left = makenew(p);

            else push(p, a[u]->left);

        }

    }

    void clear(){

        for (int i=0; i<a.size(); i++) delete a[i];

        a.clear();

    }

    void show(int u){

        if (u==0) return ;

        show(a[u]->left);

        printf("%d,", a[u]->value);

        show(a[u]->right);       

    }

    void show(){

        show(a[0]->left);

        show(a[0]->right);

    }

    bst() { a.push_back(new node(-oo)); }     

};

bst a;

main(){

    a.push(9, 0);

    a.push(4, 0);

    a.push(3, 0);

    a.push(5, 0);

    a.show();

    return 0;

}

Sample Output

3,4,5,9,

Các đặc tính khác

Kiểu vector trong C++ không thể quản lý được kiểu struct node, vì vậy, mình sử dụng vector<node*>.

BST này luôn có một nút gốc là -oo, tức là mọi nút về sau đều được đặt bên phải nút gốc này.