Iterative Inorder Traversal

Question

Hier ist meine Funktion für iterative Inorder Traversal. Aber wenn ich es ausführe, erhalte ich einen Segmentierungsfehler. Ich verwende einen Stapel für die Traversierung. In dem gegebenen Programm habe ich auch eine rekursive Funktion für inorder traversal um zu überprüfen, ob meine create() Funktion funktioniert.

Ich schiebe den Knoten auf den Stapel und Bewegen nach links des Knotens und nach, dass ich den Knoten aus dem Stapel knalle und es Druck und indem root=root->rlink nach rechts gehen.

#include <stdio.h> 
#include <stdlib.h> 
typedef struct node 
{ 
int data; 
struct node *llink; 
struct node *rlink; 
}Node; 
typedef struct Stack 
{ 
Node *a[10]; 
int top; 
}stack; 
void push(stack *s,Node *root) 
{ 
if(s->top==9) 
    printf("FULL"); 
else 
{ 
    s->top++; 
    s->a[s->top]=root; 
} 
} 
Node *pop(stack *s) 
{ 
    if(s->top==-1) 
     printf("Empty"); 
    return s->a[s->top--]; 
} 
void inorder(Node *root) 
{ 
    stack s; 
    s.top=-1; 
    int flag=1; 
    while(flag) 
    { 
    if(s.top!=9) 
    { 
     push(&s,root); 
     root=root->llink; 
    } 
    else{ 
     if(s.top!=-1) 
     { 
      root=pop(&s); 
      printf("%d",root->data); 
      root=root->rlink; 
     } 
     else 
      flag=0; 
    } 
    } 
} 
void inor(Node *root) 
{ 
if(root!=NULL) 
{ 
inor(root->llink); 
printf("%d",root->data); 
inor(root->rlink); 
} 
} 
Node *create(Node *root,int key) 
{ 
if(root==NULL) 
{ 
root=(Node *)malloc(sizeof(Node)); 
root->data=key; 
root->rlink=root->llink=NULL; 
} 
else 
{ 
if(key>root->data) 
{ 
    root->rlink=create(root->rlink,key); 
} 
else if(key<root->data) 
{ 
root->llink=create(root->llink,key); 
} 
} 
return root; 
} 
int main() 
{ 
    Node *h=NULL; 
    h=create(h,5); 
    h=create(h,1); 
    h=create(h,3); 
    h=create(h,8); 
    h=create(h,12); 
    h=create(h,51); 
    inorder(h); 
    //inor(h); 
} 

Answer 1

Wie in meinem Haupt comment diagnostiziert, ist das Problem, dass der Code nicht nach links überquert hinderte, wenn es keine weiteren Knoten in dieser Richtung war. Die Lösung ist einfach:

#include <stdio.h> 
#include <stdlib.h> 

typedef struct node 
{ 
    int data; 
    struct node *llink; 
    struct node *rlink; 
} Node; 

typedef struct Stack 
{ 
    Node *a[10]; 
    int top; 
} stack; 

static 
void push(stack *s, Node *root) 
{ 
    if (s->top == 9) 
     printf("FULL\n"); 
    else 
    { 
     s->top++; 
     s->a[s->top] = root; 
    } 
} 

static 
Node *pop(stack *s) 
{ 
    if (s->top == -1) 
     printf("Empty\n"); 
    return s->a[s->top--]; 
} 

static 
void inorder(Node *root) 
{ 
    stack s; 
    s.top = -1; 
    int flag = 1; 
    while (flag) 
    { 
     //printf("I: %p\n", (void *)root); 
     if (s.top != 9 && root != 0) 
     { 
      push(&s, root); 
      root = root->llink; 
     } 
     else 
     { 
      if (s.top != -1) 
      { 
       root = pop(&s); 
       printf(" %d", root->data); 
       root = root->rlink; 
      } 
      else 
       flag = 0; 
     } 
    } 
} 

