🥇树的总体视图、实现等等

许多人可能试图找到通用的树结构，但搜索引擎只找到二叉树......二叉搜索树，二叉树遍历和许多其他算法。
是的，确实如此，一般的树哪里都不用，遍历慢，用例小。

所以，我问自己这个问题，现在我将解释这棵树是如何构建的。因此，理想情况下，一般的树结构应该存储三个变量：

指向长子的指针
指向兄弟的指针
您要存储的数据

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

让我们声明一个指向顶点的指针：

Node *tree = NULL;

我们必须事先约定如何输入顶点；这不是二叉树，每个顶点可以有任意数量的子节点。

+ 2 (或 +ssbb 2) - 插入到树中（对于一般树，路径由行给出，其中 r 是根的创建，s 是到长子的过渡，b 是到长子的过渡兄弟）；

我举个例子：

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

结果将是一棵像这样的树：

首先，让我们创建一个添加顶点的函数，即为顶点分配内存并传递指向该顶点的指针（最初没有连接到任何东西）。

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

您还需要创建一个处理路径字符串（+bs...）的函数。每次我们从根开始遍历，如果没有创建，那么我们输出NULL（我们无能为力）。如果没有顶点，那么我们必须创建它。我们转到创建树函数并获取指向根的指针。

请注意，Node**tree 正在传递结构，而不是复制它。这使我们能够更改 Node *tree 声明无法执行的操作。

一般来说，我们必须找到一个指向我们需要添加儿子的顶点的指针：

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;
    }
}

这就是我们构建一棵树的方式。

PS这是我的第一篇文章，所以请不要过于严厉地评判

来源： habr.com

树的总体视图、实现等

添加评论 取消回复

添加评论取消回复