🥇Ағаштың жалпы көрінісі, орындалуы және т.б.

Көптеген адамдар жалпы ағаш құрылысын табуға тырысқан шығар, бірақ іздеу жүйесі тек екіліктерді тапты ... Екілік іздеу ағашы, екілік ағаштың өтуі және басқа да көптеген алгоритмдер.
Иә, шынында да, жалпы ағаш еш жерде қолданылмайды, өту баяу және пайдалану жағдайлары шектеулі.

Сонымен, мен өзіме осы сұрақты қойдым, енді мен ағаштың қалай салынғанын түсіндіремін. Ең дұрысы, жалпы ағаш құрылымы үш айнымалыны сақтауы керек:

үлкен ұлына нұсқау
ағасына нұсқау
сақтағыңыз келетін деректер

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

Біз ағашты осылай саламыз.

P.S. Бұл менің бірінші мақалам, сондықтан мені қатты айыптамаңыз.

Ақпарат көзі: www.habr.com