static 
void inor(Node *root) 
{ 
    if (root != NULL) 
    { 
     inor(root->llink); 
     printf(" %d", root->data); 
     inor(root->rlink); 
    } 
} 

static 
Node *create(Node *root, int key) 
{ 
    if (root == NULL) 
    { 
     root = (Node *)malloc(sizeof(Node)); 
     root->data = key; 
     root->rlink = root->llink = NULL; 
    } 
    else 
    { 
     if (key > root->data) 
     { 
      root->rlink = create(root->rlink, key); 
     } 
     else if (key < root->data) 
     { 
      root->llink = create(root->llink, key); 
     } 
    } 
    return root; 
} 

int main(void) 
{ 
    int nodes[] = { 37, 2, 19, 9, 7, 41 }; 
    enum { NUM_NODES = sizeof(nodes)/sizeof(nodes[0]) }; 
    Node *h = NULL; 
    h = create(h, 5); 
    h = create(h, 1); 
    h = create(h, 3); 
    h = create(h, 8); 
    h = create(h, 12); 
    h = create(h, 51); 
    printf("Recursive:\n"); 
    inor(h); 
    putchar('\n'); 
    printf("Iterative:\n"); 
    inorder(h); 
    putchar('\n'); 

    for (int i = 0; i < NUM_NODES; i++) 
    { 
     h = create(h, nodes[i]); 
     printf("Iterative:\n"); 
     inorder(h); 
     putchar('\n'); 
    } 
} 

I static auf die Funktionen verwenden, da meine Standard-Compiler-Optionen Funktionen erfordern vor dem Gebrauch deklariert oder definiert werden, und nur static Funktionen können ohne definiert werden, dass vordeklarierte:

gcc -O3 -g -std=c11 -Wall -Wextra -Werror -Wmissing-prototypes -Wstrict-prototypes -Wold-style-definition it37.c -o it37 

Sie können entscheiden, ob das für Sie von Bedeutung ist (aber ich beachte, dass keine andere Datei als diese benötigt, um auf die Funktionen zuzugreifen, so dass "Informationen ausblenden" darauf hinweist, dass die Funktionen static sein sollten).

Beispielausgabe:

Recursive: 
1 3 5 8 12 51 
Iterative: 
1 3 5 8 12 51 
Iterative: 
1 3 5 8 12 37 51 
Iterative: 
1 2 3 5 8 12 37 51 
Iterative: 
1 2 3 5 8 12 19 37 51 
Iterative: 
1 2 3 5 8 9 12 19 37 51 
Iterative: 
1 2 3 5 7 8 9 12 19 37 51 
Iterative: 
1 2 3 5 7 8 9 12 19 37 41 51 

Answer 2

Wie in obigen Ausführungen gegeben, immer in Ihrem Code „root“ bekam zugewiesene Adresse des linken Knoten und wenn Blattknoten erreicht war es in ihm „NULL“ Werte hat und Sie kann nicht auf null zugreifen, weshalb der Code fehlgeschlagen ist und Sie einen Segmentierungsfehler erhalten hätten.

sowieso hier ist mein Code Lösung Ihrer Fehler

#include <stdio.h> 
#include <stdlib.h> 
#include<stdbool.h> 


typedef struct node 
{ 
    int data; 
    struct node *llink; 
    struct node *rlink; 
}Node; 


typedef struct Stack 
{ 
    Node *a[10]; 
    int top; 
}stack; 

void push(stack *s,Node *root); 
Node *pop(stack *s); 
void inorder(Node *root); 



void push(stack *s,Node *root) 
{ 
    if(s->top==9) 
    { 
     printf("FULL"); 
    } 
    else 
    { 
     s->top++; 
     s->a[s->top]=root; 
    } 
} 


