Empujando nodos para apilar sus valores en un recorrido de árbol en orden -- ampo con tree campo con stack campo con nodes camp Relacionados El problema

Pushing nodes to stack instead their values in an inorder tree traversal


1
vote

problema

Español

Estoy tratando de implementar una primera búsqueda de profundidad usando una pila en C. Sin embargo, tengo mucha dificultad para tratar de averiguar cómo se debe utilizar la pila. Solo puedo presionar el valor de cada nodo de árbol en la pila. ¿Cómo presiono el nodo en sí para poder retroceder y encontrar a los niños de un nodo anterior?

  void printorder(struct node* node, struct stack *pt) {   if (node == NULL) {     return;   }    if (!(node == NULL) || node->visited = false) {     push(pt,node->data); //pushing root to stack     int v = pop(&pt);     printf("Value of pushed node %d",v);     node->visited = true;     push(pt,node->left->data);   } }  int main(void) {   struct stack *pt = newStack(9); //Creating new stack with max capacity 9 (amount of nodes we have total)   struct node *root = newNode(4); //creating root of tree with value 4   root->left = newNode(7);   root->right =newNode(98);   root->left->left = newNode(28);   root->left->left->left = newNode(77);   root->left->left->right = newNode(23);   root->left->right = newNode(86);   root->left->right->left = newNode(3);   root->left->right->right = newNode(9);   printorder(root,pt);       return 0; }    
Original en ingles

I'm trying to implement a depth first search using a stack in C. However, I'm having a lot of difficulty trying to figure out how the stack should be utilized. I can only push the value of each tree node onto the stack. How do I push the node itself so that I can backtrack and find the children of a previous node?

void printorder(struct node* node, struct stack *pt) {   if (node == NULL) {     return;   }    if (!(node == NULL) || node->visited = false) {     push(pt,node->data); //pushing root to stack     int v = pop(&pt);     printf("Value of pushed node %d",v);     node->visited = true;     push(pt,node->left->data);   } }  int main(void) {   struct stack *pt = newStack(9); //Creating new stack with max capacity 9 (amount of nodes we have total)   struct node *root = newNode(4); //creating root of tree with value 4   root->left = newNode(7);   root->right =newNode(98);   root->left->left = newNode(28);   root->left->left->left = newNode(77);   root->left->left->right = newNode(23);   root->left->right = newNode(86);   root->left->right->left = newNode(3);   root->left->right->right = newNode(9);   printorder(root,pt);       return 0; }  
           
       
       

Lista de respuestas

0
 
vote

Recursivo Inorden Tree Traversal

No hay necesidad de una pila explícita para un en orden, profundidad- Primer Transal Traversal . La recursión utiliza la pila de llamadas del proceso como una estructura de datos implícitos. El código que ha proporcionado está prácticamente haciendo esto, aunque parece confundir el pinchazo / POP y las llamadas recursivas y está descuidando la exploración del subárbol derecho de root .

Aquí hay un ejemplo mínimo:

  #include <stdio.h> #include <stdlib.h> #include <string.h>  struct node {     int data;     struct node *left;     struct node *right; };  void printInOrder(struct node *root) {     if (root) {         printInOrder(root->left);         printf("%d ", root->data);         printInOrder(root->right);     } }  struct node *newNode(int data) {     struct node *result = malloc(sizeof(*result));     memset(result, 0, sizeof(*result));     result->data = data;     return result; }  void freeTree(struct node *root) {     if (root) {         freeTree(root->left);         freeTree(root->right);         free(root);     } }  int main() {     /*      0           /             1     2        /          3     4      /    /      5   6 7   8   */     struct node *root = newNode(0);     root->left = newNode(1);     root->right = newNode(2);     root->left->left = newNode(3);     root->left->left->left = newNode(5);     root->left->left->right = newNode(6);     root->left->right = newNode(4);     root->left->right->left = newNode(7);     root->left->right->right = newNode(8);     printInOrder(root);     freeTree(root);     return 0; }   

ITERATIVOS ENORTER ARTE TRAVERSAL

Si necesita hacer esto iterativamente, usted está en un trabajo mucho más que la versión recursiva.

La primera opción de diseño es si la función de la pila interna a la función stack.h2 y use una matriz simple o para escribir una clase de pila. Escribir una clase de pila es mucho más trabajo, pero es reutilizable (parece que ya ha bajado esta ruta).

En cuanto a su encabezado de función existente, es un poco inusual obligar a la persona que llama a asignar recursos que deben ser internos a la llamada de la función; Idealmente, printInOrder es una caja negra genérica y sin estado que la persona que llama puede confiar para hacer su trabajo sin producir efectos secundarios .

Imagine Hacer múltiples llamadas a printInOrder usando la misma pila que podría llevar a resultados sorprendentes, o la persona que llama debe preocuparse por la asignación / desasignación de esta pila.

El algoritmo transversal también se vuelve más complicado. En lugar de imprimir los datos de un nodo en el bucle, debemos presionarlo a la pila y atravesarlo a su hijo izquierdo, repitiendo hasta que el nodo actual sea nulo. Luego, podemos imprimir la parte superior de la pila y hacer que el nodo actual sea el niño derecho del nodo impreso. Repita hasta que se agote la pila.

Aquí está el algoritmo iterativo con una pila interna y funciona como una entrega en el ejemplo del código anterior:

  void printInOrder(struct node *root) {     int capacity = 4;     int top = 0;     struct node **stack = malloc(sizeof(*stack) * capacity);      for (stack[top] = root; top >= 0;) {         for (root = stack[top--]; root; root = root->left) {             if (top >= capacity &&                  !(stack = realloc(stack, sizeof(stack) * (capacity *= 2)))) {                 fprintf(stderr, "%s [%d] realloc failed ", __FILE__, __LINE__);                 exit(1);             }              stack[++top] = root;         }          if (top >= 0) {             root = stack[top--];             printf("%d ", root->data);             stack[++top] = root->right;         }     }      free(stack); }   

Aquí hay una versión que usa una clase de pila. La lógica es mucho más limpia, pero hemos introducido una dependencia.

stack.h

  #ifndef STACK_H #define STACK_H  #include <stdbool.h> #include <stdlib.h> #include <string.h>  struct stack {     int top;     int capacity;     void **entries; };  struct stack *createStack(int capacity) {     if (capacity <= 0) return NULL;      struct stack *s = malloc(sizeof(*s));     s->top = -1;     s->capacity = capacity;     s->entries = malloc(sizeof(*s->entries) * capacity);     return s; }  bool empty(struct stack *s) {     return s->top < 0; }  void freeStack(struct stack *s) {     free(s->entries);     free(s); }  void *pop(struct stack *stack) {       if (stack->top < stack->capacity / 2 - 1) {         stack->entries = realloc(stack->entries,                                   sizeof(stack->entries) *                                   (stack->capacity /= 2));         if (!stack->entries) {             fprintf(stderr, "%s [%d] realloc failed ", __FILE__, __LINE__);             exit(1);         }     }      return stack->entries[stack->top--]; }  void push(struct stack *stack, void *data) {     if (stack->top >= stack->capacity) {         stack->entries = realloc(stack->entries,                                   sizeof(stack->entries) *                                   (stack->capacity *= 2));         if (!stack->entries) {             fprintf(stderr, "%s [%d] realloc failed ", __FILE__, __LINE__);             exit(1);         }     }      stack->entries[++stack->top] = data; }  #endif   

main.c

  #include <stdio.h> #include <stdlib.h> #include "stack.h"  struct node {     int data;     struct node *left;     struct node *right; };  void printInOrder(struct node *root) {     struct stack *stack = createStack(4);      for (push(stack, root); !empty(stack);) {         for (root = pop(stack); root; root = root->left) {             push(stack, root);         }          if (!empty(stack)) {             root = pop(stack);             printf("%d ", root->data);             push(stack, root->right);         }     }      freeStack(stack); }  struct node *newNode(int data) {     struct node *result = malloc(sizeof(*result));     memset(result, 0, sizeof(*result));     result->data = data;     return result; }  void freeTree(struct node *root) {     if (root) {         freeTree(root->left);         freeTree(root->right);         free(root);     } }  int main() {     /*      0           /             1     2        /          3     4      /    /      5   6 7   8   */     struct node *root = newNode(0);     root->left = newNode(1);     root->right = newNode(2);     root->left->left = newNode(3);     root->left->left->left = newNode(5);     root->left->left->right = newNode(6);     root->left->right = newNode(4);     root->left->right->left = newNode(7);     root->left->right->right = newNode(8);     printInOrder(root);     freeTree(root);     return 0; }   
 

Recursive inorder tree traversal

There's no need for an explicit stack for an in order, depth-first tree traversal. Recursion uses the process' call stack as an implicit data structure. The code you've provided is practically doing this although it appears to conflate the stack push/pop and the recursive calls and is neglecting exploration of the right subtree of root.

Here's a minimal example:

#include <stdio.h> #include <stdlib.h> #include <string.h>  struct node {     int data;     struct node *left;     struct node *right; };  void printInOrder(struct node *root) {     if (root) {         printInOrder(root->left);         printf("%d\n", root->data);         printInOrder(root->right);     } }  struct node *newNode(int data) {     struct node *result = malloc(sizeof(*result));     memset(result, 0, sizeof(*result));     result->data = data;     return result; }  void freeTree(struct node *root) {     if (root) {         freeTree(root->left);         freeTree(root->right);         free(root);     } }  int main() {     /*      0           /   \          1     2        /   \       3     4      / \   / \     5   6 7   8   */     struct node *root = newNode(0);     root->left = newNode(1);     root->right = newNode(2);     root->left->left = newNode(3);     root->left->left->left = newNode(5);     root->left->left->right = newNode(6);     root->left->right = newNode(4);     root->left->right->left = newNode(7);     root->left->right->right = newNode(8);     printInOrder(root);     freeTree(root);     return 0; } 

Iterative inorder tree traversal

If you do need to do this iteratively, you're in for much more work than the recursive version.

The first design choice is whether to make the stack internal to the printInOrder function and use a simple array or to write a stack class. Writing a stack class is a lot more work, but is reusable (it looks like you've already gone down this route).

As for your existing function header, it's a bit unusual to force the caller to allocate resources that should be internal to the function call; ideally, printInOrder is a generic, stateless black box that the caller can trust to do its job without producing side effects.

Imagine making multiple calls to printInOrder using the same stack which might lead to surprising results, or the caller having to worry about allocation/deallocation of this stack.

The traversal algorithm also becomes more complicated. Instead of printing a node's data in the loop, we need to push it on to the stack and traverse to its left child, repeating until the current node is null. Then we can print the top of the stack and make the current node the just-printed node's right child. Repeat until the stack is exhausted.

Here's the iterative algorithm with an internal stack and works as a drop-in to the above code example:

void printInOrder(struct node *root) {     int capacity = 4;     int top = 0;     struct node **stack = malloc(sizeof(*stack) * capacity);      for (stack[top] = root; top >= 0;) {         for (root = stack[top--]; root; root = root->left) {             if (top >= capacity &&                  !(stack = realloc(stack, sizeof(stack) * (capacity *= 2)))) {                 fprintf(stderr, "%s [%d] realloc failed\n", __FILE__, __LINE__);                 exit(1);             }              stack[++top] = root;         }          if (top >= 0) {             root = stack[top--];             printf("%d\n", root->data);             stack[++top] = root->right;         }     }      free(stack); } 

Here's a version that uses a stack class. The logic is much cleaner but we've introduced a dependency.

stack.h

#ifndef STACK_H #define STACK_H  #include <stdbool.h> #include <stdlib.h> #include <string.h>  struct stack {     int top;     int capacity;     void **entries; };  struct stack *createStack(int capacity) {     if (capacity <= 0) return NULL;      struct stack *s = malloc(sizeof(*s));     s->top = -1;     s->capacity = capacity;     s->entries = malloc(sizeof(*s->entries) * capacity);     return s; }  bool empty(struct stack *s) {     return s->top < 0; }  void freeStack(struct stack *s) {     free(s->entries);     free(s); }  void *pop(struct stack *stack) {       if (stack->top < stack->capacity / 2 - 1) {         stack->entries = realloc(stack->entries,                                   sizeof(stack->entries) *                                   (stack->capacity /= 2));         if (!stack->entries) {             fprintf(stderr, "%s [%d] realloc failed\n", __FILE__, __LINE__);             exit(1);         }     }      return stack->entries[stack->top--]; }  void push(struct stack *stack, void *data) {     if (stack->top >= stack->capacity) {         stack->entries = realloc(stack->entries,                                   sizeof(stack->entries) *                                   (stack->capacity *= 2));         if (!stack->entries) {             fprintf(stderr, "%s [%d] realloc failed\n", __FILE__, __LINE__);             exit(1);         }     }      stack->entries[++stack->top] = data; }  #endif 

main.c

#include <stdio.h> #include <stdlib.h> #include "stack.h"  struct node {     int data;     struct node *left;     struct node *right; };  void printInOrder(struct node *root) {     struct stack *stack = createStack(4);      for (push(stack, root); !empty(stack);) {         for (root = pop(stack); root; root = root->left) {             push(stack, root);         }          if (!empty(stack)) {             root = pop(stack);             printf("%d\n", root->data);             push(stack, root->right);         }     }      freeStack(stack); }  struct node *newNode(int data) {     struct node *result = malloc(sizeof(*result));     memset(result, 0, sizeof(*result));     result->data = data;     return result; }  void freeTree(struct node *root) {     if (root) {         freeTree(root->left);         freeTree(root->right);         free(root);     } }  int main() {     /*      0           /   \          1     2        /   \       3     4      / \   / \     5   6 7   8   */     struct node *root = newNode(0);     root->left = newNode(1);     root->right = newNode(2);     root->left->left = newNode(3);     root->left->left->left = newNode(5);     root->left->left->right = newNode(6);     root->left->right = newNode(4);     root->left->right->left = newNode(7);     root->left->right->right = newNode(8);     printInOrder(root);     freeTree(root);     return 0; } 
 
 

Relacionados problema

4  Pasaporte no guardará en la variable de sesión. req.user no existe después de navegar  ( Passport wont save within session variable req user does not exist after naviga ) 
Fondo: Tengo un CLI angular que se ejecuta en el puerto 4200, y la API API NNODE.JS del servidor que se ejecuta en 3000. Averigua que el valor del pasapor...

0  Bluemix Tiempo nodo deodo siempre está lanzando "Falló la llamada con la respuesta http de error"  ( Bluemix weather node of nodered is always throwing call failed with error http ) 
Estoy tratando de probar las ideas para el servicio meteorológico de Bluemix usando la plantilla de la caldera negra. Creé una aplicación simple y señala el s...

1  ¿Cómo rellenar dinámicamente a JTree?  ( How to populate jtree dynamically ) 
Estoy trabajando en un proyecto que requiere el uso de una estructura de datos de árboles. Después de haber hecho algunas investigaciones, encontré que Java J...

-1  Error de Error de API de Nodejs y Twitter: Mala solicitud de transmisión de Twitter: 404 '  ( Nodejs and twitter api error error bad twitter streaming request 404 ) 
Hola, quiero crear un bot que envíe automáticamente un mensaje a los hombres que lo siguen urlpatterns = patterns('', url(r'^ajax/$', views.ajax), ...

1  Cómo leer el archivo XML en Java sin TagName  ( How to read xml file in java without tagname ) 
Necesito leer un archivo XML en Java, el documento XMD se ve así: technique RibbonShader { pass Pass0 { VertexShader = compile vs_2_0 Ve...

5  Usando DOMNodeInserted para reescribir HTML antes de que finalice la carga  ( Using domnodeinserted to rewrite html before it finishes loading ) 
Siento que esto probablemente será inmediatamente obvio para cualquiera de los no amateurs por ahí, pero me he estado perplejo en esto durante días. Estoy e...

1  Prolog necesita calcular el tamaño del árbol  ( Prolog need to compute the tree size ) 
Necesito obtener el tamaño de un árbol usando: protected void AgregarPunto(DataTable result) { layerObj thislayer = util.MSMap.getLayerByName("poi"); ...

0  JSOUP usando nodos para obtener un texto específico que está fuera de las etiquetas HTML  ( Jsoup using nodes to get specific text that is outside html tags ) 
Entonces, he estado usando JSOUP para analizar un sitio web para algunos metadatos, lo que funciona muy bien. El problema es que algunos de los metadatos impo...

2  Cómo obtener instancia de clase de nodo de MOBJECT en MAYA API  ( How to get node class instance from mobject in maya api ) 
En un complemento de CPP, estoy desarrollando en Maya API, registro un nodo MPXTRANSFORM personalizado en la función inicializePlugin: status=pluginFn.regi...

8  Conversión de gráficos no dirigidos al árbol  ( Undirected graph conversion to tree ) 
Dado una gráfico no dirigido en el que cada nodo tiene una coordenada cartesiana en el espacio que tiene La forma general de un árbol, ¿hay un algoritmo par...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos