Wie liefert diese Rekursionsfunktion in BST eine verkettete Liste, die in der richtigen Reihenfolge ist?

Question

Wie liefert diese Rekursionsfunktion in BST eine verkettete Liste, die in der richtigen Reihenfolge ist?

Gegeben: (Struktur)

typedef struct TreeNode 
{ 
    struct TreeNode *left ; //left child 
    struct TreeNode *right ;  //right child 
    struct TreeNode *next ; //field for linked list in tree 
    Data Node_info;    //info data in node 
} TreeNode; 

Nehmen wir an, wir ein BST mit den Nummern 3,2,4 haben. (3 ist root, 2 ist links Kind, 4 ist richtig Kind)

Ich habe 2 Funktionen, die das gleiche tun, sie erstellen eine verknüpfte Liste von der BST. Ich folge der Rekursion hier nicht weiter, wenn mir jemand helfen kann, es herauszufinden, wäre es großartig!

Erste Funktion:

void what1(TreeNode **head, TreeNode *root) 
{ 
    if(root == NULL) 
      return; 
    what1((head),root->right); 
    root->next=(*head); 
    (*head)=root; 
    what1((head),root->left); 
} 

Meine Berechnungen: Zum rechten Unterbaum, bis wir null zu erreichen, Rückkehr, 4-> nächsten Punkt auf NULL machen, Kopfpunkt auf 4 machen, dann gehen Sie nach links , zurück zu 4, zurück zu 1, jetzt 3-> nächster Punkt auf 4, und Kopfpunkt auf 4, und so weiter ..

Aber mir fehlt noch das Verständnis, wenn andere Funktionen "auf Halten" sind und wann werden sie ausgeführt, was bedeutet, dass meine Berechnungen nicht korrekt sind und ich die Funktion nicht richtig befolge, was bedeutet, dass ich irgendwo keine Rekursion unde habe Standing.

Hier ist die zweite Funktion, die ich absolut KEINE IDEE habe, wie man ihr folgt, was eigentlich das Gleiche macht. Wenn Sie mir mit einer dieser Funktionen helfen können, würde es sehr geschätzt werden, wenn ich versuche, Rekursion mit BST vollständig zu verstehen. Ich schreibe hier viele Fragen dazu, bis ich das vollständig verstehe.

TreeNode * what2(TreeNode *root) 
{ 
    TreeNode *left = NULL, *right = NULL, *tmp = root; 
    if (root != NULL) 
    {  
     left = what2(root->left);  
     right = what2(root->right);  
     root->next = right;  
     if (left != NULL) 
     { 
      tmp=left; 
      while (left->next != NULL)    
       left=left->next;   
      left->next=root;  
     } 
    } 
    return tmp; 
} 

Answer 1

Dies ist für what1. Hier

ist head ein Node ** - was bedeutet, dass:

head : is a : pointer to a pointer to TreeNode 
*head : is a : pointer to a TreeNode 
**head : is a : TreeNode 

Nun, wenn what1 diese aus dem Haupt genannt wird (oder eine andere Funktion) es wie folgt aufgerufen:

/* Suppose root points to root TreeNode in tree */ 

/* ll_head will point to first node in linked list */ 
TreeNode *ll_head = NULL; 

/* Call what1 and pass address of ll_head so that 
* address of the first node in linked_list can be stored in ll_head 
*/ 
what1(&ll_head, root); 

Jetzt sehen was passiert, wenn what1(&llhead, root), (dh what1(&ll_head, node 3)) heißt:

Wenn what1(&ll_head, node 3) genannt wird, macht es die folgenden:

1. Calls (& ll_head, Knoten 4)
2. hat einige Verarbeitung für den Knoten 3
3. Calls (& ll_head, Knoten 2)

Lets sehen sie eins nach dem anderen:

1.In Knoten 4

4->next = (*head) /* which right now is pointing to NULL */ 
(*head) /* which is ll_head in main */ = address of node 4 

So, jetzt:

4->next = NULL, and 
(*head) /* which is ll_head in main */ = address of node 4 

2. Verarbeitung im Knoten 3

3->next = (*head) /* which right now is pointing to node 4 */ 
(*head) /* which is ll_head in main */ = address of node 3 

So, jetzt:

4->next is NULL, 
3->next = address of node 4, and 
(*head) /* which is ll_head in main */ = address of node 3 

3. Im Knoten 2

2->next = (*head) /* which right now is pointing to node 3 */ 
3->next = address of node 4 
4->next = NULL, and 
(*head) /* which is ll_head in main */ = address of node 2 

Also, wenn What1 (* ll_head, node3) dies der Stand der Dinge wird zurückgibt:

ll_head = address of node 2 
2->next = address of node 3 
3->next = address of node 4 
4->next = NULL 

Welche die um verkettete Liste dieses BST ist.

Answer 2

Sie haben recht, wie die erste Funktion funktioniert, Sie bauen den Baum im Grunde von Anfang bis Ende.

Um die zweite zu verstehen, müssen Sie nur bemerken, dass es eine Liste in den Unterbäumen erstellt und dann die zwei Listen kombiniert. Wenn Sie die Funktion aufrufen, passieren die folgenden Schritte:

1. den Kopf des aus dem linken Knoten
2. allein erstellt Liste Holen Sie sich den Kopf der Liste Erhalten Sie allein vom rechten Knoten erstellt
3. die Wurzel Attach Knoten, indem Sie das Ende der linken Liste so einstellen, dass es auf root zeigt, und dann den Wurzelpunkt an den Anfang der rechten Liste setzen.

Dies kann durch

1.

left = what2(root->left); 

In Ihrem Beispiel zu sehen ist, wird dies einfach die linke Knoten zurück, weil sie allein ist, aber dies geschieht, weil left->left und left->right NULL sind für der linke Knoten, so dass es einfach left zurückgibt.

2.

right = what2(root->right); 

Die gleiche Sache geschieht hier, aber mit dem richtigen Knoten.

3.

root->next = right;  
if (left != NULL) 
{ 
    tmp=left; 
    while (left->next != NULL)    
     left=left->next;   
    left->next=root;  
} 

Hier setzen wir zuerst root->next zu right so, dass wir die Mitte der Liste erstellt im Grunde haben. Dann setze tmp auf left, weil es der Kopf der Liste sein wird (am weitesten links, also am Anfang). Durchqueren Sie dann die linke Liste, bis wir das letzte Element auf root setzen können. Dies erzeugt eine fortlaufende Liste von left bis root bis right, also in Reihenfolge.