ගස පිළිබඳ පොදු දැක්ම, ක්රියාත්මක කිරීම සහ තවත් දේ

බොහෝ අය බොහෝ විට සාමාන්‍ය ගස් ඉදිකිරීමක් සොයා ගැනීමට උත්සාහ කළ නමුත් සෙවුම් යන්ත්‍රය සොයා ගත්තේ ද්විමය ඒවා පමණි ... ද්විමය සෙවුම් ගස, ද්විමය ගස් ට්‍රැවර්සල් සහ තවත් බොහෝ ඇල්ගොරිතම.
ඔව්, ඇත්ත වශයෙන්ම, සාමාන්‍ය ගස කොතැනකවත් භාවිතා නොවේ, ගමන් කිරීම මන්දගාමී වේ, භාවිත අවස්ථා කුඩා වේ.

ඉතින්, මම මෙම ප්රශ්නය මගෙන්ම ඇසුවෙමි, දැන් මම ගස ඉදිකරන ආකාරය පැහැදිලි කරමි. එබැවින්, ඉතා මැනවින්, සාමාන්ය ගස් ව්යුහයක් විචල්ය තුනක් ගබඩා කළ යුතුය:

• වැඩිමහල් පුතාට දර්ශකය
• සහෝදරයාට දර්ශකය
• ඔබ ගබඩා කිරීමට යන දත්ත

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

ප්‍රති result ලය මේ වගේ ගසක් වනු ඇත:

1
  2
    5
  3
    6
    7
  3

පළමුව, අපි ශීර්ෂයක් එකතු කරන ශ්‍රිතයක් නිර්මාණය කරමු, එනම්, ශීර්ෂයට මතකය වෙන් කර, මෙම ශීර්ෂයට පොයින්ටරයක් ​​ලබා දීම (මුලදී කිසිවකට සම්බන්ධ නොවේ).

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 ප්‍රතිදානය කරමු (අපට කිසිවක් කළ නොහැක). ශීර්ෂයක් නොමැති නම්, අපි එය නිර්මාණය කළ යුතුය. අපි create tree function එකට ගිහින් root එකට pointer එකක් ගන්නවා.

Node** ගස ව්‍යුහය පසුකරමින් සිටින බව සලකන්න, එය පිටපත් නොකරයි. මේකෙන් අපිට Node *tree declaration එකෙන් කරන්න බැරි දේවල් වෙනස් කරන්න හැකියාව ලැබෙනවා.

පොදුවේ ගත් කල, අපට පුතා එකතු කිරීමට අවශ්‍ය මුදුනට දර්ශකයක් සොයාගත යුතුය:

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

අපි ගහක් හදන්නේ මෙහෙමයි.

පී.එස්. මගේ පළමු ලිපිය, එබැවින් කරුණාකර දැඩි ලෙස විනිශ්චය නොකරන්න

මූලාශ්රය: www.habr.com