CODEWITHSUNDEEP
c++algorithmtree
angryip
angryip

Reputation: 2290

Traversing a general tree in c++

I am attempting to traverse a general tree. For the purpose of this example, I have this struct to hold my child and parent relationships.

struct DataItem {
    int id;
    DataItem* root;
    vector<DataItem*> children;
};

In comparison to a binary tree traversal, I am not using a *left and *right, as there could be more than one node. To traverse the code, I am using these two methods, called constructMap and then traverseTree.

void traverseTree(std::vector<int>::iterator current, std::vector<int>::iterator end,
    std::vector<int>::iterator next, DataItem *root) {
    while (current != end) {
        DataItem *childNode;
        childNode->id = *current;
        childNode->root = root;
        if (*current + 1 == *next) {
            root->children.push_back(childNode);
        } else {
            // traverse the next tree
            traverseTree(++current, end, ++next, childNode);
        }
        ++next;
        ++current;
    }
}


void constructMap(std::vector<int>::iterator start, std::vector<int>::iterator end) {
    auto next = std::next(start, 1);
    DataItem *parentNode;
    parentNode->id = *start;
    parentNode->root = NULL;
    traverseTree(++start, end, ++next, parentNode);
    cout << " at the end " << endl;
}

I have yet to test the logic to see the traversal is actually functional, though I presume its not, but I keep getting the following error:

Segmentation fault (core dumped)

After some commenting out, it turns that this occurs in the constructMap, when I invoke this call: 

parentNode->id = *start;

If I do something like this instead:

int val = *start;
parentNode->id = val;

I am able to pass this segmentation fault and continue forward.

I am passing an iterator of a vector to my map to process, containing something like this: 1,3,4,5,7,8,10

constructMap(allNumbers.begin(), allNumbers.end());

Upvotes: 1

Views: 3012

Answers (2)

schoetbi
schoetbi

Reputation: 12846

I would not use raw pointers if possible. Either use plain objects or smart pointers such as std::unique_ptr or std::shared_ptr.

Then to traverse the tree you could use a recursive lambda function. I made an example program

#include <functional>
#include <iostream>
#include <vector>
using namespace std;

struct Node {
  Node(int id) : Id(id) {}
  int Id;
  vector<Node> Children;
};

int main(void) {
  int id{};
  Node n0(id++);
  n0.Children.emplace_back(id++);
  n0.Children.emplace_back(id++);
  n0.Children.emplace_back(id++);
  auto &n1 = n0.Children.back();
  n1.Children.emplace_back(id++);
  n1.Children.emplace_back(id++);
  n1.Children.emplace_back(id++);
  n1.Children.emplace_back(id++);
  auto &n2 = n1.Children.back();

  std::function<void(const Node &)> visit = [&](const Node &n) {
    std::cout << n.Id << "\n";
    for (const Node &c : n.Children) {
      visit(c);
    }
  };

  visit(n0);
}

Upvotes: 0

tsandy
tsandy

Reputation: 931

The issue is that you're trying to access the uninitialized pointer parentNode. Maybe make this a simple object:

DataItem parentNode;
parentNode.id = *start;
parentNode.root = NULL;
traverseTree(++start, end, ++next, &parentNode);

Upvotes: 3

Related Questions