Eine Verknüpfte Liste ist eine Kette von Knoten, die über "Nächste" -Zeiger verbunden sind. Ein Baum ähnelt einer verknüpften Liste, aber jeder Knoten kann mit mehreren Knoten verknüpft werden.
Wenn wir von einem Baum sprechen, meinen wir grundsätzlich einen binären Baum, also eine Struktur, die zwei Kinder hat, links und rechts.
Binäre Baumdarstellung
Ein binärer Baumknoten wird durch eine Struktur dargestellt, die ein Datenelement und zwei Zeiger auf andere Strukturen des gleichen Typs enthält.
struct node
{
int data;
struct node *left;
struct node *right;
};
Ein spezieller Zeiger namens ROOT zeigt auf den Knoten, der der Elternknoten aller anderen Knoten ist.
Außerdem zeigen Knoten, die keine Kinder haben, mit ihrem linken und rechten Zeiger auf NULL .
Ein einfacher Binärbaum mit drei Knoten kann wie folgt erstellt werden:
/* Initialize nodes */ struct node *root; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->left = two; one->right = three; two->left = NULL; two->right = NULL; three->left = NULL; three->right = NULL; /* Save address of first node in root */ root = one;
In wenigen Schritten haben wir einen Binärbaum mit drei Knoten erstellt.
Bäume können viel tiefer und komplexer sein. Die in jedem Knoten gespeicherten Daten können komplexer sein und viel mehr Kinder als nur zwei haben.
Bäume auftragen
Bäume und ihre Varianten sind eine äußerst nützliche Datenstruktur mit vielen praktischen Anwendungen.
- Binäre Suchbäume (BST) werden verwendet, um schnell zu überprüfen, ob sich ein Element in einer Menge befindet.
- Heap (Set) ist eine Art Baum, der verwendet wird, um mehrere Elemente zu sortieren.
- Eine modifizierte Version des Baums namens Tries wird in modernen Routern verwendet, um Routing-Informationen zu speichern.
- Die beliebtesten Datenbanken verwenden B-Bäume (B-Bäume) und T-Bäume (T-Bäume), die Varianten der Baumstruktur sind, die wir oben gelernt haben, um ihre Daten zu speichern.
- Compiler verwenden einen Syntaxbaum, um die Syntax jedes von Ihnen geschriebenen Programms zu überprüfen (validieren).
Vollständiges C-Programm zur Implementierung von Tree
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* left;
struct node* right;
};
struct node* createNode(value){
struct node* newNode = malloc(sizeof(struct node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
struct node* insertLeft(struct node *root, int value) {
root->left = createNode(value);
return root->left;
}
struct node* insertRight(struct node *root, int value){
root->right = createNode(value);
return root->right;
}
int main(){
struct node *root = createNode(1);
insertLeft(root, 2);
insertRight(root, 3);
printf("The elements of tree are %d %d %d", root->data, root->left->data, root->right->data);
}
Programmausgabe
1 2 3
