Technologieaustausch

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. Konzept und Struktur des Baumes

1.1 Das Konzept des Baumes

Baum ist einnichtlinear Eine Datenstruktur, bei der es sich um eine Reihe hierarchischer Beziehungen handelt, die aus n (n>=0) begrenzten Knoten bestehen.BündelnEr wird Baum genannt, weil er wie ein umgedrehter Baum aussieht, was bedeutet, dass die Wurzeln nach oben und die Blätter nach unten zeigen.

• Wurzelknoten: Der Wurzelknoten hat keinen Vorgängerknoten.
• Bis auf den Wurzelknoten sind die übrigen Knoten in Teilbäume unterteilt, deren Struktur der eines Baums ähnelt. Der Wurzelknoten jedes Teilbaums hat genau einen Vorgänger und kann 0 oder mehr Nachfolger haben.
• Daher ist der Baumrekursive Definitionvon.

1.2 Verwandte Konzepte von Bäumen

• Grad des Knotens: Die Anzahl der in einem Knoten enthaltenen Teilbäume wird als Grad des Knotens bezeichnet, wie in der Abbildung oben gezeigt: A ist 4
• Blattknoten oder Endknoten: Knoten mit Grad 0 werden Blattknoten genannt; wie in der Abbildung oben gezeigt: Knoten B, F, G, D und H sind Blattknoten.
• Nichtterminaler Knoten oder Verzweigungsknoten: Ein Knoten, dessen Grad nicht 0 ist. Wie in der Abbildung oben gezeigt: Die Knoten A, C und E sind Verzweigungsknoten.
• Übergeordneter Knoten oder übergeordneter Knoten: Wenn ein Knoten untergeordnete Knoten enthält, wird dieser Knoten als übergeordneter Knoten seines untergeordneten Knotens bezeichnet. Wie in der Abbildung oben gezeigt: A ist der übergeordnete Knoten von B
• untergeordneter Knoten oder untergeordneter Knoten: Der Wurzelknoten des in einem Knoten enthaltenen Teilbaums wird als untergeordneter Knoten des Knotens bezeichnet. Wie in der Abbildung oben gezeigt: B ist der untergeordnete Knoten von A
• Geschwisterknoten: Knoten mit demselben übergeordneten Knoten werden wie oben gezeigt als Geschwisterknoten bezeichnet: B und C sind Geschwisterknoten.
• Grad des Baumes: In einem Baum wird der Grad des größten Knotens als Grad des Baums bezeichnet, wie oben gezeigt: Der Grad des Baums beträgt 4
• Knotenebene: Ausgehend von der Definition der Wurzel ist die Wurzel die 1. Ebene, die untergeordneten Knoten der Wurzel sind die 2. Ebene und so weiter;
• Höhe oder Tiefe des Baumes: Die maximale Knotenebene im Baum, wie oben gezeigt: Die Höhe des Baums beträgt 3
• Cousin-Knoten: Knoten, deren Eltern auf derselben Ebene liegen, sind Cousins ​​voneinander, wie in der Abbildung oben gezeigt: F und G sind Bruderknoten voneinander.
• Vorfahr des Knotens: Alle Knoten auf den Zweigen von der Wurzel bis zum Knoten, wie in der Abbildung oben gezeigt: A ist der Vorfahre aller Knoten
• Nachkommenschaft : Jeder Knoten im Unterbaum, der an einem bestimmten Knoten wurzelt, wird als Nachkomme dieses Knotens bezeichnet.Wie oben gezeigt: Alle Knoten sind Nachkommen von A
• Wald: Eine Ansammlung von m disjunkten Bäumen wird Wald genannt;

1.3 Baumdarstellung

Die Baumstruktur ist komplizierter als die lineare Tabelle und es ist schwieriger, sie zu speichern und darzustellen.Es ist notwendig, sowohl den Wertebereich als auch die Beziehung zwischen Knoten und Knoten zu speichern.Tatsächlich gibt es viele Möglichkeiten, Bäume darzustellen, wie zum Beispiel:Parent-Notation, Child-Notation, Child-Eltern-Notation und Child-Bruder-NotationWarten.

Bei der Einführung der folgenden Speicherstruktur nehmen wir den folgenden Baum als Beispiel.

1.3.1 Elternvertretung

Wir gehen davon aus, dass die Knoten des Baums gleichzeitig in einer Reihe kontinuierlicher Räume gespeichert sindAn jeden Knoten ist ein Indikator angehängt, der die Position seines übergeordneten Knotens in der verknüpften Liste anzeigt. . Mit anderen Worten: Jeder Knoten weiß nicht nur, wer er ist, sondern auch, wo sich seine übergeordneten Knoten befinden.

