ProHoster > Blog > internet haberleri > Ağacın genel görünümü, uygulaması ve daha fazlası

Ağacın genel görünümü, uygulaması ve daha fazlası

Pek çok kişi muhtemelen genel bir ağaç yapısı bulmaya çalıştı, ancak arama motoru yalnızca ikili olanları buldu... İkili arama ağacı, ikili ağaç geçişi ve diğer birçok algoritma.
Evet, aslında genel ağaç hiçbir yerde kullanılmıyor, geçiş yavaş ve kullanım durumları küçük.

Ben de kendime bu soruyu sordum ve şimdi ağacın nasıl yapıldığını anlatacağım. Dolayısıyla ideal olarak genel bir ağaç yapısının üç değişkeni saklaması gerekir:

  • en büyük oğlunun işaretçisi
  • kardeşe işaretçi
  • saklayacağınız veriler 

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

Tepe noktasına bir işaretçi bildirelim:

Node *tree = NULL;

Köşelerin nasıl girileceğine önceden karar vermeliyiz; bu ikili bir ağaç değildir ve her köşenin arzu edildiği kadar çocuğu olabilir.

  • + 2 (veya +ssbb 2) - bir ağaca yerleştirme (genel bir ağaç için yol çizgiyle verilir, burada r bir kökün oluşturulmasıdır, s en büyük oğula geçiştir, b bir geçiştir) Bir erkek kardeş);

Bir örnek vereceğim: 

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

Sonuç şöyle bir ağaç olacak: 

1
  2
    5
  3
    6
    7
  3

İlk olarak, bir köşe ekleyen, yani köşe için bellek ayıran ve bu köşeye bir işaretçi (başlangıçta hiçbir şeye bağlı olmayan) ileten bir fonksiyon oluşturalım.

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

Ayrıca yol dizesini (+bs...) işleyen bir işlev de oluşturmanız gerekir. Çapraz geçişi her kökten başlattığımızda, eğer oluşturulmamışsa NULL çıktısı alırız (hiçbir şey yapamayız). Eğer köşe yoksa, onu yaratmalıyız. Ağaç oluşturma işlevine gidiyoruz ve köke yönelik bir işaretçi alıyoruz.

Node**tree'nin yapıyı kopyalamak yerine aktardığını unutmayın. Bu bize Node *tree bildirimiyle yapamayacağımız şeyleri değiştirme yeteneği verir.

Genel olarak, oğlunu eklememiz gereken tepe noktasına yönelik bir işaretçi bulmalıyız:

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

Bu şekilde bir ağaç oluşturuyoruz.

Not: İlk makalem, bu yüzden lütfen çok sert yargılamayın

Kaynak: habr.com

Yorum ekle