trees c basic terminology
C ++ Ağaçları Üzerine Bu Derinlemesine Eğitim, Ağaç Türlerini, Ağaç Geçiş Tekniklerini ve Resimlerle ve Örnek Programlarla Temel Terminolojiyi Açıklar:
Bu C ++ Serisinde şimdiye kadar hem statik hem de dinamik doğanın doğrusal veri yapısını gördük. Şimdi doğrusal olmayan veri yapısı ile ilerleyeceğiz. Bu kategorideki ilk veri yapısı 'Ağaçlar' dır.
Ağaçlar doğrusal olmayan hiyerarşik veri yapılarıdır. Bir ağaç, yönlendirilmiş veya yönlendirilmemiş 'kenarlar' vasıtasıyla birbirine bağlanan düğümler topluluğudur. Düğümlerden biri 'Kök düğüm' olarak adlandırılır ve kalan düğümlere alt düğümler veya kök düğümün yaprak düğümleri denir.
Genel olarak, her düğümün çok sayıda çocuğu olabilir, ancak yalnızca bir ana düğüm olabilir.
=> Tüm C ++ Eğitim Serisine Göz Atın
Bir ağacın düğümleri ya kardeş düğümler olarak adlandırılan aynı seviyededir ya da bir ebeveyn-çocuk ilişkisine sahip olabilirler. Ebeveyne aynı olan düğümler kardeş düğümlerdir.
Ne öğreneceksin:
C ++ 'da Ağaçlar
Aşağıda, çeşitli kısımlarıyla birlikte bir Örnek ağaç verilmiştir.
Ağaçlar için kullandığımız bazı temel terimlerin tanımlarına bakalım.
- Kök düğüm: Bu, ağaç hiyerarşisindeki en üstteki düğümdür. Yukarıdaki diyagramda, Düğüm A, kök düğümdür. Kök düğümün herhangi bir ebeveyni olmadığını unutmayın.
- Yaprak düğümü: Bir ağaç hiyerarşisinde en alttaki düğümdür. Yaprak düğümler, alt düğümleri olmayan düğümlerdir. Harici düğümler olarak da bilinirler. Yukarıdaki ağaçtaki E, F, G, H ve C düğümlerinin tümü yaprak düğümleridir.
- Alt ağaç: Alt ağaç, kök boş olmadığında bir düğümün çeşitli soyundan gelenleri temsil eder. Bir ağaç genellikle bir kök düğüm ve bir veya daha fazla alt ağaçtan oluşur. Yukarıdaki diyagramda, (B-E, B-F) ve (D-G, D-H) alt ağaçlardır.
- Ana düğüm: Bir alt düğüme ve üst öğeye doğru yukarı doğru bir kenara sahip olan kök düğüm dışında herhangi bir düğüm.
- Ata Düğümü: Kökten o düğüme giden bir yoldaki herhangi bir önceki düğümdür. Kökün herhangi bir atası olmadığını unutmayın. Yukarıdaki diyagramda, A ve B, E'nin atalarıdır.
- Anahtar: Bir düğümün değerini temsil eder.
- Seviye: Bir düğümün oluşumunu temsil eder. Bir kök düğüm her zaman 1. düzeydedir. Kökün alt düğümleri 2. düzeydedir, kökün torunları 3. düzeydedir vb. Genel olarak, her düğüm, üstünden daha yüksek bir seviyededir.
- Yol: Yol, ardışık kenarlardan oluşan bir dizidir. Yukarıdaki diyagramda, E'ye giden yol A => B-> E'dir.
- Derece: Bir düğümün derecesi, bir düğümün sahip olduğu çocuk sayısını gösterir. Yukarıdaki diyagramda, B ve D derecelerinin her biri 2 iken, C derecesi 0'dır.
C ++ Ağaç Türleri
Ağaç veri yapısı, aşağıdaki diyagramda gösterildiği gibi aşağıdaki alt tiplere sınıflandırılabilir.
# 1) Genel Ağaç
Genel ağaç, bir ağacın temel temsilidir. Bir düğümü ve bir veya daha fazla alt düğümü vardır. En üst düzey düğüm, yani kök düğüm 1. düzeyde mevcuttur ve diğer tüm düğümler çeşitli düzeylerde mevcut olabilir.
Aşağıdaki şekilde Genel Ağaç gösterilmektedir.
Yukarıdaki şekilde gösterildiği gibi, genel bir ağaç herhangi bir sayıda alt ağaç içerebilir. B, C ve D düğümleri 2. düzeyde bulunur ve kardeş düğümlerdir. Benzer şekilde, E, F, G ve H düğümleri de kardeş düğümlerdir.
Farklı seviyelerde bulunan düğümler bir ebeveyn-çocuk ilişkisi sergileyebilir. Yukarıdaki şekilde, B, C ve D düğümleri A'nın çocuklarıdır.E ve F düğümleri B'nin çocukları iken G ve H düğümleri D'nin çocuklarıdır.
Genel ağaç, C ++ uygulaması kullanılarak aşağıda gösterilmiştir:
mp3 müzik indir ücretsiz en iyi uygulama
#include using namespace std; //declaration for new tree node struct node { int data; struct node *left; struct node *right; }; //allocates new node struct node* newNode(int data) { // declare and allocate new node struct node* node = new struct node(); node->data = data; // Assign data to this node // Initialize left and right children as NULL node->left = NULL; node->right = NULL; return(node); } int main() { /*create root node*/ struct node *rootNode = newNode(10); cout<<'General tree created is as follows:'<data<left = newNode(20); rootNode->right = newNode(30); cout<<' '<left->data<<' '<right->data; cout<left->left = newNode(40); cout<<' '<<'/'<left->left->data; return 0; } Çıktı:
Oluşturulan genel ağaç aşağıdaki gibidir:
10
/
20 30
/
40
# 2) Ormanlar
Kök düğümü ağaçtan ve bir sonraki seviye elemanları ve kökü birleştiren kenarları sildiğimizde, aşağıda gösterildiği gibi ayrık ağaç kümeleri elde ederiz.
Windows 10'da bios nasıl güncellenir
Yukarıdaki şekilde, kök düğüm A'yı ve kök düğümü B, C ve D düğümlerine bağlayan üç kenarı silerek iki orman elde ettik.
# 3) İkili Ağaç
Her düğümün en fazla iki çocuk düğüme sahip olduğu bir ağaç veri yapısına ikili ağaç denir. İkili ağaç, en popüler ağaç veri yapısıdır ve ifade değerlendirmesi, veritabanları vb. Gibi bir dizi uygulamada kullanılır.
Aşağıdaki şekilde bir ikili ağaç gösterilmektedir.
Yukarıdaki şekilde, A, B ve D düğümlerinin her birinin iki çocuğu olduğunu görüyoruz. Her düğümün tam olarak sıfır veya iki çocuğa sahip olduğu bir ikili ağaç, tam ikili ağaç olarak adlandırılır. Bu ağaçta tek çocuğu olan düğüm yok.
Tam bir ikili ağaç, soldan sağa doldurulan en düşük seviye haricinde tamamen dolu bir ikili ağaca sahiptir. Yukarıda gösterilen ikili ağaç, tam bir ikili ağaçtır.
Aşağıda, ikili bir ağacı göstermek için basit bir program verilmiştir. Ağacın çıktısının, giriş ağacının sıralı geçiş sırası olduğuna dikkat edin.
#include using namespace std; struct bintree_node{ bintree_node *left; bintree_node *right; int data; } ; class bst{ bintree_node *root; public: bst(){ root=NULL; } int isempty() { return(root==NULL); } void insert(int item); void displayBinTree(); void printBinTree(bintree_node *); }; void bst::insert(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL){ parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bst::displayBinTree(){ printBinTree(root); } void bst::printBinTree(bintree_node *ptr){ if(ptr!=NULL){ printBinTree(ptr->left); cout<<' '<data<<' '; printBinTree(ptr->right); } } int main(){ bst b; b.insert(20); b.insert(10); b.insert(5); b.insert(15); b.insert(40); b.insert(45); b.insert(30); cout<<'Binary tree created: '< Çıktı:
İkili ağaç oluşturuldu:
5 10 15 20 30 40 45
# 4) İkili Arama Ağacı
Sıralanan ikili ağaç, ikili arama ağacı olarak adlandırılır. Bir ikili arama ağacında, soldaki düğümler kök düğümden daha küçükken, sağdaki düğümler kök düğümden büyük veya ona eşittir.
Aşağıda ikili arama ağacı örneği gösterilmektedir.
Yukarıdaki şekilde, sol düğümlerin hepsinin kök eleman olan 20'den küçük olduğunu görebiliriz. Sağ düğümler ise kök düğümden daha büyüktür. İkili arama ağacı, arama ve sıralama tekniklerinde kullanılır.
# 5) İfade Ağacı
Basit aritmetik ifadeleri değerlendirmek için kullanılan ikili ağaca ifade ağacı denir.
Aşağıda basit bir ifade ağacı gösterilmektedir.
Yukarıdaki örnek ifade ağacında, (a + b) / (a-b) ifadesini temsil ediyoruz. Yukarıdaki şekilde gösterildiği gibi, ağacın yaprak olmayan düğümleri ifadenin operatörlerini temsil ederken, yaprak düğümler işlenenleri temsil eder.
İfade ağaçları çoğunlukla cebirsel ifadeleri çözmek için kullanılır.
Ağaç Geçiş Teknikleri
Diziler, bağlantılı listeler, yığınlar, kuyruklar vb. Gibi doğrusal veri yapıları gördük. Tüm bu veri yapılarının, yapıyı yalnızca tek bir şekilde, yani doğrusal olarak kateden ortak bir geçiş tekniği vardır.
Ancak ağaçlar söz konusu olduğunda, aşağıda listelendiği gibi farklı geçiş tekniklerine sahibiz:
# 1) Sırayla: Bu geçiş tekniğinde, sol alt ağaçta daha fazla düğüm kalmayana kadar ilk önce sol alt ağaçtan geçiyoruz. Bundan sonra, kök düğümü ziyaret ederiz ve ardından sağ alt ağaçta geçilecek başka düğüm kalmayana kadar sağ alt ağaçtan geçmeye devam ederiz. Böylece, inOrder geçişinin sırası sol-> kök-> sağdır.
deneyimli için plsql röportaj soruları ve cevapları
# 2) Ön sipariş: Ön sıralı geçiş tekniği için, önce kök düğümü işleriz, sonra tüm sol alt ağacın üzerinden geçeceğiz ve son olarak sağ alt ağaçtan geçeceğiz. Bu nedenle, ön sipariş geçişinin sırası kök-> sol-> sağ şeklindedir.
# 3) Sipariş sonrası: Sipariş sonrası geçiş tekniğinde, soldaki alt ağaçtan, sonra sağ alt ağaçtan ve son olarak da kök düğümü geçiyoruz. Konumlayıcı tekniği için geçiş sırası sol-> sağ-> kök şeklindedir.
Kök düğüm n ise ve 'l' ve 'r' sırasıyla ağacın sol ve sağ düğümleriyse, ağaç geçiş algoritmaları aşağıdaki gibidir:
Sırayla (lnr) algoritması:
- İnOrder (sol-Alt ağaç) kullanarak sol alt ağacı çaprazlayın.
- Kök düğümü (n) ziyaret edin.
- İnOrder (sağ alt ağaç) kullanarak sağ alt ağacı çaprazlayın.
Ön sipariş (nlr) algoritması:
- Kök düğümü (n) ziyaret edin.
- Ön sipariş (sol alt ağaç) kullanarak sol alt ağacı çaprazlayın.
- Ön sipariş (sağ alt ağaç) kullanarak sağ alt ağacı çaprazlayın.
Postorder (lrn) algoritması:
- PostOrder (sol alt ağaç) kullanarak sol alt ağacı çaprazlayın.
- PostOrder (sağ alt ağaç) kullanarak sağ alt ağacı çaprazlayın.
- Kök düğümü (n) ziyaret edin.
Yukarıdaki geçiş teknikleri algoritmalarından, tekniklerin istenen sonucu elde etmek için belirli bir ağaca yinelemeli bir şekilde uygulanabileceğini görüyoruz.
Aşağıdaki ağacı düşünün.
Yukarıdaki geçiş tekniklerini kullanarak, yukarıdaki ağaç için geçiş sırası aşağıda verilmiştir:
- Sipariş içi geçiş: 2 3 5 6 10
- PreOrder geçiş: 6 3 2 5 10
- Sipariş sonrası geçiş: 2 5 3 10 6
Sonuç
Ağaçlar, yazılım alanındaki birçok uygulamada kullanılan doğrusal olmayan hiyerarşik bir veri yapısıdır.
Listeyi geçmek için tek bir yolu olan doğrusal veri yapılarının aksine, ağaçları çeşitli şekillerde gezebiliriz. Bu eğitimde, geçiş teknikleri ve çeşitli ağaç türleri hakkında ayrıntılı bir çalışma yaptık.
=> C ++ Yeni Başlayanlar Kılavuzuna Buradan Bir Göz Atın
Önerilen Kaynaklar
- C ++ 'da B Ağacı ve B + Ağacı Veri Yapısı
- C ++ 'da İkili Ağaç Veri Yapısı
- Yazılım Projelerinde Risk Türleri
- C ++ 'da AVL Ağacı ve Yığın Veri Yapısı
- Python Veri Türleri
- Yazılım Testi Temel Bilginizi Kontrol Etmek İçin 20 Basit Soru (Çevrimiçi Test)
- C ++ Veri Türleri
- C ++ 'da Temel Giriş / Çıkış İşlemleri
