General view of the tree, implementation and more

Many have probably tried to find a general tree structure, but the search engine only found binary ones... Binary search tree, traversing a binary tree, and many other algorithms.
Yes, indeed, a general tree is not used anywhere, the traversal is slow, and the use cases are limited.

So, I asked myself this question, and now I will explain how a tree is built. Ideally, the structure of a general tree should store three variables:

• a pointer to the eldest son
• a pointer to the brother
• the data you intend to store

struct Tnode {
    int key;
    struct Tnode *son;
    struct Tnode *brother;
};
typedef struct Tnode Node;

Let's declare a pointer to the root:

Node *tree = NULL;

We must agree in advance on how to input nodes, as this is not a binary tree, and each node can have any number of sons.

• + 2 (or +ssbb 2) — insert into the tree (for a general tree, the path is specified by a string, where r creates the root, s is a transition to the eldest son, b is a transition to the brother);

Let me give an example:

+r 1
+ 2
+ 3
+ 3
+s 5
+sb 6
+sb 7

As a result, we will get the following tree:

1
  2
    5
  3
    6
    7
  3

First, we will create a function that performs the addition of a node, specifically allocating memory for the node and passing the pointer to this node (initially not linked to anything).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  // initialize pointers to brothers and sons, an independent node holding value
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

It is also necessary to create a function that processes the path string (+bs…). Each time we start the traversal from the root; if it is not created, we output NULL (we cannot do anything). If the node does not exist, we must create it. We go to the create tree function and get a pointer to the root.

Note that Node **tree passes the structure, rather than copying it. This gives us the ability to modify, unlike declaring Node *tree.

In general, we need to find the pointer to the node where we need to add a son:

Node* add_node(Node **tree, const char *a) {
  Node* t = *tree;
  int value;
  scanf("%d", &value);
  int i = 0;
      while (a[++i] != ' ') {
        if (a[i] == 'r') {
            *tree = create_tree(value); // create root
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // function that returns a pointer to son
            continue;
          return NULL; // otherwise NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) // returns a pointer to brother t
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // we reached the peak we wanted to
   // and now we go to its last son,
   // to add to the end of the list
    t->brother = create_tree(value);
    return t->brother;
    }
    else {// if there is no son, we will create one
      t->son = create_tree(value);
      return t->son;
    }
}

Thus we build the tree.

P.S. This is my first article, so please be kind.

Source: habr.com