[JAVA] Memorandum über gegabelte Bäume für Anfänger (Teil 2 Suche nach gegabelten Bäumen)

Klicken Sie hier für Teil 1

Erforschung von gegabelten Bäumen

Wenn Sie eine Datenstruktur verwenden, müssen Sie in der Lage sein, nach Daten zu suchen. Es gibt zwei Hauptsuchrichtlinien für den gegabelten Baum. Breitensuche und Tiefensuche.

Suche nach Breitenpriorität

Die Suche mit Breitenpriorität bezieht sich auf eine Suche, die in der Reihenfolge von der Suche an der Wurzel aussieht.

Tiefenprioritätssuche

Die Suche mit Tiefenpriorität bezieht sich auf eine Suche, die einen Baum entlang einer Seite verfolgt. Es gibt drei Arten der Suche nach Tiefenprioritäten: die Reihenfolge des Gehens (Vorbestellung), die Reihenfolge des Bestehens (Inorder) und die Reihenfolge der Rückgabe (Nachbestellung). Schauen Sie sich in der Reihenfolge der Ankunft zuerst den Elternteil, dann das linke Kind und schließlich das rechte Kind an. Schauen Sie sich in der Pass-by-Reihenfolge zuerst das Kind links, dann das Elternteil und schließlich das Kind rechts an. Schauen Sie sich in der Rückgabereihenfolge zuerst das linke Kind, dann das rechte Kind und schließlich das Elternteil an. Die Suche wird realisiert, indem diese Algorithmen rekursiv von der Wurzel aus angewendet werden.

Erstellen wir nun ein Programm, das Knotendaten entsprechend ausgibt. Betrachten Sie der Einfachheit halber Dichotomien, die keine leeren Elemente enthalten, wenn Sie ein Array der Länge 7 verwenden.

Implementierungsbeispiel

C++

BinaryTree.cpp

#include <iostream>
using namespace std;

void breadthFirstSearch(string binaryTree[], int nodeNum);
void preorder(string binaryTree[], int nodeNum, int nodeIndex);
void inorder(string binaryTree[], int nodeNum, int nodeIndex);
void postorder(string binaryTree[], int nodeNum, int nodeIndex);

void breadthFirstSearch(string binaryTree[], int nodeNum)
{
  for (int i = 0; i < nodeNum; i++) {
    cout << binaryTree[i] + " ";
  }
  cout << endl;
}

void preorder(string binaryTree[], int nodeNum, int nodeIndex)
{
  if (nodeIndex >= nodeNum) {
    return;
  }

  cout << binaryTree[nodeIndex] + " ";
  preorder(binaryTree, nodeNum, 2 * nodeIndex + 1);
  preorder(binaryTree, nodeNum, 2 * nodeIndex + 2);
}

void inorder(string binaryTree[], int nodeNum, int nodeIndex)
{
  if (nodeIndex >= nodeNum) {
    return;
  }

  inorder(binaryTree, nodeNum, 2 * nodeIndex + 1);
  cout << binaryTree[nodeIndex] + " ";
  inorder(binaryTree, nodeNum, 2 * nodeIndex + 2);
}

void postorder(string binaryTree[], int nodeNum, int nodeIndex)
{
  if (nodeIndex >= nodeNum) {
    return;
  }

  postorder(binaryTree, nodeNum, 2 * nodeIndex + 1);
  postorder(binaryTree, nodeNum, 2 * nodeIndex + 2);
  cout << binaryTree[nodeIndex] + " ";
}


int main()
{
  string binaryTree[7] = {"Präsident", "Design Manager", "Ingenieur-Manager", "Charakter Designer",
                          "UI-Designer", "Serveringenieur", "Infrastrukturingenieur"};

  breadthFirstSearch(binaryTree, 7);

  preorder(binaryTree, 7, 0);
  cout << endl;
  inorder(binaryTree, 7, 0);
  cout << endl;
  postorder(binaryTree, 7, 0);
  cout << endl;
}

Java

BinaryTree.java

public class BinaryTree {
	public static void breadthFirstSearch(String[] binaryTree, int nodeNum) {
		for (int i = 0; i < nodeNum; i++) {
			System.out.print(binaryTree[i] + " ");
		}
		System.out.println("");
	}

	public static void preorder(String[] binaryTree, int nodeNum, int nodeIndex) {
		if (nodeIndex >= nodeNum) {
			return;
		}

		System.out.print(binaryTree[nodeIndex] + " ");
		preorder(binaryTree, nodeNum, 2 * nodeIndex + 1);
		preorder(binaryTree, nodeNum, 2 * nodeIndex + 2);
	}

	public static void inorder(String[] binaryTree, int nodeNum, int nodeIndex) {
		if (nodeIndex >= nodeNum) {
			return;
		}

		inorder(binaryTree, nodeNum, 2 * nodeIndex + 1);
		System.out.print(binaryTree[nodeIndex] + " ");
		inorder(binaryTree, nodeNum, 2 * nodeIndex + 2);
	}

	public static void postorder(String[] binaryTree, int nodeNum, int nodeIndex) {
		if (nodeIndex >= nodeNum) {
			return;
		}

		postorder(binaryTree, nodeNum, 2 * nodeIndex + 1);
		postorder(binaryTree, nodeNum, 2 * nodeIndex + 2);
		System.out.print(binaryTree[nodeIndex] + " ");
	}

	public static void main(String[] args) {
		String[] binaryTree = {"Präsident", "Design Manager", "Ingenieur-Manager", "Charakter Designer",
													 "UI-Designer", "Serveringenieur", "Infrastrukturingenieur"};

		breadthFirstSearch(binaryTree, 7);

		preorder(binaryTree, 7, 0);
		System.out.println();
		inorder(binaryTree, 7, 0);
		System.out.println();
		postorder(binaryTree, 7, 0);
		System.out.println();

	}
}

Erläuterung zur Implementierung

Die Suche nach Breitenprioritäten, wenn eine Dichotomie mithilfe eines Arrays realisiert wird, ist einfach, da das Array nur in der Reihenfolge von Anfang an gelesen wird. Im Fall der Zielreihenfolge wird dies realisiert, indem der Index des aktuell angezeigten Knotens dem Argument nodeIndex übergeben wird und wiederkehrend ist. Da die Reihenfolge des Passierens und Zurückgebens unterschiedlich ist, kann dies durch einfaches Ersetzen der Zeilen in der Reihenfolge des Passierens erreicht werden. Die Idee der Wiederholung ist schwierig, aber wenn Sie ein Anfänger sind, denken Sie langsam darüber nach, was dieses Programm bedeutet. Die Ausführungsergebnisse sind wie folgt.

Präsident Design Abteilungsleiter Ingenieur Abteilungsleiter Charakter Designer UI Designer Server Ingenieur Infrastrukturingenieur
Präsident Designabteilung Character Designer UI Designer Ingenieur Abteilung Server Ingenieur Infrastrukturingenieur
Character Designer Design Abteilungsleiter UI Designer Präsident Server Engineer Engineer Abteilungsleiter Infrastructure Engineer
Character Designer UI Designer General Manager der Konstruktionsabteilung Server Engineer Infrastructure Engineer General Manager der Engineer Department President

Haben Sie die Suche nach gegabelten Bäumen verstanden?

Teil 3 ist hier