Data structure/Tree

[asxxx]

Hello.I start my adevneture with trees and I know only about binary trees I want to build family tree using tree structure ofcourse. I create something like that so far I think that is not enough because family members can be more than two so binary tree is not enough. Please any tips and thanks for help !

  struct node
{
char *data;
struct node *left;
struct node* right;

}

[Duthomhas]

struct node
{
  int data;
  std::vector <node> children;
};

[asxxx]

Children are pointers to down nodes in tree?

[jonnin]

yes.
pointers of the same type as themselves, chained until the pointer is a special terminal value "null".
node -> children[0]->children[3]->children[11]…. child[11] there is the great-grandchild of node.

any size-adjustable container can be used to contain the child pointers, including another tree or a linked list or whatever. A vector is probably best.

[Duthomhas]

The only downside to using a vector is that children must appear in order from first to last without any gaps. That is, you cannot have a NULL first child and a non-NULL second child.

If you need to have arbitrary branches then make a nullary node type. An easy way would be to use std::optional<>.

struct node
{
  int data;
  std::vector <std::optional <node> > children;
};

struct node
{
  std::optional <int> data;
  std::vector <node> children;
};

This would mean that you would have to check everything for non-null-ness before every access, though. So if you can design your algorithm without needing that life is easier.


Heh, figured I would compile this first, just to make sure I didn’t steer you wrong. Here is a full example:

#include <iostream>
#include <optional>
#include <vector>

struct node
{
  std::string data;
  std::vector <std::optional <node> > children;
};

std::ostream& operator << ( std::ostream& outs, const node& n )
{
  if (!n.children.empty()) outs << "(";
  outs << n.data;
  for (auto child : n.children)
    if (child) outs << " " << *child;
    else       outs << " ()";
  if (!n.children.empty()) outs << ")";
  return outs;
}

int main()
{
  auto xs =
  node{ "*", {
    node{ "+", {
      node{ "1" },
      node{ "2" } } },
    node{ "3" } } };
  std::cout << xs << "\n";
}

[jonnin]

The only downside to using a vector is that children must appear in order from first to last without any gaps. That is, you cannot have a NULL first child and a non-NULL second child.

I don't disagree, but it seems like a non-issue.
- if the vector is empty, no children, node is a leaf.
- else, node has children.
- the vector should not have null nodes at all? If you deleted someone (and presumably their kids: no shuffle makes sense to reinstate them) you wouldn't keep a pointer?

[Duthomhas]

jonnin wrote:

I don't disagree, but it seems like a non-issue.

Sometimes it does matter, though.

I personally try to avoid designing my structures in a way that it does matter.

Though, the coolest (and scariest) thing I ever did was make a s-expression using shared_ptrs. Give me a bit and I’ll trim down an example for y’all here.

[Duthomhas]

Meh, I can't trim it down to less than a couple hundred lines without giving you nothing to see. Suffice to say it is a nested variant/shared_ptr that essentially looks like this:

    struct value : shared_ptr <variant <TYPES>>
    {
      value car;
      value cdr;
    };

It is an S-expression for a version of Scheme I was writing (and will maybe finish some day, should I find time and interest).

[dhayden]

If this program is more than a toy then a tree isn't the right structure. Consider this situation, which I heard happened years ago, but don't recall the people involved:

John has a son named Bob
Jane has a daughter named Sue.
John marries Sue and Bob marries Jane.

So John is his own grandfather-in-law, because he is his wife's mother's husband's father.

Also how will you represent step-children? Or adopted vs. natural children?

A more robust structure is a table:

person1 id, person2 id,  relationship

[Duthomhas]

Is there a SQL to this story...?

[asxxx]

Thanks everyone for help !