C-Programmierung
Baumknoten Einfügen
← Aufwand der Baumtraversierung | ● | Baumknoten Löschen →
Um einen neuen Knoten x einzufügen, traversiert man den Baum bis zu einem Knoten y, der noch keinen entsprechenden Nachfolger besitzt.
- Ist x < y so wird x das linke Kind von y.
- Sonst wird x das rechte Kind von y.
Beispiel:
7 9
5 --> 5 --> 5
/ \ ins / \ ins / \
3 8 3 8 3 8
/ / \
7 7 9
Iteratives Einfügen:
node_ptr root=NULL; /* global root node */
void insert_element(const T &element, node_ptr *ptr = &root)
{
while (*ptr!=NULL)
if (element < (*ptr)->item)
ptr=&((*ptr)->left);
else
ptr=&((*ptr)->right);
*ptr = new node_type;
(*ptr)->item = element;
(*ptr)->left = (*ptr)->right = NULL;
}
void insert_element(const T &element, node_ptr *ptr = &root)
{
while (*ptr!=NULL)
if (element < (*ptr)->item)
ptr=&((*ptr)->left);
else
ptr=&((*ptr)->right);
*ptr = new node_type;
(*ptr)->item = element;
(*ptr)->left = (*ptr)->right = NULL;
}