Unter diesen sind Daten das Datenfeld, in dem die Dateninformationen des Knotens gespeichert werden. Und parent ist ein Zeigerfeld, das die Indizes der Eltern des Knotens im Array speichert.
Das Folgende ist der Knotenstruktur-Definitionscode für unsere übergeordnete Darstellung.

/*树的双亲表示法结点结构定义*/
#define MAX_TREE_SIZE 100
typedef int TElemType;	//树结点的数据类型，目前暂定为整型
/*结点结构*/
typedef struct TreeNode
{
	TElemType data;	//结点数据
	int parent;	//双亲位置
}TreeNode;
/*树结构*/
typedef struct
{
	TreeNode nodes[MAX_TREE_SIZE];	//结点数组
	int r, n;	//根的位置和结点数
}PTree;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Mit einer solchen Speicherstruktur können wir die übergeordneten Knoten anhand des verwendeten übergeordneten Knotens leicht findenDie Zeitkomplexität beträgt 0(1) , bis der übergeordnete Wert -1 ist, was anzeigt, dass die Wurzel des Baumknotens gefunden wurde. Wenn wir jedoch wissen möchten, was die untergeordneten Knoten des Knotens sind, durchlaufen Sie bitte die gesamte Struktur.

1.3.2 Vertretung des Kindesbruders

Gerade haben wir die Speicherstruktur des Baums aus der Perspektive der Eltern und aus der Perspektive des Kindes untersucht. Was wäre, wenn wir uns für eine hierarchische Struktur wie einen Baum nur das ansehen würden? Brüder der Knoten. Nach der Beobachtung haben wir herausgefunden, dass für jeden Baum das erste Kind seines Knotens eindeutig ist, wenn er existiert, und sein rechter Bruder ebenfalls eindeutig ist, wenn er existiert. Daher setzen wir zwei Zeiger, die auf das erste Kind des Knotens und das rechte Geschwister des Knotens zeigen.

/*树的孩子兄弟表示法结构定义*/
typedef struct TreeNode
{
	TElemtype data;
	struct TreeNode *firstchild, *rightsib;
} TreeNode,* pTreeNode;
1
2
3
4
5
6

1.4 Praktische Anwendungen von Bäumen

2. Konzept und Struktur des Binärbaums

2.1 Konzept

Ein Binärbaum ist eine endliche Menge von Knoten, nämlich:

• oder leer
• Es besteht aus einem Wurzelknoten und zwei Binärbäumen, auch bekannt als linker Teilbaum und rechter Teilbaum.

Wie auf dem Bild oben zu sehen ist:

1. In einem Binärbaum gibt es keinen Knoten mit einem Grad größer als 2
2. Die Teilbäume eines Binärbaums können in linke und rechte Teilbäume unterteilt werden, und die Reihenfolge kann nicht umgekehrt werden, so wie es beim Binärbaum der Fall istgeordneter Baum

Hinweis: Jeder Binärbaum besteht aus den folgenden Situationen:

2.2 Spezielle Binärbäume

1. vollständiger Binärbaum: ein Binärbaum,Wenn die Anzahl der Knoten in jeder Schicht das Maximum erreicht, ist der Binärbaum ein vollständiger Binärbaum. . Das heißt, wenn die Anzahl der Ebenen eines Binärbaums K und die Gesamtzahl der Knoten 2^k-1 beträgt, handelt es sich um einen vollständigen Binärbaum.
2. vollständiger Binärbaum: Ein vollständiger Binärbaum ist eine sehr effiziente Datenstruktur.Vollständige Binärbäume werden aus vollständigen Binärbäumen abgeleitet . Ein Binärbaum mit n Knoten der Tiefe K wird genau dann als vollständiger Binärbaum bezeichnet, wenn jeder Knoten eins zu eins den von 1 bis n nummerierten Knoten im vollständigen Binärbaum der Tiefe K entspricht. Vorsicht ist gebotenEin vollständiger Binärbaum ist eine besondere Art eines vollständigen Binärbaums.
   

2.3 Eigenschaften von Binärbäumen

