نمای کلی درخت، اجرا و موارد دیگر

احتمالاً بسیاری از مردم سعی کرده‌اند یک ساختار درختی کلی پیدا کنند، اما موتور جستجو فقط موارد باینری را پیدا کرده است... درخت جستجوی دودویی، پیمایش درخت باینری و بسیاری از الگوریتم‌های دیگر.
بله، در واقع، درخت عمومی هیچ جا استفاده نمی شود، پیمایش کند است، موارد استفاده کوچک است.

بنابراین، من این سوال را از خودم پرسیدم و اکنون نحوه ساخت درخت را توضیح می دهم. بنابراین، در حالت ایده آل، یک ساختار درختی کلی باید سه متغیر را ذخیره کند:

• اشاره به پسر بزرگتر
• اشاره به برادر
• داده هایی که قرار است ذخیره کنید

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

نتیجه درختی مانند زیر خواهد بود:

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 می رویم و یک اشاره گر به ریشه می گیریم.

توجه داشته باشید که Node**tree در حال عبور از ساختار است نه کپی کردن آن. این به ما توانایی تغییر چیزهایی را می دهد که نمی توانیم با اعلان Node *درخت انجام دهیم.

به طور کلی، ما باید یک اشاره گر به راس پیدا کنیم که باید son را به آن اضافه کنیم:

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