He creado un programa que contiene una clase Nodo, para representar un árbol binario de cualquier tipo (plantilla).

En mi clase Node.h, tengo dos constructores, sin embargo, no estoy seguro de haberlos implementado correctamente. Inicializar los valores dentro de los constructores me ha confundido. En mi archivo main.cpp, tengo una función setUpTree. Mi programa se ejecuta ahora, pero no imprime el árbol configurado.

He intentado durante horas intentar solucionar este problema, pero sin fin. Todavía no tengo mucha experiencia con C ++, punteros, constructores, etc.

Agradecería que alguien pudiera ayudarme a arreglar mi código para que funcione la función setUpTree, y también el método printTree.

Gracias

Clase Node.h:

   #ifndef NODE_H
#define NODE_H
#include <iostream>
#include <string>
using namespace std;

//an object of type node holds 3 things
// - an item (of type t)
// - a left subtree
// - a right subtree

template<typename T>
class Node {
public:
    Node(T item); //constructor to create a leaf node
    Node(T item, Node *lft, Node *rht); //constructor which creates an internal node 
    ~Node(); //Destructor

    //public data member functions:
    bool searchTree(T key);
    void printTree();

private:
    //private data member functions:
    Node* left;
    Node* right;
    T item;
};

//constructor 
template<typename T>
Node<T>::Node(T i, Node<T> *lft, Node<T> *rht) {
    item = i;
    left = NULL;
    right = NULL;
}

//constructor 
template <typename T>
Node<T>::Node(T i) { //should i be a parameter here?
    item = i; //is this right for this constructor?
}

//destructor
template <typename T>
Node<T>::~Node() {
    delete left;
    delete right;
    //delete;
}


//print tree method
template <typename T>
void Node<T>::printTree() {
    if (left != NULL) {
        left->printTree();
        cout << item << endl;//alphabetical order
    }

    if (right != NULL) {
        right->printTree();
        //cout << item << endl; //post order
    }
}

//search Tree method
template <typename T>
bool Node<T>::searchTree(T key) {
    bool found = false;
    if (item == key) {
        return true;
    }
    if (left != NULL) {
        found = left->searchTree(key);
        if (found) return true;
    }
    if (right != NULL) {
        return right->searchTree(key);
    }
    return false; //if left and right are both null & key is not the search item, then not found == not in the tree.
}

#endif

Clase Main.cpp:

#include "Node.h"
#include <iostream>
using namespace std;

//set up tree method
Node<string> *setUpTree() {
    Node<string> *s_tree =
        new Node<string>("Sunday",
        new Node<string>("monday",
        new Node<string>("Friday"),
        new Node<string>("Saturday")),
        new Node<string>("Tuesday",
        new Node<string>("Thursday"),
        new Node<string>("Wednesday")));
    return s_tree;
}

int main() {

    Node<string> *s_tree;
    s_tree = setUpTree(); //call setUpTree method on s_tree

    cout << "Part 2 :Printing tree values: " << endl;
    s_tree->printTree(); //call print tree method

    cout << endl;

    //search for range of tree values
    //searchTree(s_tree, "Sunday");
    //searchTree(s_tree, "Monday");

    return 0;
}
0
Liam 14 dic. 2016 a las 19:36

2 respuestas

La mejor respuesta

No sé si es el único problema pero ... si construyes una hoja, tienes que configurar los punteros left y right a NULL

template <typename T>
Node<T>::Node(T i) : left(NULL), right(NULL), item(i)
 { }

De lo contrario, cuando se llama al destructor

template <typename T>
Node<T>::~Node() {
    delete left;
    delete right;
    //delete;
}

delete se llama sobre valores indefinidos; dos veces.

Es una receta perfecta para un accidente.

Otros problemas en cada punto que use left o right verificando si el puntero es NULL, como se hizo en printTree() o searchTree(): el valor no está definido, entonces puede ser no NULL, pasa la prueba y se llama a printTree() sobre un puntero con un valor indefinido

- EDITAR -

Constructores sugeridos.

template <typename T>
Node<T>::Node (T i, Node<T> * lft, Node<T> * rht)
 : left(lft), right(right), item(i)
 { }

template <typename T>
Node<T>::Node (T i)
 : left(NULL), right(NULL), item(i)
 { }

--- EDITAR 2 ---

ahora está imprimiendo algunos valores al menos; lunes domingo martes. no estoy seguro del resto

Mira tu método printTree()

Template void Node :: printTree () {if (left! = NULL) {left-> printTree (); cout << item << endl; // orden alfabético}

if (right != NULL) {
    right->printTree();
    //cout << item << endl; //post order
}

}

Imprime el valor (item) solo si left no es NULL. Entonces no imprime el valor de las hojas.

Sugerencia: modifique printTree() para imprimir item incluso cuando left sea NULL.

Por ejemplo

template <typename T>
void Node<T>::printTree() {
    if (left != NULL) {
        left->printTree();
    }

    cout << item << endl;

    if (right != NULL) {
        right->printTree();
    }
}
1
max66 14 dic. 2016 a las 18:52

Primero, el retorno en setupTree debería ser s_tree.

En segundo lugar, construye un árbol binario agregando cada elemento uno a la vez. Sugeriría hacer que setupTree acepte una matriz de valores que luego puede tomar uno a la vez y construir el árbol.

Como se señaló, los valores predeterminados para la izquierda y la derecha deben ser NULL. Sin embargo, simplemente lo haría en la declaración, para que no tenga que repetirlo en todos los constructores donde no se especifican los valores:

private:
    //private data member functions:
    Node* left = NULL;
    Node* right = NULL;
    T item;
2
tinstaafl 14 dic. 2016 a las 16:57