ទិដ្ឋភាពទូទៅនៃដើមឈើ ការអនុវត្ត និងច្រើនទៀត

មនុស្សជាច្រើនប្រហែលជាព្យាយាមស្វែងរកសំណង់ដើមឈើទូទៅ ប៉ុន្តែម៉ាស៊ីនស្វែងរកបានរកឃើញតែប្រភេទគោលពីរ... មែកធាងស្វែងរកគោលពីរ ការឆ្លងកាត់ដើមឈើគោលពីរ និងក្បួនដោះស្រាយជាច្រើនទៀត។
បាទ ពិតហើយ ដើមឈើទូទៅមិនត្រូវបានប្រើនៅកន្លែងណាទេ ឆ្លងកាត់យឺត ករណីប្រើប្រាស់គឺតូច។

ដូច្នេះ ខ្ញុំ​បាន​សួរ​ខ្លួន​ឯង​នូវ​សំណួរ​នេះ ហើយ​ឥឡូវ​នេះ​ខ្ញុំ​នឹង​ពន្យល់​ពី​របៀប​ដែល​ដើម​ឈើ​ត្រូវ​បាន​គេ​សាងសង់។ ដូច្នេះតាមឧត្ដមគតិ រចនាសម្ព័ន្ធមែកធាងទូទៅគួរតែរក្សាទុកអថេរបី៖

• ចង្អុលទៅកូនប្រុសច្បង
• ចង្អុលទៅបងប្រុស
• ទិន្នន័យដែលអ្នកនឹងរក្សាទុក

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

ជាដំបូង ចូរយើងបង្កើតមុខងារដែលបន្ថែម vertex មួយ ពោលគឺ បែងចែកអង្គចងចាំសម្រាប់ vertex ហើយបញ្ជូនទ្រនិចទៅចំនុចកំពូលនេះ (ដំបូងមិនភ្ជាប់ទៅអ្វីទាំងអស់)។

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

អ្នកក៏ត្រូវបង្កើតមុខងារដែលគ្រប់គ្រងខ្សែអក្សរផ្លូវ (+bs...) ។ រាល់ពេលដែលយើងចាប់ផ្តើមឆ្លងកាត់ពី root ប្រសិនបើវាមិនត្រូវបានបង្កើតទេនោះយើងបញ្ចេញ NULL (យើងមិនអាចធ្វើអ្វីបានទេ) ។ ប្រសិនបើគ្មានចំនុចកំពូលទេនោះ យើងត្រូវបង្កើតវា។ យើងចូលទៅកាន់មុខងារបង្កើតមែកធាង ហើយយកទ្រនិចទៅឫស។

ចំណាំថា Node ** មែកធាងកំពុងឆ្លងកាត់រចនាសម្ព័ន្ធ មិនមែនចម្លងវាទេ។ វាផ្តល់ឱ្យយើងនូវសមត្ថភាពក្នុងការផ្លាស់ប្តូរអ្វីដែលយើងមិនអាចធ្វើបានជាមួយនឹងការប្រកាស 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 នេះជាអត្ថបទដំបូងរបស់ខ្ញុំ ដូច្នេះសូមកុំវិនិច្ឆ័យខ្លាំងពេក

ប្រភព: www.habr.com