/ / Algorithmus für Nachfolger - Algorithmus

Algorithmus für den Nachfolger - Algorithmus

Ich brauche einen Algorithmus, um den Nachfolgerknoten eines beliebigen Knotens der gegebener binärer Suchbaum.

Antworten:

5 für die Antwort № 1

Um Ihnen eine Antwort mit dem gleichen Detaillierungsgrad wie Ihrer Frage zu geben: Gehen Sie nach oben, bis Sie nach rechts gehen können, und dann nach links, bis Sie ein Blatt erreichen.


1 für die Antwort № 2

Es gibt zwei allgemeine Ansätze:

  • Wenn Ihre binären Baumknoten Zeiger auf ihre habenElternknoten, dann können Sie direkt vom Knoten zum Nachfolgerknoten übergehen. Sie müssen festlegen, wie die übergeordneten Zeiger für die Traversierung verwendet werden.
  • Wenn Ihre binären Baumknoten dies tun nicht Haben Sie Elternzeiger, dann müssen Sie eine Inorder-Traversierung des Baumes durchführen, beginnend bei der Wurzel (vermutlich haben Sie einen Wurzelknotenzeiger) und den nächsten Knoten nach dem gegebenen Knoten zurückgeben.

0 für die Antwort № 3

Sie müssen ein beibehalten Reißverschluss wenn du den Baum hinabsteigst. Ein Zipper ist einfach eine Liste der Knoten, die Sie durchlaufen haben, und für jeden eine Anzeige, ob Sie als nächstes nach links oder rechts gegangen sind. Es erlaubt Ihnen, wieder in den Baum zu reisen, auch wenn es keine Hinweise von Kindern zu Eltern gibt.

Der Algorithmus für den Nachfolger ist, zurückzugehen (oben im Reißverschluss), solange du von links kommst, dann gehst du einmal nach rechts und dann nach links zum untersten Kind.

Es ist einfacher mit einer Figur ...


0 für die Antwort № 4

Der Nachfolger eines Knotens bedeutet, dass Sie nach einem Inorder-Nachfolger suchen. Die folgende Methode hilft Ihnen beim Bestimmen des Inorder-Nachfolgers OHNE PARENT NODE ODER EXTRA SPACE NON-RECURSIVY

struct node * inOrderSuccessor(struct node *root, struct node *n)
{
//*If the node has a right child, return the smallest value of the right sub tree*

if( n->right != NULL )
return minValue(n->right);

//*Return the first ancestor in whose left subtree, node n lies*
struct node *succ=NULL;
while(root)
{
if(n->datadata < root->data)
{
succ=root; root=root->left;
}

else if(n->data > root->data)
root=root->right;
else break;
}
return succ;
}

Ich bin mir ziemlich sicher, dass das richtig ist. Berichtigen Sie mich, wenn ich falsch liege. Danke.