Node *pop(stack *s) 
{ 
    if(s->top==-1) 
    { 
     printf("Empty"); 
     return NULL; 
    } 

    return s->a[s->top--]; 
} 
void inorder(Node *root) 
{ 
    stack *s;// took it as a pointer so that i could use it easily 
    s=(stack *)malloc(sizeof(stack)); 
    s->top=-1;//initialized to -1 because we increment top then insert at location indicated by top 
    int flag=1; 
    bool traverse_left=true; 

    while(flag) 
    { 
     if(root->llink!=NULL && traverse_left)//if left link available go left 
     { 
      push(s,root); 
      root=root->llink; 
     } 
     else if((root->llink==NULL&&root->rlink!=NULL)||(root->llink!=NULL && !traverse_left)) 
     { 
      printf("%d ",root->data); 
      root=root->rlink; 
      traverse_left=true; 
     } 
     else if(root->llink==NULL&&root->rlink==NULL) 
     { 
      printf("%d ",root->data); 
      if(root->llink==NULL&&root->rlink==NULL&&s->top==-1) 
      { 
       flag=0; 
      } 
      else 
      { 
       root=pop(s); 
      } 
      traverse_left=false; 
     } 


    } 
} 


void inor(Node *root) 
{ 
    if(root!=NULL) 
    { 
     inor(root->llink); 
     printf("%d",root->data); 
     inor(root->rlink); 
    } 
} 

Node *create(Node *root,int key) 
{ 
    if(root==NULL) 
    { 
     root=(Node *)malloc(sizeof(Node)); 
     root->data=key; 
     root->rlink=root->llink=NULL; 
    } 

    else 
    { 
     if(key>root->data) 
     { 
      root->rlink=create(root->rlink,key); 
     } 
     else if(key<root->data) 
     { 
      root->llink=create(root->llink,key); 
     } 
    } 

return root; 
} 
int main() 
{ 
    Node *h=NULL; 

    h=create(h,5); 
    h=create(h,1); 
    h=create(h,3); 
    h=create(h,8); 
    h=create(h,12); 
    h=create(h,51); 

    inorder(h); 
    //inor(h); 
} 

• In diesem Programm, wenn wir für einen linken Knoten gehen i diesen Knoten in Stapel gelegt, bevor wir nach links Knoten verschoben

• beim Zurückqueren, wenn der Stapel den linken Knoten enthält, bedeutet das, dass wir bereits den linken Baum davon durchlaufen haben, so dass ich ihn platziere und beginne, seinen rechten Unterbaum zu durchlaufen

• wenn ein Knoten des linken und rechten Zeiger null sind i des Knotens aus dem Stapel Pop und starten Sie es richtig ist Unterbaum bitte kommentieren

Wenn Sie irgendwelche Zweifel bezüglich dieser Antwort durchquert.

Answer 3

Inorder Traversal: links, Eltern, rechts

Key Idee iterative Traversal einen Stapel verwendet, ist:

1. Go (auch in den Stack schieben) nach links, bis null gefunden.

2. Die While-Schleife ausführen, bis der Stapel leer ist. Jedes Mal, Pop-Top-Element, fügen Sie es in die Ergebnisliste. Wenn dann ein rechtes Kind vorhanden ist, geh zum rechten Kind (drücke auch in den Stapel) und gehe dann nach links (drücke auch in den Stapel) bis null gefunden wird. Also im Grunde Code für Schritt 1 wird innerhalb der While-Schleife kopiert werden.

-Code wie folgt aussieht:

class Node { 
    int key; 
    Node left, right; 

    public Node() {} 

    public Node(int key) { 
     this.key = key; 
    } 
} 
public List<Integer> inOrderIterative() { 
    List<Integer> list = new ArrayList<>(); 
    Stack<Node> nodeStack = new Stack<>(); 
    Node current = root; 
    nodeStack.push(current); 
    while (null != current.left) { 
     current = current.left; 
     nodeStack.push(current); 
    } 

    while(!nodeStack.empty()) { 
     current = nodeStack.pop(); 
     list.add(current.key); 

     if (null != current.right) { 
      current = current.right; 
      nodeStack.push(current); 
      while (null != current.left) { 
       current = current.left; 
       nodeStack.push(current); 
      } 
     } 
    } 

    return list; 
}