Bu yazıda veri yapısında ön sipariş 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.
Ön sipariş geçişinde önce kök düğüm ziyaret edilir, ardından sol alt ağaç ve ardından sağ alt ağaç ziyaret edilir. Ön sipariş geçiş süreci şu şekilde temsil edilebilir:
root → left → right
Kök düğüm, ön sipariş geçişinde her zaman ilk olarak geçilirken, sipariş sonrası geçişin son öğesidir. Ön sipariş geçişi, bir ağacın önek ifadesini elde etmek için kullanılır.
Ön sipariş geçişini gerçekleştirme adımları aşağıdaki gibi listelenmiştir:
- İlk önce kök düğümü ziyaret edin.
- Ardından sol alt ağacı ziyaret edin.
- Sonunda sağ alt ağacı ziyaret edin.
Ön sipariş geçiş tekniği şu şekildedir: Kök Sol Sağ politika. Ad ön siparişinin kendisi, önce kök düğümün geçileceğini gösteriyor.
Algoritma
Şimdi ön sipariş geçişinin algoritmasını görelim.
Step 1: Repeat Steps 2 to 4 while TREE != NULL Step 2: Write TREE -> DATA Step 3: PREORDER(TREE -> LEFT) Step 4: PREORDER(TREE -> RIGHT) [END OF LOOP] Step 5: END
Ön sipariş geçişi örneği
Şimdi ön sipariş geçişinin bir örneğini görelim. Bir örnek kullanarak ön sipariş 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 ön sipariş geçişini kullanarak geçeceğiz.
- Kök düğüm 40 ile başlayın. İlk olarak, 40 yazdır ve sonra yinelemeli olarak sol alt ağacı dolaşın.
- Şimdi sol alt ağaca gidin. Sol alt ağaç için kök düğüm 30'dur. Yazdır 30 ve 30'un sol alt ağacına doğru ilerleyin.
- 30'un sol alt ağacında 25 numaralı bir öğe vardır, yani yazdır 25 ve 25'in sol alt ağacını geç.
- 25'in sol alt ağacında 15 numaralı bir öğe vardır ve 15'in alt ağacı yoktur. Bu yüzden, 15 yazdır ve 25'in sağ alt ağacına gidin.
- 25'in sağ alt ağacında 28 vardır ve 28'in alt ağacı yoktur. Bu yüzden, yazdır 28 ve 30'un sağ alt ağacına gidin.
- 30'un sağ alt ağacında alt ağacı olmayan 35 vardır. Bu yüzden yazdır 35 ve 40'ın sağ alt ağacını geç.
- 40'ın sağ alt ağacında 50 vardır. Yazdır 50 ve 50'nin sol alt ağacını geç.
- 50'nin sol alt ağacında hiç çocuğu olmayan 45 kişi var. Bu yüzden, baskı 45 ve 50'nin sağ alt ağacını geç.
- 50'nin sağ alt ağacında 60 vardır. Yazdır 60 ve 60'ın sol alt ağacını geç.
- 60'ın sol alt ağacında çocuğu olmayan 55 var. Bu yüzden, yazdır 55 ve 60'ın sağ alt ağacına gidin.
- 60'ın sağ alt ağacında çocuğu olmayan 70 kişi var. Bu yüzden, yazdır 70 ve işlemi durdurun.
Ön sipariş geçişi tamamlandıktan sonra nihai çıktı şu şekildedir:
40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
Ön Sipariş geçişinin karmaşıklığı
Ön sipariş geçişinin zaman karmaşıklığı Açık) burada 'n' ikili ağacın boyutudur.
Oysa ön sipariş geçişinin alan karmaşıklığı Ç(1) işlev çağrıları için yığın boyutunu dikkate almazsak. Aksi takdirde, ön sipariş geçişinin alan karmaşıklığı Ah) , burada 'h' ağacın yüksekliğidir.
Ön sipariş geçişinin uygulanması
Şimdi farklı programlama dillerinde ön sipariş geçişinin uygulanmasını görelim.
Program: C dilinde ön sipariş geçişini uygulayan bir program yazın.
#include #include 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 preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; printf(' %d ', root->element); traversePreorder(root->left); traversePreorder(root->right); } 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 Preorder traversal of given binary tree is -
'); traversePreorder(root); return 0; } Çıktı
Yukarıdaki kodun yürütülmesinden sonra çıktı şu şekilde olacaktır:
Program: C++'da ön 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 preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; cout<<' '<element<left); traversepreorder(root->right); } int main() { struct node* root = createNode(39); root->left = createNode(29); root->right = createNode(49); root->left->left = createNode(24); root->left->right = createNode(34); root->left->left->left = createNode(14); root->left->left->right = createNode(27); root->right->left = createNode(44); root->right->right = createNode(59); root->right->right->left = createNode(54); root->right->right->right = createNode(69); cout<<'
the preorder traversal of given binary tree is -
'; traversepreorder(root); return 0; } < 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/25/preorder-traversal-14.webp" alt="Preorder Traversal"> <p> <strong>Program:</strong> Write a program to implement preorder 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 traversePreorder(Node node) { if (node == null) return; Console.Write(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(38); bt.root.left = new Node(28); bt.root.right = new Node(48); bt.root.left.left = new Node(23); bt.root.left.right = new Node(33); bt.root.left.left.left = new Node(13); bt.root.left.left.right = new Node(26); bt.root.right.left = new Node(43); bt.root.right.right = new Node(58); bt.root.right.right.left = new Node(53); bt.root.right.right.right = new Node(68); Console.WriteLine('Preorder traversal of given binary tree is - '); bt.traversePreorder(); } } </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/25/preorder-traversal-15.webp" alt="Preorder Traversal"> <p> <strong>Program:</strong> Write a program to implement preorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PreorderTraversal { Node root; PreorderTraversal() { root = null; } void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } public static void main(String args[]) { PreorderTraversal pt = new PreorderTraversal(); pt.root = new Node(37); pt.root.left = new Node(27); pt.root.right = new Node(47); pt.root.left.left = new Node(22); pt.root.left.right = new Node(32); pt.root.left.left.left = new Node(12); pt.root.left.left.right = new Node(25); pt.root.right.left = new Node(42); pt.root.right.right = new Node(57); pt.root.right.right.left = new Node(52); pt.root.right.right.right = new Node(67); System.out.println(); System.out.println('Preorder traversal of given binary tree is - '); pt.traversePreorder(); 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/25/preorder-traversal-16.webp" alt="Preorder 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 ön sipariş geçişini uygulayan bir program yazın.
class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PreorderTraversal { Node root; PreorderTraversal() { root = null; } void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } public static void main(String args[]) { PreorderTraversal pt = new PreorderTraversal(); pt.root = new Node(37); pt.root.left = new Node(27); pt.root.right = new Node(47); pt.root.left.left = new Node(22); pt.root.left.right = new Node(32); pt.root.left.left.left = new Node(12); pt.root.left.left.right = new Node(25); pt.root.right.left = new Node(42); pt.root.right.right = new Node(57); pt.root.right.right.left = new Node(52); pt.root.right.right.right = new Node(67); System.out.println(); System.out.println('Preorder traversal of given binary tree is - '); pt.traversePreorder(); 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.