Teil 4 ist hier
Dieses Mal werde ich den Dichotomiebaum erklären. Auch hier ist die Struktur einfach: Die übergeordneten Daten sind immer größer als die linken untergeordneten Daten, und die rechten untergeordneten Daten sind immer größer als die übergeordneten Daten. Dies ist nicht immer eine vollständige Zweiteilung, daher wird sie mithilfe von Klassen erreicht.
C++
BST.cpp
#include <iostream>
using namespace std;
class BST
{
public:
friend class Main;
int value;
BST *left;
BST *right;
BST(int);
~BST();
};
void inorder(BST *);
BST *insertNode(BST *, int);
BST *deleteNode(BST *, int);
BST *deleteNodeEl(BST *, BST *, BST *, bool);
BST::BST(int value):value(value), left(0), right(0){}
BST::~BST()
{
delete left;
delete right;
}
void inorder(BST *root)
{
if (root->left != 0) {
inorder(root->left);
}
cout << root->value << " ";
if (root->right != 0) {
inorder(root->right);
}
return;
}
//Eine Funktion, die einen neuen Knoten in den Dichotomiebaum einfügt
//Gibt BST nach dem Einfügen zurück
BST *insertNode(BST *root, int value)
{
//Tun Sie nichts, wenn es bereits Wert gibt
if (root->value == value) {
return root;
}
//Wenn die aktuelle Position größer als der Wert ist
else if (root->value > value) {
//Wenn links kein Kind ist
if (root->left == 0) {
root->left = new BST(value);
}
//Wenn Sie links ein Kind haben
else {
root->left = insertNode(root->left, value);
}
}
//Wenn die aktuelle Position größer als der Wert ist
else {
//Wenn es kein richtiges Kind gibt
if (root->right == 0) {
root->right = new BST(value);
}
//Wenn Sie das richtige Kind haben
else {
root->right = insertNode(root->right, value);
}
}
return root;
}
//Eine Funktion, die Knoten löscht, die Wert in den Daten haben
//Gibt die gelöschte BST zurück
BST *deleteNode(BST *root, int value)
{
BST *parent = 0;
BST *present = root;
bool directionIsLeft = false;
while (present != 0) {
//Wenn die Daten an der aktuellen Position größer als der Wert sind
if (present->value > value) {
parent = present;
directionIsLeft = true;
present = present->left;
}
//Wenn der Wert größer als die Daten an der aktuellen Position ist
else if (present->value < value) {
parent = present;
directionIsLeft = false;
present = present->right;
}
//Wenn Wert und aktuelle Positionsdaten übereinstimmen
else {
//Mindestens einer hat keine Kinder
if (present->left == 0 || present->right == 0) {
return deleteNodeEl(root, present, parent, directionIsLeft);
}
//Wenn Sie beide Kinder haben
else {
BST *right = present->right;
parent = present;
directionIsLeft = false;
//Finden Sie den Mindestwert unter dem richtigen Kind
while (right->left != 0) {
parent = right;
right = right->left;
directionIsLeft = true;
}
//Zum Zeitpunkt des Beendens der vorherigen Zeit gibt rechts den Knoten mit dem Mindestwert unter dem rechten untergeordneten Element an.
//Aktuelle und richtige Daten austauschen
present->value = right->value;
right->value = value;
return deleteNodeEl(root, right, parent, directionIsLeft);
}
}
}
return root;
}
//Eine Funktion, die einen Dichotomiebaum nach dem Löschen eines Geschenks rekonstruiert, wenn ein oder weniger Kinder vorhanden sind
//Gibt die rekonstruierte BST zurück
BST *deleteNodeEl(BST *root, BST *present, BST *parent, bool directionIsLeft)
{
//Wenn Sie keine Kinder haben
if (present->left == 0 && present->right == 0) {
//Wenn die aktuelle Position root ist
if (parent == 0) {
delete present;
return NULL;
}
//Wenn die aktuelle Position nicht die Wurzel ist
else {
if (directionIsLeft) {
parent->left = 0;
}
else {
parent->right = 0;
}
delete present;
return root;
}
}
//Wenn Sie nur ein Kind haben
else if (present->left == 0 || present->right == 0) {
//Wenn Sie das richtige Kind haben
if (present->right != 0) {
//Wenn die aktuelle Position root ist
if (parent == 0) {
BST *right = present->right;
delete present;
return right;
}
//Wenn die aktuelle Position nicht die Wurzel ist
else {
if (directionIsLeft) {
parent->left = present->right;
}
else {
parent->right = present->right;
}
delete present;
return root;
}
}
//Wenn Sie links ein Kind haben
else {
//Wenn die aktuelle Position root ist
if (parent == 0) {
BST *left = present->left;
delete present;
return left;
}
//Wenn die aktuelle Position nicht die Wurzel ist
else {
if (directionIsLeft) {
parent->left = present->left;
}
else {
parent->right = present->left;
}
delete present;
return root;
}
}
}
delete present;
return root;
}
int main()
{
BST *root = new BST(20);
root = insertNode(root, 10);
root = insertNode(root, 26);
root = insertNode(root, 5);
root = insertNode(root, 14);
root = insertNode(root, 23);
root = insertNode(root, 25);
//Das doppelte Einfügen ist nicht zulässig
root = insertNode(root, 25);
inorder(root);
cout << endl;
cout << "10: " << boolalpha << searchNode(root, 10) << endl;
cout << "23: " << boolalpha << searchNode(root, 23) << endl;
//Sie können nicht nach dem suchen, was Sie nicht haben
cout << "15: " << boolalpha << searchNode(root, 15) << endl;
root = deleteNode(root, 25);
root = deleteNode(root, 14);
//Sie können nicht löschen, was Sie nicht haben
root = deleteNode(root, 14);
inorder(root);
cout << endl;
}
Java
BST.java
public class BST {
int value;
BST left;
BST right;
BST(int value) {
this.value = value;
this.left = null;
this.right = null;
}
public static void inorder(BST root) {
if (root.left != null) {
inorder(root.left);
}
System.out.print(root.value + " ");
if (root.right != null) {
inorder(root.right);
}
return;
}
//Eine Funktion, die einen neuen Knoten in den Dichotomiebaum einfügt
//Gibt BST nach dem Einfügen zurück
public static BST insertNode(BST root, int value) {
//Tun Sie nichts, wenn es bereits Wert gibt
if (root.value == value) {
return root;
}
//Wenn die aktuelle Position größer als der Wert ist
else if (root.value > value) {
//Wenn links kein Kind ist
if (root.left == null) {
root.left = new BST(value);
}
//Wenn Sie links ein Kind haben
else {
root.left = insertNode(root.left, value);
}
}
//Wenn die aktuelle Position größer als der Wert ist
else {
//Wenn es kein richtiges Kind gibt
if (root.right == null) {
root.right = new BST(value);
}
//Wenn Sie das richtige Kind haben
else {
root.right = insertNode(root.right, value);
}
}
return root;
}
//Eine Funktion, die Knoten löscht, die Wert in den Daten haben
//Gibt die gelöschte BST zurück
public static BST deleteNode(BST root, int value) {
BST parent = null;
BST present = root;
boolean directionIsLeft = false;
while (present != null) {
//Wenn die Daten an der aktuellen Position größer als der Wert sind
if (present.value > value) {
parent = present;
directionIsLeft = true;
present = present.left;
}
//Wenn der Wert größer als die Daten an der aktuellen Position ist
else if (present.value < value) {
parent = present;
directionIsLeft = false;
present = present.right;
}
//Wenn Wert und aktuelle Positionsdaten übereinstimmen
else {
//Mindestens einer hat keine Kinder
if (present.left == null || present.right == null) {
return deleteNodeEl(root, present, parent, directionIsLeft);
}
//Wenn Sie beide Kinder haben
else {
BST right = present.right;
parent = present;
directionIsLeft = false;
//Finden Sie den Mindestwert unter dem richtigen Kind
while (right.left != null) {
parent = right;
right = right.left;
directionIsLeft = true;
}
//Zum Zeitpunkt des Beendens der vorherigen Zeit gibt rechts den Knoten mit dem Mindestwert unter dem rechten untergeordneten Element an.
//Aktuelle und richtige Daten austauschen
present.value = right.value;
right.value = value;
return deleteNodeEl(root, right, parent, directionIsLeft);
}
}
}
return root;
}
//Eine Funktion, die einen Dichotomiebaum nach dem Löschen eines Geschenks rekonstruiert, wenn ein oder weniger Kinder vorhanden sind
//Gibt die rekonstruierte BST zurück
public static BST deleteNodeEl(BST root, BST present, BST parent, boolean directionIsLeft) {
//Wenn Sie keine Kinder haben
if (present.left == null && present.right == null) {
//Wenn die aktuelle Position root ist
if (parent == null) {
return null;
}
//Wenn die aktuelle Position nicht die Wurzel ist
else {
if (directionIsLeft) {
parent.left = null;
}
else {
parent.right = null;
}
return root;
}
}
//Wenn Sie nur ein Kind haben
else if (present.left == null || present.right == null) {
//Wenn Sie das richtige Kind haben
if (present.right != null) {
//Wenn die aktuelle Position root ist
if (parent == null) {
return present.right;
}
//Wenn die aktuelle Position nicht die Wurzel ist
else {
if (directionIsLeft) {
parent.left = present.right;
}
else {
parent.right = present.right;
}
return root;
}
}
//Wenn Sie links ein Kind haben
else {
//Wenn die aktuelle Position root ist
if (parent == null) {
return present.left;
}
//Wenn die aktuelle Position nicht die Wurzel ist
else {
if (directionIsLeft) {
parent.left = present.left;
}
else {
parent.right = present.left;
}
return root;
}
}
}
return root;
}
public static void main(String[] args) {
BST root = new BST(20);
root = insertNode(root, 10);
root = insertNode(root, 26);
root = insertNode(root, 5);
root = insertNode(root, 14);
root = insertNode(root, 23);
root = insertNode(root, 25);
//Das doppelte Einfügen ist nicht zulässig
root = insertNode(root, 25);
inorder(root);
System.out.println();
System.out.println("10: " + searchNode(root, 10));
System.out.println("23: " + searchNode(root, 23));
//Sie können nicht nach dem suchen, was Sie nicht haben
System.out.println("15: " + searchNode(root, 15));
root = deleteNode(root, 25);
root = deleteNode(root, 14);
//Sie können nicht löschen, was Sie nicht haben
root = deleteNode(root, 14);
inorder(root);
System.out.println();
}
}
Das Ausführungsergebnis ist wie folgt.
5 10 14 20 23 25 26
10: true
23: true
15: false
5 10 20 23 26
Die folgenden Erklärungen basieren auf Java-Programmen. Die folgenden Funktionen sind im obigen Programm implementiert.
--void inorder (BST root): Eine Funktion, die einen dichotomisierten Baum in der Reihenfolge des Durchgangs anzeigt. --BST insertNode (BST root, int value): Eine Funktion, die einen neuen Knoten mit Wert als Daten in den Dichotomiebaum einfügt. --BST deleteNode (BST root, int value): Eine Funktion, die Knoten mit Wert als Daten aus dem Dichotomiebaum löscht. --BST deleteNodeEl (BST-Wurzel, BST vorhanden, BST-Eltern, Boolesche RichtungIsLeft): Eine Funktion, die einen Dichotomiebaum rekonstruiert, wenn ein oder weniger Kinder vorhanden sind.
Die Funktion insertNode vergleicht zunächst die aktuellen Positionsdaten mit dem Wert. Wenn sie gleich sind, kehren sie zurück, ohne einen neuen Knoten zu erstellen. Wenn die Daten an der aktuellen Position größer als der Wert sind, verschieben Sie die aktuelle Position auf das untergeordnete Element links. Wenn der Wert größer als die Daten an der aktuellen Position ist, verschieben Sie die aktuelle Position zum rechten untergeordneten Element. Wiederholen Sie den vorherigen Vorgang, bis kein Ziel mehr vorhanden ist. Wenn kein Ziel vorhanden ist, erstellen Sie einen neuen Knoten mit dem Wert als Daten, und das Einfügen ist abgeschlossen.
Die searchNode-Funktion verhält sich ähnlich wie die zuvor erwähnte insertNode-Funktion. Vergleichen Sie zunächst die aktuellen Positionsdaten mit dem Wert. Wenn die aktuellen Positionsdaten größer als der Wert sind, verschieben Sie die aktuelle Position zum linken untergeordneten Element. Wenn der Wert größer als die Daten an der aktuellen Position ist, verschieben Sie die aktuelle Position zum rechten untergeordneten Element. Wiederholen Sie den vorherigen Vorgang, bis Sie einen Knoten mit Daten erreichen, die dem Wert entsprechen. Wenn der Zielknoten gefunden wird, wird true zurückgegeben, und wenn das Blatt erreicht wird, ohne gefunden zu werden, wird false zurückgegeben und die Suche ist abgeschlossen.
Die Funktion deleteNode ist zunächst auch den Funktionen searchNode und insertNode sehr ähnlich. Wenn die Daten an der aktuellen Position größer als der Wert sind, verschieben Sie die aktuelle Position auf das untergeordnete Element links. Wenn der Wert größer als die Daten an der aktuellen Position ist, verschieben Sie die aktuelle Position zum rechten untergeordneten Element. Wiederholen Sie den vorherigen Vorgang, bis Sie einen Knoten mit Daten erreichen, die dem Wert entsprechen. Wenn Sie den gewünschten Knoten gefunden haben, löschen Sie ihn. Wenn Sie es jedoch einfach löschen, wird sogar das untergeordnete Element des Knotens an der aktuellen Position gelöscht. Daher muss der Bereich unter dem Knoten an der aktuellen Position neu erstellt werden. Stellen Sie zunächst fest, ob der Knoten an der aktuellen Position linke und rechte untergeordnete Elemente hat. Wenn Sie nur ein Kind haben, bewegen Sie dieses Kind einfach an seine aktuelle Position und Sie sind fertig. Wenn Sie auch keine haben, löschen Sie einfach den Knoten an Ihrem aktuellen Standort und Sie sind fertig. Wenn Sie beide untergeordneten Elemente haben, suchen Sie den Knoten mit den kleinsten Daten unter dem rechten untergeordneten Element und tauschen Sie die Daten an diesem Knoten mit den Daten an Ihrem aktuellen Standort aus. Erstellen Sie danach den unteren Bereich des ausgetauschten Knotens neu, und Sie sind fertig.
Das ist der ganze Artikel über den halben Baum, an den ich mich erinnern wollte. Vielen Dank, dass Sie so weit gelesen haben. Ich hoffe, dieser Artikel hilft Ihnen beim Studium.
Recommended Posts