data-structures
Drzewo wyszukiwania binarnego

Tworzenie węzła w BST

Drzewo wyszukiwania binarnego (BST) to hierarchiczna struktura danych z pojedynczym wskaźnikiem do węzła głównego.

Węzeł w BST zazwyczaj zawiera „elementy” (takie jak liczby lub nazwiska) do szybkiego wyszukiwania. Każdy węzeł ma najwyżej dwoje dzieci (lewy i prawy). Każdy węzeł jest uporządkowany według niektórych kluczowych pól danych. Dla każdego węzła w BST jego klucz jest większy niż lewy klucz dziecka i mniej niż prawy klucz dziecka

Typowa struktura węzła (która przechowuje liczbę całkowitą) byłaby

struct bst_node {
    int item; 
    bst_node* left;
    bst_node* right;
}; 

Będzie tylko jeden węzeł główny BST. Węzeł główny można utworzyć za pomocą

bst_node* root = NULL;
root = (bst_node*) malloc(sizeof(bst_node));

Aby ustawić klucz pozycji root na 10.

root->item = 10;

wstawienie węzła do drzewa wyszukiwania binarnego

struct tree{
    int a;
    tree* right;
    tree* left;
};
tree* root=NULL;
void insert(tree*& in, int b){
        if(in){
            if(in->a<b)
                    insert(in->right,b);
            else if(in->a>b)
                    insert(in->left,b);
            else
                cout<<"the value is already in the tree."<<endl;
        }else{
            tree* temp = new tree;
            temp->a=b;
            temp->right=NULL;
            temp->left=NULL;
            in=temp;
        }
}