Datenstruktur und Algorithmen - Baum

Baum repräsentiert die Knoten, die durch Kanten verbunden sind. Wir werden speziell auf den binären Baum oder den binären Suchbaum eingehen.

Binary Tree ist eine spezielle Datenstruktur, die zur Datenspeicherung verwendet wird. Ein Binärbaum hat eine spezielle Bedingung, dass jeder Knoten maximal zwei untergeordnete Knoten haben kann. Ein Binärbaum bietet die Vorteile eines geordneten Arrays und einer verknüpften Liste, da die Suche so schnell ist wie in einem sortierten Array und der Einfüge- oder Löschvorgang so schnell ist wie in einer verknüpften Liste.

Wichtige Begriffe

Es folgen die wichtigen Begriffe in Bezug auf den Baum.

Path - Pfad bezieht sich auf die Folge von Knoten entlang der Kanten eines Baums.
Root- Der Knoten oben im Baum heißt root. Es gibt nur eine Wurzel pro Baum und einen Pfad vom Wurzelknoten zu einem Knoten.
Parent - Jeder Knoten außer dem Wurzelknoten hat eine Kante nach oben zu einem Knoten namens Parent.
Child - Der Knoten unter einem bestimmten Knoten, der durch seine Kante nach unten verbunden ist, wird als untergeordneter Knoten bezeichnet.
Leaf - Der Knoten, der keinen untergeordneten Knoten hat, wird als Blattknoten bezeichnet.
Subtree - Teilbaum repräsentiert die Nachkommen eines Knotens.
Visiting - Beim Besuch wird der Wert eines Knotens überprüft, wenn sich die Steuerung auf dem Knoten befindet.
Traversing - Durchqueren bedeutet, Knoten in einer bestimmten Reihenfolge zu durchlaufen.
Levels- Die Ebene eines Knotens repräsentiert die Erzeugung eines Knotens. Befindet sich der Wurzelknoten auf Ebene 0, befindet sich sein nächster untergeordneter Knoten auf Ebene 1, sein Enkel auf Ebene 2 usw.
keys - Schlüssel stellt einen Wert eines Knotens dar, auf dessen Grundlage eine Suchoperation für einen Knoten ausgeführt werden soll.

Darstellung des binären Suchbaums

Der binäre Suchbaum weist ein besonderes Verhalten auf. Das linke Kind eines Knotens muss einen Wert haben, der kleiner als der Wert seines Elternteils ist, und das rechte Kind des Knotens muss einen Wert haben, der größer als sein übergeordneter Wert ist.

Wir werden den Baum mithilfe eines Knotenobjekts implementieren und durch Referenzen verbinden.

Baumknoten

Der Code zum Schreiben eines Baumknotens ähnelt dem unten angegebenen. Es hat einen Datenteil und verweist auf seinen linken und rechten untergeordneten Knoten.

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

In einem Baum haben alle Knoten ein gemeinsames Konstrukt.

BST-Grundoperationen

Die grundlegenden Operationen, die an einer binären Suchbaumdatenstruktur ausgeführt werden können, sind die folgenden:

Insert - Fügt ein Element in einen Baum ein / erstellt einen Baum.
Search - Sucht ein Element in einem Baum.
Preorder Traversal - Durchquert einen Baum vorbestellt.
Inorder Traversal - Durchquert einen Baum in der richtigen Reihenfolge.
Postorder Traversal - Durchquert einen Baum nachträglich.

In diesem Kapitel lernen wir, eine Baumstruktur zu erstellen (einzufügen) und ein Datenelement in einem Baum zu suchen. Wir werden im kommenden Kapitel etwas über Baumüberquerungsmethoden lernen.

Operation einfügen

Beim allerersten Einfügen wird der Baum erstellt. Wenn danach ein Element eingefügt werden soll, suchen Sie zuerst die richtige Position. Starten Sie die Suche vom Stammknoten aus. Wenn die Daten kleiner als der Schlüsselwert sind, suchen Sie nach der leeren Position im linken Teilbaum und fügen Sie die Daten ein. Suchen Sie andernfalls nach der leeren Stelle im rechten Teilbaum und fügen Sie die Daten ein.

Algorithmus

If root is NULL 
   then create root node
return

If root exists then
   compare the data with node.data
   
   while until insertion position is located

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree

   endwhile 
   
   insert data
	
end If

Implementierung

Die Implementierung der Einfügefunktion sollte folgendermaßen aussehen:

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty, create root node
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent  = NULL;

      while(1) {                
         parent = current;

         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            
            //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }
			
         //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}

Suchvorgang

Wenn ein Element durchsucht werden soll, starten Sie die Suche vom Stammknoten aus. Wenn die Daten kleiner als der Schlüsselwert sind, suchen Sie im linken Teilbaum nach dem Element. Suchen Sie andernfalls nach dem Element im rechten Teilbaum. Befolgen Sie für jeden Knoten den gleichen Algorithmus.

Algorithmus

If root.data is equal to search.data
   return root
else
   while data not found

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree
         
      If data found
         return node
   endwhile 
   
   return data not found
   
end if

Die Implementierung dieses Algorithmus sollte so aussehen.

struct node* search(int data) {
   struct node *current = root;
   printf("Visiting elements: ");

   while(current->data != data) {
      if(current != NULL)
      printf("%d ",current->data); 
      
      //go to left tree

      if(current->data > data) {
         current = current->leftChild;
      }
      //else go to right tree
      else {                
         current = current->rightChild;
      }

      //not found
      if(current == NULL) {
         return NULL;
      }

      return current;
   }  
}

Um mehr über die Implementierung der binären Suchbaumdatenstruktur zu erfahren, klicken Sie bitte hier .