Árbol binary en Objective-C

Estoy aprendiendo algorithms y estructuras de datos y para entrenar estoy tratando de diseñar e implementar un tree binary usando el objective c.

Hasta el momento tengo las siguientes classs:

  • main – para la testing
  • Node – nodo de tree
  • BinaryTree : para todos los methods relacionados con el tree.

Uno de los primeros methods BinaryTree en class insertNode:forRoot: es insertNode:forRoot:

 - (void)insertNodeByRef:(Node **)node forRoot:(Node **)root{ if (head == NULL) { head = *node; } // Case 2 root is null so can assign the value of the node to it if (root == NULL) { root = node; } else { if (node.data > root.data) { // to the right [self insertNode:node forRoot:root.right]; } else if (node.data < root.data) { //or to the left [self insertNode:node forRoot:root.left]; } } } 

Donde se ve la interfaz de la class Node :

 @interface Node : NSObject @property(nonatomic, assign) int data; @property(nonatomic, strong) Node * right; @property(nonatomic, strong) Node * left; @end 

Mi problema es que no sé cómo acceder a las variables de miembro de la class de nodo si estoy pasando Nodo como reference. Cada vez que trato de acceder a las properties del nodo (como datos, izquierda o derecha) obtengo el siguiente post de error:

 Member reference base type 'Node *__autoreleasing *' is not a structure or union 

Entonces, mis preguntas son: ¿cómo puedo acceder a esas properties (datos, izquierda o derecha) y usarlas para almacenar datos int o reference a otro nodo?

Espero que tenga sentido. ¡Gracias!

Solutions Collecting From Web of "Árbol binary en Objective-C"

Su código está mezclando dos enfoques comunes a la tarea, de ahí el problema. También está utilizando un enfoque de tipo de datos abstractos (ADT), en lugar de uno orientado a objects , por lo que hay tres enfoques para considerar.

En ambos enfoques de ADT, su tree se representa mediante una reference a su raíz, en Objective-C esto probablemente se almacena en una variable de instancia:

 Node *TreeRoot; 

Tenga en count también que ambos algorithms utilizan references de campo, a – a->b , en lugar de references de propiedad, ab – esto se debe a que el primero hace reference a una variable y el segundo requiere pasar una reference a una variable.

ADT funcional: Pase por valor y asigne resultado.

En este enfoque, se inserta un nodo en un tree y se devuelve un tree modificado que se asigna de nuevo, por ejemplo, la llamada de nivel superior para insert un Node nodeToInsert sería:

 TreeRoot = insertNode(nodeToInsert, TreeRoot); 

y la function insertNode ve así:

 Node *insertNode(Node *node, Node *root) { if(root == nil) { // empty tree - return the insert node return node; } else { // non-empty tree, insert into left or right subtree if(node->data > root->data) // to the right { root->right = insertNode(node, root->right); } else if(node->data < root->data)//or to the left { root->left = insertNode(node, root->left); } // tree modified if needed, return the root return root; } } 

Tenga en count que en este enfoque, en el caso de un tree (sub) no vacío, el algorithm realiza una asignación networkingundante en una variable: el valor asignado es lo que ya está en la variable … Debido a esto, algunas personas prefieren:

ADT de procedimiento: paso por reference

En este enfoque, la variable que contiene la raíz del (sub) tree se pasa por reference, en lugar de pasar su valor, y se modifica por el procedimiento llamado según sea necesario. Por ejemplo, la llamada de nivel superior sería:

 insertNode(nodeToInsert, &TreeRoot); // & -> pass the variable, not its value 

y el procedimiento insertNode se ve así:

 void insertNode(Node *node, Node **root) { if(*root == nil) { // empty tree - insert node *root = node; } else { // non-empty tree, insert into left or right subtree Node *rootNode = *root; if(node->data > rootNode->data) // to the right { insertNode(node, &rootNode->right); } else if(node->data < rootNode->data)//or to the left { insertNode(node, &root->left); } } } 

Ahora puede ver que su método es una mezcla de los dos enfoques anteriores. Ambos son válidos, pero como está usando Objective-C, podría ser mejor tomar el tercer enfoque:

ADT orientada a objects

Esta es una variación de la ADT de procedimiento: en lugar de pasar una variable a un procedimiento, la variable, ahora llamada object , posee un método que se actualiza por sí mismo. Hacerlo de esta manera significa que debe probar un tree (sub) vacío antes de hacer una llamada para insert un nodo, mientras que los dos enfoques anteriores testingn en la llamada. Entonces, ahora tenemos el método en Node :

 - (void) insert:(Node *)node { if(node.data > self.data) // using properties, could also use fields -> { if(self.right != nil) [self.right insert:node]; else self.right = node; } else if(node.data < rootNode.data) { if(self.left != nil) [self.left insert:node]; else self.left = node; } } 

También debe cambiar la llamada de nivel superior para hacer la misma testing para un tree vacío:

 if(TreeRoot != nil) [TreeRoot insert:nodeToInsert]; else TreeRoot = nodeToInsert; 

Y una nota final: si está utilizando MRC, en lugar de ARC o GC, para administrar la memory, necesitará insert las llamadas de retención / liberación apropiadas.

Espero que te ayude a resolver las cosas.

En primer lugar, no escriba sus methods para tomar Node ** . Es solo confuso

Segundo, piense en cómo debería funcionar. Descríbase cómo debería funcionar a un nivel bastante abstracto. Traduce esa descripción directamente en código, ¡inventando posts nuevos (aún no escritos!) Cuando sea necesario. Si hay pasos que aún no sabe cómo hacerlo, simplemente desconéctelos a los nuevos posts que escribirá más tarde. Te guiaré por eso.

Es BinaryTree que desee que la API pública de BinaryTree incluya este post:

 @interface BinaryTree - (void)insertValue:(int)value; 

Entonces, ¿cómo implementas insertValue: 😕 Finge que eres el object BinaryTree . ¿Cuál es tu descripción de alto nivel de lo que necesitas hacer para insert un valor? Desea crear un nuevo Node . Entonces quieres insert ese nuevo Node en ti mismo. Traducir esa descripción directamente en el código:

 @implementation BinaryTree { Node *root_; // root node, or nil for an empty tree } - (void)insertValue:(int)value { Node *node = [[Node alloc] initWithData:value]; [self insertNode:node]; } 

Ahora piense en cómo hace la inserción. Bueno, si eres un tree vacío, tu root_ es nulo y puedes simplemente configurarlo en el nuevo nodo. De lo contrario, puede pedirle a su nodo raíz que inserte el nuevo nodo debajo de él. Traducir esa descripción directamente en el código:

 - (void)insertNode:(Node *)node { if (root_ == nil) { root_ = node; } else { [root_ insertNode:node]; } } 

Ahora finge que eres un Node . Se te ha pedido que insertes un nuevo Node debajo de ti. ¿Cómo lo haces? Debes comparar el valor del nuevo nodo con tu valor. Si el valor del nuevo nodo es menor que su valor, desea insert el nuevo nodo en su lado izquierdo. De lo contrario, desea insertlo en su lado derecho. Traducir esa descripción directamente en el código:

 @implementation Node - (void)insertNode:(Node *)node { if (node.data < self.data) { [self insertNodeOnLeftSide:node]; } else { [self insertNodeOnRightSide:node]; } } 

Ahora usted todavía es un Node , y se le ha pedido que inserte un nuevo nodo en su lado izquierdo. ¿Cómo lo haces? Bueno, si todavía no tiene un hijo en su lado izquierdo, simplemente use el nuevo nodo como su hijo izquierdo. De lo contrario, le pide a su hijo izquierdo que inserte el nuevo nodo debajo de sí mismo. Traducir esa descripción directamente en el código:

 - (void)insertNodeOnLeftSide:(Node *)node { if (self.left == nil) { self.left = node; } else { [self.left insertNode:node]; } } 

insertNodeOnRightSide: la implementación de insertNodeOnRightSide: como un ejercicio para el lector. ; ^)

Su código, en mi opinión, tiene muchos errores de lógica. Tal vez considere revisar qué es un puntero a puntero para asegurarse de que está diseñando el efecto deseado. Del mismo modo, necesita desvincular nodo / raíz para acceder a ellos en estado normal. De lo contrario, el error es válido, Nodo ** no es el tipo de estructura o unión.

(Node **)node es un puntero a un puntero de object, por lo que node.something es inválido porque usted es una reference muy lejos del object.

Pero (*node).something funcionará.


Adición para comentarios:
Cuando originalmente -(void)insertNodeByRef:(Node **)node forRoot:(Node **)root este método: -(void)insertNodeByRef:(Node **)node forRoot:(Node **)root ¿cómo lo llamas?
Del error que publicaste en tu comentario, mira que estás haciendo:
Node *n = [[Node alloc] init];
[aNode insertNodeByRef:n forRoot:aRoot];

cuando la firma de su método indica que debe llamar así:
[aNode insertNodeByRef:&n forRoot:&aRoot];
Para pasar la dirección del puntero al object.

Lo digo porque su error ahora indica que están enviando Node * lugar de Node ** que son 2 cosas diferentes. (( Incompatible pointer types sending 'Node *' to parameter of type 'Node **' ) He eliminado el __autoreleasing entre los 2 *, estaba oscureciendo el post de error).
Entonces, en otras palabras, está pasando un pointer to an object cuando su método solicita un pointer TO A pointer to an object .