Was ist die verknüpfte Speicherstruktur eines Binärbaums?

Die verknüpfte Speicherstruktur eines Binärbaums bezieht sich auf die Verwendung einer verknüpften Liste zur Darstellung eines Binärbaums, dh die Verwendung einer verknüpften Liste zur Angabe der logischen Beziehung zwischen Elementen. Die verknüpfte Speicherstruktur eines Binärbaums weist normalerweise zwei Speicherformen auf: eine binär verknüpfte Liste und eine dreifach verknüpfte Liste.

Die Betriebsumgebung dieses Tutorials: Windows 7-System, c99-Version, Dell G3-Computer.

Die verknüpfte Speicherstruktur eines Binärbaums verwendet eine verknüpfte Liste zur Darstellung eines Binärbaums, dh eine verknüpfte Liste wird verwendet, um die logische Beziehung zwischen Elementen anzuzeigen. Normalerweise gibt es zwei Speicherformen:

• Jeder Knoten in der verknüpften Liste besteht aus drei Feldern. Zusätzlich zum Datenfeld gibt es auch zwei Zeigerfelder, die zur Angabe des linken und rechten untergeordneten Knotens verwendet werden bzw. die Speicheradresse, an der es sich befindet.

• Jeder Knoten in der verknüpften Liste besteht aus vier Feldern. Zusätzlich zum Datenfeld gibt es auch drei Zeigerfelder, die zur Angabe der Speicheradressen des linken untergeordneten, rechten untergeordneten und übergeordneten Knotens verwendet werden. Die verkettete Speicherstruktur eines Binärbaums (detaillierte Erklärung in C-Sprache) Wenn es verkettet ist, müssen Sie zum Speichern nur am Wurzelknoten des Baums beginnen und jeden Knoten sowie seine linken und rechten untergeordneten Knoten in einer verknüpften Liste speichern. Daher ist in Abbildung 2 die Kettenspeicherstruktur entsprechend Abbildung 1 dargestellt:

Abbildung 2 Schematische Darstellung der verketteten Speicherstruktur eines BinärbaumsWie aus Abbildung 2 ersichtlich ist, besteht die Knotenstruktur bei Verwendung der verketteten Speicherung von Binärbäumen aus drei Teilen (wie in Abbildung 3 dargestellt):

Zeiger zum linken untergeordneten Knoten (Lchild);

Im Knoten gespeicherte Daten (Daten);

Zeiger auf den rechten untergeordneten Knoten (Rchild);

• Abbildung 3 Binärbaumknotenstruktur

Der C-Sprachcode, der die Knotenstruktur darstellt, ist:

• typedef struct BiTNode{
      TElemType data;//数据域
      struct BiTNode *lchild,*rchild;//左右孩子指针
      struct BiTNode *parent;
  }BiTNode,*BiTree;

  Der C-Sprachcode, der der Kettenspeicherstruktur in Abbildung 2 entspricht, ist:

  #include <stdio.h>
  #include <stdlib.h>
  #define TElemType int
  typedef struct BiTNode{
      TElemType data;//数据域
      struct BiTNode *lchild,*rchild;//左右孩子指针
  }BiTNode,*BiTree;
  void CreateBiTree(BiTree *T){
      *T=(BiTNode*)malloc(sizeof(BiTNode));
      (*T)->data=1;
      (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
      (*T)->lchild->data=2;
      (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
      (*T)->rchild->data=3;
      (*T)->rchild->lchild=NULL;
      (*T)->rchild->rchild=NULL;
      (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
      (*T)->lchild->lchild->data=4;
      (*T)->lchild->rchild=NULL;
      (*T)->lchild->lchild->lchild=NULL;
      (*T)->lchild->lchild->rchild=NULL;
  }
  int main() {
      BiTree Tree;
      CreateBiTree(&Tree);
      printf("%d",Tree->lchild->lchild->data);
      return 0;
  }

Programmausgabeergebnis:

• 4

  Tatsächlich ist das Kette des Binärbaums Es gibt viel mehr Speicherstrukturen als die in Abbildung 2 gezeigte. In einigen tatsächlichen Szenarien kann beispielsweise die Operation „Finden des übergeordneten Knotens eines Knotens“ ausgeführt werden. In diesem Fall kann der Knotenstruktur ein Zeigerfeld hinzugefügt werden, das auf seinen übergeordneten Knoten zeigt, wie gezeigt in Abbildung 4. :

Abbildung 4 Die verknüpfte Speicherstruktur eines benutzerdefinierten Binärbaums
Eine solche verknüpfte Listenstruktur wird normalerweise als ternäre verknüpfte Liste bezeichnet.

Mithilfe der in Abbildung 4 gezeigten dreigliedrigen verknüpften Liste können wir den übergeordneten Knoten jedes Knotens leicht finden. Daher kann bei der Lösung praktischer Probleme durch die Verwendung einer geeigneten verknüpften Listenstruktur zum Speichern von Binärbäumen mit halbem Aufwand das Doppelte des Ergebnisses erzielt werden.

Verwandte Empfehlungen: „

C-Sprachvideo-Tutorial

“

Das obige ist der detaillierte Inhalt vonWas ist die verknüpfte Speicherstruktur eines Binärbaums?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!