Bu yazıda veri yapısında postorder geçişini tartışacağız.
Yığın, dizi, kuyruk vb. gibi doğrusal veri yapılarının verileri dolaşmak için yalnızca tek bir yolu vardır. Ancak hiyerarşik bir veri yapısında ağaç , verilerde geçiş yapmanın birden fazla yolu vardır. Dolayısıyla burada ağaç veri yapısını geçmenin başka bir yolunu tartışacağız; posta siparişi geçişi . Postorder geçişi, ağaçtaki düğümü ziyaret etmek için kullanılan geçiş tekniklerinden biridir. Prensibi takip ediyor LRN (Sol-sağ düğüm) . Postorder geçişi, bir ağacın postfix ifadesini elde etmek için kullanılır.
kylie jenner'ın yaşı
Sipariş sonrası geçişi gerçekleştirmek için aşağıdaki adımlar kullanılır:
- Postorder işlevini yinelemeli olarak çağırarak sol alt ağaçta gezinin.
- Postorder işlevini yinelemeli olarak çağırarak sağ alt ağaçta gezinin.
- Geçerli düğümün veri kısmına erişin.
Sipariş sonrası geçiş tekniği aşağıdakileri takip eder: Sol Sağ Kök politika. Burada Sol Sağ Kök, önce kök düğümün sol alt ağacının geçildiği, ardından sağ alt ağacın ve son olarak kök düğümün geçildiği anlamına gelir. Burada Postorder adının kendisi, ağacın kök düğümünün en sonunda geçileceğini gösteriyor.
Algoritma
Şimdi sipariş sonrası geçiş algoritmasını görelim.
Step 1: Repeat Steps 2 to 4 while TREE != NULL Step 2: POSTORDER(TREE -> LEFT) Step 3: POSTORDER(TREE -> RIGHT) Step 4: Write TREE -> DATA [END OF LOOP] Step 5: END
Posta siparişi geçişi örneği
Şimdi sipariş sonrası geçişin bir örneğini görelim. Bir örnek kullanarak sipariş sonrası geçiş sürecini anlamak daha kolay olacaktır.
Sarı renkli düğümler henüz ziyaret edilmemiştir. Şimdi yukarıdaki ağacın düğümlerini postorder geçişini kullanarak geçeceğiz.
- Burada 40 kök düğümdür. İlk önce 40'ın sol alt ağacını, yani 30'u ziyaret ederiz. 30. düğüm de sonradan sırayla geçecektir. 25, 30'un sol alt ağacıdır, dolayısıyla sonradan sırayla da geçilir. O halde 15, 25'in sol alt ağacıdır. Ancak 15'in alt ağacı yoktur, dolayısıyla 15 yazdır ve 25'in sağ alt ağacına doğru ilerleyin.
- 28, 25'in sağ alt ağacıdır ve çocuğu yoktur. Bu yüzden, yazdır 28 .
- Şimdi, yazdır 25 ve posta siparişi geçişi 25 bitti.
- Daha sonra 30'un sağ alt ağacına doğru ilerleyin. 35, 30'un sağ alt ağacıdır ve çocuğu yoktur. Bu yüzden, yazdır 35 .
- Daha sonrasında, 30 yazdır ve posta siparişi geçişi 30 bitti. Böylece verilen ikili ağacın sol alt ağacı geçilir.
- Şimdi 40'ın sağ alt ağacına, yani 50'ye doğru ilerleyin, o da sonradan sırayla hareket edecektir. 45, 50'nin sol alt ağacıdır ve çocuğu yoktur. Bu yüzden, baskı 45 ve 50'nin sağ alt ağacına doğru ilerleyin.
- 60, 50'nin sağ alt ağacıdır ve bu da sonradan sırayla geçilecektir. 55, 60'ın çocuğu olmayan sol alt ağacıdır. Bu yüzden, yazdır 55 .
- Şimdi, 70 yazdır, bu da 60'ın sağ alt ağacıdır.
- Şimdi, 60 yazdır, ve 60 için sipariş sonrası geçiş tamamlandı.
- Şimdi, 50 yazdır, ve 50 için sipariş sonrası geçiş tamamlandı.
- Sonunda, 40 yazdır, bu, verilen ikili ağacın kök düğümüdür ve 40. düğüm için sipariş sonrası geçiş tamamlanır.
Sipariş sonrası geçişten sonra elde edeceğimiz son çıktı:
geliştirici modu android nasıl kapatılır
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
Posta siparişi geçişinin karmaşıklığı
Sipariş sonrası geçişin zaman karmaşıklığı Açık) burada 'n' ikili ağacın boyutudur.
Oysa sipariş sonrası geçişin alan karmaşıklığı Ç(1) işlev çağrıları için yığın boyutunu dikkate almazsak. Aksi takdirde, sipariş sonrası geçişin alan karmaşıklığı Ah) , burada 'h' ağacın yüksekliğidir.
Posta siparişi geçişinin uygulanması
Şimdi, sipariş sonrası geçişin farklı programlama dillerinde uygulanmasını görelim.
Program: C dilinde posta siparişi geçişini uygulayan bir program yazın.
#include #include struct node { s struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in postorder*/ void traversePostorder(struct node* root) { if (root == NULL) return; traversePostorder(root->left); traversePostorder(root->right); printf(' %d ', root->element); } int main() { struct node* root = createNode(40); root->left = createNode(30); root->right = createNode(50); root->left->left = createNode(25); root->left->right = createNode(35); root->left->left->left = createNode(15); root->left->left->right = createNode(28); root->right->left = createNode(45); root->right->right = createNode(60); root->right->right->left = createNode(55); root->right->right->right = createNode(70); printf('
The Postorder traversal of given binary tree is -
'); traversePostorder(root); return 0; } Çıktı
Program: C++'ta sipariş geçişini uygulayan bir program yazın.
#include using namespace std; struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in postorder*/ void traversePostorder(struct node* root) { if (root == NULL) return; traversePostorder(root->left); traversePostorder(root->right); cout<<' '<element<left="createNode(28);" root->right = createNode(48); root->left->left = createNode(23); root->left->right = createNode(33); root->left->left->left = createNode(13); root->left->left->right = createNode(26); root->right->left = createNode(43); root->right->right = createNode(58); root->right->right->left = createNode(53); root->right->right->right = createNode(68); cout<<'
the postorder traversal of given binary tree is -
'; traversepostorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/85/postorder-traversal-14.webp" alt="Postorder Traversal"> <p> <strong>Program:</strong> Write a program to implement postorder traversal in C#.</p> <pre> using System; class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class BinaryTree { Node root; BinaryTree() { root = null; } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); Console.Write(node.value + ' '); } void traversePostorder() { traversePostorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(37); bt.root.left = new Node(27); bt.root.right = new Node(47); bt.root.left.left = new Node(22); bt.root.left.right = new Node(32); bt.root.left.left.left = new Node(12); bt.root.left.left.right = new Node(25); bt.root.right.left = new Node(42); bt.root.right.right = new Node(57); bt.root.right.right.left = new Node(52); bt.root.right.right.right = new Node(67); Console.WriteLine('The Postorder traversal of given binary tree is - '); bt.traversePostorder(); } } </pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/85/postorder-traversal-15.webp" alt="Postorder Traversal"> <p> <strong>Program:</strong> Write a program to implement postorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PostorderTraversal { Node root; PostorderTraversal() { root = null; } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + ' '); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { PostorderTraversal pt = new PostorderTraversal(); pt.root = new Node(36); pt.root.left = new Node(26); pt.root.right = new Node(46); pt.root.left.left = new Node(21); pt.root.left.right = new Node(31); pt.root.left.left.left = new Node(11); pt.root.left.left.right = new Node(24); pt.root.right.left = new Node(41); pt.root.right.right = new Node(56); pt.root.right.right.left = new Node(51); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Postorder traversal of given binary tree is - '); pt.traversePostorder(); System.out.println(); } } </pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/85/postorder-traversal-16.webp" alt="Postorder Traversal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'
></'> Çıktı
Yukarıdaki kodun yürütülmesinden sonra çıktı şu şekilde olacaktır:
Program: Java'da sipariş geçişini uygulayan bir program yazın.
bir komut arp
class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PostorderTraversal { Node root; PostorderTraversal() { root = null; } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + ' '); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { PostorderTraversal pt = new PostorderTraversal(); pt.root = new Node(36); pt.root.left = new Node(26); pt.root.right = new Node(46); pt.root.left.left = new Node(21); pt.root.left.right = new Node(31); pt.root.left.left.left = new Node(11); pt.root.left.left.right = new Node(24); pt.root.right.left = new Node(41); pt.root.right.right = new Node(56); pt.root.right.right.left = new Node(51); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Postorder traversal of given binary tree is - '); pt.traversePostorder(); System.out.println(); } } Çıktı
Yukarıdaki kodun yürütülmesinden sonra çıktı şu şekilde olacaktır:
Yani bu makaleyle ilgili. Umarım makale sizin için yararlı ve bilgilendirici olacaktır.