🥇General view of the tree, implementation and more

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

So, I asked this question and now I will explain how a tree is built after all. So, ideally, a general tree structure should store three variables:

pointer to eldest son
pointer to brother
the data you are going to store

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

Let's declare a pointer to the top:

Node *tree = NULL;

We must agree in advance how to input vertices, this is not a binary tree, and each vertex can have any number of children.

+ 2 (or +ssbb 2) - insert into the tree (for a general tree, the path is given by a string, where r is the creation of the root, s is the transition to the eldest son, b is the transition to the brother);

I will give an example:

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

This will result in a tree like this:

To begin with, let's create a function that adds a vertex, namely, it allocates memory for a vertex and passes a pointer to this vertex (initially unrelated to anything).

Node *create_tree(int v) {
  Node *Tree = (Node *) malloc(sizeof(Node));
  Tree->key = v;
  //обнуляем указатели к братьям и сыновьям, независимая вершина, которая хранит value
  Tree->son = NULL;
  Tree->brother = NULL;
  return Tree;
}

You also need to create a function that handles the path string (+bs...). Each time we start the traversal from the root, if it is not created, then we output NULL (we cannot do anything). If there is no vertex, then we must create it. We pass into the function to create a tree and get a pointer to the root.

Note, Node**tree passes the structure, not copies. This gives us the ability to change, which can't be done, unlike the Node *tree declaration.

In general, we must find a pointer to the top, to which 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); // создаем корень
            t = *tree;
            return *tree;
          }
        if (a[i] == 's') {
          if (t = to_son(t)) // функция, которая возвращает указатель на сына
            continue;
          return NULL; //иначе NULL
        }
        if (a[i] == 'b') {
          if (t = to_brother(t)) //возвращает указатель на брата t 
            continue;
          return NULL;
        }
    }
    if (t->son != NULL) {
    t = last_son(t); // мы перешли к вершине, к которой хотели 
   //и теперь идем к последнему ее сыну,
   //чтобы добавить в конец списка
    t->brother = create_tree(value);
    return t->brother;
    }
    else {//если сына нет, то создадим его
      t->son = create_tree(value);
      return t->son;
    }
}

Thus we build a tree.

PS my first article, so please do not judge strictly

Source: habr.com

General view of the tree, implementation and more

Add a comment Отменить ответ