🥇트리, 구현 등에 대한 일반적인 보기

많은 사람들이 아마도 일반적인 트리 구성을 찾으려고 노력했지만 검색 엔진은 이진 검색 트리, 이진 트리 순회 및 기타 여러 알고리즘만 찾았습니다.
예, 실제로 일반 트리는 어디에도 사용되지 않으며 순회가 느리고 사용 사례가 작습니다.

그래서 저는 스스로에게 이런 질문을 던졌고 이제 트리가 어떻게 만들어지는지 설명하겠습니다. 따라서 이상적으로 일반 트리 구조는 세 가지 변수를 저장해야 합니다.

장남을 가리키는 말
형제를 가리키는 포인터
저장하려는 데이터

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

이것이 우리가 나무를 만드는 방법입니다.

추신 첫 글이니 너무 가혹하게 판단하지 말아주세요

출처 : habr.com

트리, 구현 등에 대한 일반적인 보기

코멘트를 추가 답장을 취소