1. Wenn die Anzahl der Ebenen des Wurzelknotens mit 1 angegeben ist, dann wird dieEs gibt höchstens 2^(i-1) auf der i-ten Ebene Knoten
2. Wenn die Anzahl der Ebenen des Wurzelknotens mit 1 angegeben ist, dannDie maximale Anzahl von Knoten eines Binärbaums mit der Tiefe h beträgt 2^h-1
3. Für jeden Binärbaum, wennDie Anzahl der Blattknoten mit Grad 0 beträgt n0 und die Anzahl der Verzweigungsknoten mit Grad 2 beträgt n2, dann ist n0 = n2 +1
4. Wenn die Anzahl der Ebenen des Wurzelknotens mit 1 angegeben ist,Die Tiefe eines vollständigen Binärbaums mit n Knoten, h=log (n+1) (ps: log ist Basis 2, n+1 ist Logarithmus)
5. Wenn für einen vollständigen Binärbaum mit n Knoten alle Knoten beginnend bei 0 in der Array-Reihenfolge von oben nach unten und von links nach rechts nummeriert sind, dann gilt für den Knoten mit der Seriennummer i:
   • Wenn i>0, die übergeordnete Nummer des Knotens an Position i: (i-1)/2;, i ist die Wurzelknotennummer, es gibt keinen übergeordneten Knoten
   • Wenn 2i+1, 2i+1>=n sonst gibt es kein linkes Kind
   • Wenn 2i+2, 2i+2>=n sonst gibt es kein richtiges Kind

2.4 Speicherstruktur des Binärbaums

Binärbäume können im Allgemeinen mit zwei Strukturen gespeichert werden:Eine sequentielle Struktur, eine Kettenstruktur.

1. sequentielle Speicherung
   Es ist eine sequentielle Strukturspeicherung zu verwendenArrayZum Speichern wird im Allgemeinen ein Array verwendetNur zur Darstellung vollständiger Binärbäume geeignet , da es sich nicht um einen vollständigen Binärbaum handelt und Platzverschwendung entsteht. In Wirklichkeit verwendet nur der Heap Arrays zur Speicherung.Die sequentielle Speicherung von Binärbäumen ist physikalisch ein Array und logisch ein Binärbaum.
   2. Kettenlagerung
   Die verknüpfte Speicherstruktur eines Binärbaums bezieht sich auf:Verwenden Sie eine verknüpfte Liste, um einen Binärbaum darzustellen , das heißt, es werden Ketten verwendet, um die logische Beziehung von Elementen anzuzeigen. **Die übliche Methode besteht darin, dass jeder Knoten in der verknüpften Liste aus drei Feldern besteht, dem Datenfeld und den linken und rechten Zeigerfeldern. Die linken und rechten Zeiger werden verwendet, um die Speicheradressen der Verknüpfungspunkte anzugeben, an denen sich das linke Kind befindet Das rechte Kind des Knotens befindet sich jeweils. **Kettenstrukturen werden in binäre Ketten und dreigeteilte Ketten unterteilt. Derzeit untersuchen wir binäre Ketten.
   

3. Sequentielle Struktur und Implementierung des Binärbaums

Gewöhnliche Binärbäume eignen sich nicht für die Speicherung in Arrays, da möglicherweise viel Speicherplatz verschwendet wird.UndVollständige Binärbäume eignen sich besser für die sequentielle Strukturspeicherung .In Wirklichkeit tun wir das normalerweiseEin Heap (ein Binärbaum) verwendet zum Speichern ein Array sequenzieller StrukturenEs ist zu beachten, dass der Heap hier und der Heap im virtuellen Prozessadressraum des Betriebssystems zwei verschiedene Dinge sind. Das eine ist eine Datenstruktur und das andere ist eine Bereichssegmentierung, die den Speicher im Betriebssystem verwaltet.
Informationen zur spezifischen Implementierung und Anwendung finden Sie unter:[Datenstruktur] 08. Heap und Heap-Anwendungen

4. Kettenstruktur des Binärbaums und seine Implementierung

4.1 Binärbaumdurchquerung

Der einfachste Weg, eine binäre Baumstruktur zu erlernen, besteht darin, sie zu durchlaufen.sogenanntBei der Durchquerung des Binärbaums (Traversal) werden entsprechende Operationen an den Knoten im Binärbaum nacheinander gemäß bestimmten Regeln ausgeführt, und jeder Knoten wird nur einmal bedient . Die von den zugreifenden Knoten ausgeführten Operationen hängen vom jeweiligen Anwendungsproblem ab. Das Durchlaufen ist eine der wichtigsten Operationen an einem Binärbaum und bildet auch die Grundlage für andere Operationen an einem Binärbaum.

