የዛፉ አጠቃላይ እይታ, አተገባበር እና ሌሎችም

ብዙ ሰዎች ምናልባት አጠቃላይ የዛፍ ግንባታ ለማግኘት ሞክረው ይሆናል፣ ነገር ግን የፍለጋ ፕሮግራሙ ሁለትዮሽ የሆኑትን ብቻ አገኘ... ሁለትዮሽ የፍለጋ ዛፍ፣ የሁለትዮሽ ዛፍ መሻገር እና ሌሎች በርካታ ስልተ ቀመሮችን አግኝቷል።
አዎን, በእርግጥ, አጠቃላይ ዛፉ በየትኛውም ቦታ ጥቅም ላይ አይውልም, መሻገሪያው ቀርፋፋ ነው, የአጠቃቀም ጉዳዮች ትንሽ ናቸው.

ስለዚህ, ይህንን ጥያቄ እራሴን ጠየኩ እና አሁን ዛፉ እንዴት እንደሚገነባ እገልጻለሁ. ስለዚህ ፣ በሐሳብ ደረጃ ፣ አጠቃላይ የዛፍ መዋቅር ሶስት ተለዋዋጮችን ማከማቸት አለበት-

• ወደ የበኩር ልጅ ጠቋሚ
• ለወንድም ጠቋሚ
• የምታስቀምጠው ውሂብ

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

ጠቋሚውን ወደ አከርካሪው እናውጅ፡-

Node *tree = NULL;

ወደ ጫፎች እንዴት እንደሚገቡ አስቀድመን መስማማት አለብን, ይህ ሁለትዮሽ ዛፍ አይደለም, እና እያንዳንዱ ጫፍ የፈለገውን ያህል ልጆች ሊኖረው ይችላል.

• + 2 (ወይም +ssbb 2) - በዛፍ ውስጥ ማስገባት (ለአጠቃላይ ዛፍ, መንገዱ በመስመሩ ይሰጣል, r ሥሩ መፍጠር ነው, s ወደ የበኩር ልጅ ሽግግር ነው, ለ ሽግግር ነው. ወንድም);

አንድ ምሳሌ ልስጥህ፡-

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

ውጤቱም እንደዚህ አይነት ዛፍ ይሆናል.

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ን እናወጣለን (ምንም ማድረግ አንችልም)። ምንም ወርድ ከሌለ, እኛ መፍጠር አለብን. ወደ የዛፉ አሠራር እንሄዳለን እና ለሥሩ ጠቋሚን እናገኛለን.

መስቀለኛ መንገድ *** ዛፍ አወቃቀሩን እያሳለፈ እንጂ እየቀዳ እንዳልሆነ ልብ ይበሉ። ይህ በመስቀለኛ መንገድ *የዛፍ መግለጫ ማድረግ የማንችላቸውን ነገሮች የመቀየር ችሎታ ይሰጠናል።

በአጠቃላይ ልጁን የምንጨምርበት የጫፍ ጫፍ ጠቋሚ ማግኘት አለብን፡-

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 ይህ የእኔ የመጀመሪያ መጣጥፍ ነው፣ ስለዚህ እባክዎን በጣም በጭካኔ አይፍረዱ

ምንጭ: hab.com