n-ary tree

[jade souza]

hi guys,
i should write a code that creates a tree with arbitrary number of children (every child has pointer to its parent), to support insert a node. is this okay?

class naryTree{
struct Node{
char data;
vector <Node*> children;
Node* parentn;
}
public:
Node* root;
naryTree() {
root = new Node();
root->data=0;
}
Node *CreateNode(char data)
{
Node *parent_node = new Node;
if (parent_node)
parent_node->value = data;
return parent_node;
}
Node *InsertNode(Node *parent, Node *ChildNode, char data)
{
if (parent == NULL)
ChildNode = CreateNode(data);
else
{
TreeNode *childNode = new Node(data);
parent->children.push_back(childNode);
childNode->parentn = parent;
return childNode;
}
return ChildNode;
}

};

[keskiverto]

Please note that this is not a homework site. We won't do your homework for you. The purpose of homework is that you learn by doing. However we are always willing to help solve problems you encountered, correct mistakes you made in your code and answer your questions.

We didn't see your attempts to solve this problem yourself and so we cannot correct mistakes you didn't made and answer questions you didn't ask. To get help you should do something yourself and get real problems with something. If your problem is "I don't understand a thing", then you should go back to basics and study again.

[dhayden]

It's best to use separate classes for the tree and the nodes within the tree.

i should write a code that creates a tree with arbitrary number of children

You don't mention what data each node stores. I'll assume it's an int. As a first start for the nodes, we have:

class Node {
    vector<Node*> children;
    int data;
};

(every child has pointer to its parent)

Let's add that:

class Node {
    vector<Node*> children;
    Node *parent;
    int data;
};

to support insert of a node, printing a tree in preorder and deleting a node.

So the Tree class has these operations. It also has a pointer to the root node:

class Tree {
    Node *root;
    void insert(int val);
    void print(ostream &os);   // print to the stream.
    void delete(int val);
};

Notice that the insert() and delet() methods take an integer to specify the value that you want to add/delete.

[ne555]

	Node *InsertNode(Node *parent, Node *ChildNode, char data) {
		if(parent == NULL)
			ChildNode = CreateNode(data);
		else {
			TreeNode *childNode = new Node(data);
			parent->children.push_back(childNode);
			childNode->parentn = parent;
			return childNode;
		}
		return ChildNode;
	}

¿what's the point of `ChildNode'? you never use its value
also, naryTree::Node is private, not sure how do you expect the client to use it.


and there is no Node(char) constructor, but it should.

[dhayden]

Get rid of createNode() and replace it with a constructor for struct Node:
struct Node{

Node(char d) :
    data(d),
    parent(nullptr)    // createNode() left parent uninitialized.
    {}
char data;
vector <Node*> children;
Node* parent;
}

Regarding inserNode, is the tree sorted? If there are already N children then do you have to descend into a child to insert there?

It might help if you give some more details about what this tree is supposed to do. If this is an assignment, can you post the text of the assignment?

[JLBorges]

> i should write a code that creates a tree with arbitrary number of children (every child has
> pointer to its parent), to support insert a node. is this okay?

Why not keep it simple: have a vector of nodes, instead of a vector of pointers to dynamically allocated nodes?

For example:

#include <iostream>
#include <list> // <vector>
#include <algorithm>
#include <string>
#include <cctype>

struct nary_tree {

    void insert( const std::string& str ) {

        node* n = std::addressof(root) ;
        for( char c : str ) n = n->insert_or_find_child( std::tolower(c) ) ;
        // n->end_of_word = true ; // uncomment to make it a trie
    }

    bool contains( const std::string& str ) const {

        const node* n = std::addressof(root) ;
        for( char c : str ) {

            n = n->find_child( std::tolower(c) ) ;
            if( n == nullptr ) return false ;
        }
        return true ; // trie: return n->end_of_word == true ;
    }

    private:

        struct node {

            node( char c, node* p = nullptr ) : data(c), parent(p) {}

            const node* find_child( char c ) const {

                for( const node& n : children ) if( n.data == c ) return std::addressof(n) ;
                return nullptr ; // not found
            }

            node* insert_or_find_child( char c ) {

                const node* n = find_child(c) ;
                if( n != nullptr ) return const_cast<node*>(n) ;

                children.emplace_back( c, this ) ; // parent == this
                return std::addressof( children.back() ) ;
            }

            char data ;
            std::list /*vector*/<node> children ;
            node* parent ; // non-owning (raw) pointer
        };

        node root { 0, nullptr } ; // root is a marker start node holding a null character
};

int main() {

    const std::string text[] { "code", "that", "CREATES", "a", "tree", "with", "arbitrary", "number", "of", "children" } ;

    nary_tree tree ;
    for( const std::string& word : text ) tree.insert(word) ;

    std::cout << std::boolalpha
              << tree.contains( "creates" ) << '\n' // true
              << tree.contains( "create" ) << '\n' // true
              << tree.contains( "created" ) << '\n' // false
              << tree.contains( "crates" ) << '\n' // false
              << tree.contains( "eat" ) << '\n'  // false
              << tree.contains( "wit" ) << '\n' ; // true
}

http://coliru.stacked-crooked.com/a/978d7fa4714376f7
http://coliru.stacked-crooked.com/a/3114ddbca8cbd823

[ne555]

@JLBorges: the parent pointer will become invalid if the vector reallocates
store pointers, reserve enough capacity (¿possible?) or use a container that doesn't reallocate

or use another method to reference the parent, for example a pointer to the container and an index

[JLBorges]

Right, thanks! Correcting it now; use std::list as std::deque won't allow graceful deletions.