4.1.1 Vorbestellungsdurchquerung

//根 左子树 右子树
void PrevOrder(pTreeNode root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%d ", root->val);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

Die folgende Abbildung zeigt den rekursiven Prozess:

4.1.2 Durchquerung in der richtigen Reihenfolge

//左子树 根 右子树
void InOrder(pTreeNode root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

Das Folgende ist der rekursive Prozess:

4.1.3 Postorder-Traversal

//左子树 右子树 根
void PostOrder(pTreeNode root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

Das Folgende ist der rekursive Prozess:

4.2.4 Level-Order-Durchquerung

Level-Order-Traversal: Zusätzlich zum Pre-Order-Traversal, In-Order-Traversal und Post-Order-Traversal kann Level-Order-Traversal auch für Binärbäume durchgeführt werden. Gehen Sie davon aus, dass die Ebenennummer des Wurzelknotens des Binärbaums 1 ist. Die Durchquerung der Ebenenreihenfolge beginnt am Wurzelknoten des Binärbaums. Zuerst wird der Wurzelknoten der ersten Ebene besucht, dann werden die Knoten auf der zweiten Ebene besucht Ebene von links nach rechts und dann die dritte Ebene Die Knoten der Ebene und so weiter.Der Prozess, die Knoten des Baums Schicht für Schicht von oben nach unten und von links nach rechts zu besuchen, ist eine Durchquerung der Schichtreihenfolge.。
Illustration:

Hier greifen wir in die Warteschlange ein, um eine Vorbestellungsdurchquerung des Binärbaums durchzuführen.

// 层序遍历
void LevelOrder(pTreeNode root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		pTreeNode front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			printf("NULL ");
		}
		else
		{
			printf("%d ", front->val);
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}
	QueueDestory(&q);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

4.1 Erstellung und Zerstörung von Binärbäumen

Um einen Binärbaum zu erstellen und zu zerstören, verwenden wirDurchquerung eines BinärbaumsZum Beispiel.

//二叉树的创建
struct TreeNode* Creat(char* arr,int n,int* i)
{ 
    if(*i<n&&arr[*i]=='#')
    {
        (*i)++;
        return NULL;
    }
    
    TreeNode* newnode=(TreeNode*)malloc(sizeof(TreeNode));
    newnode->left=NULL;
    newnode->right=NULL;

    newnode->val=arr[(*i)++];
    newnode->left=Creat(arr,n,i);
    newnode->right=Creat(arr,n,i);
    
    return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//二叉树的销毁
void TreeDestroy(struct TreeNode* root)
{
    if(root==NULL)
    {
        return;
    }
    TreeDestroy(root->left);
    TreeDestroy(root->right);
    free(root);
}
1
2
3
4
5
6
7
8
9
10
11

4.3 Andere Operationen an Binärbäumen

Die folgenden Operationen werden alle nach dem Prinzip der Durchquerung ausgeführt.

// 二叉树节点个数
int TreeSize(pTreeNode root)
{
	if (root == NULL)
	{
		return 0;
	}
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}
1
2
3
4
5
6
7
8
9

// 二叉树叶子节点个数
int TreeLeafSize(pTreeNode root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

// 二叉树第k层节点个数
int TreeLevelKSize(pTreeNode root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

// 二叉树查找值为x的节点
pTreeNode TreeFind(pTreeNode root, TreeDataType x)
{

	if (root == NULL)
	{
		return NULL;
	}
	//相等就返回
	if (root->val == x)
		return root;
	//找左子树
	pTreeNode left=TreeFind(root->left, x);
	if (left)
	{
		return left;
	}
	//找右子树
	pTreeNode right = TreeFind(root->right, x);
	if (right)
	{
		return right;
	}
	//都没找到
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

//二叉树的高度
int TreeHeight(pTreeNode root)
{
	if (root == NULL)
	{
		return 0;
	}
	int max_left = TreeHeight(root->left) ;
	int max_right = TreeHeight(root->right);
	return max_left > max_right ? max_left + 1 : max_right + 1;
}
1
2
3
4
5
6
7
8
9
10
11

//判断是否是完全二叉树
bool TreeComplete(pTreeNode root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q))
	{
		pTreeNode front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
		else
		{
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
	}
	while (!QueueEmpty(&q))
	{
		pTreeNode front = QueueFront(&q);
		QueuePop(&q);
		if (front)
		{
			QueueDestory(&q);
			return false;
		}
	}
	QueueDestory(&q);
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36