Tässä artikkelissa käsittelemme järjestyksen läpikulkua tietorakenteessa.
Jos haluamme kulkea solmut nousevassa järjestyksessä, käytämme inorder-läpikulkua. Seuraavat vaiheet vaaditaan tilauksen läpikulkua varten:
- Käy vasemman alipuun kaikissa solmuissa
- Vieraile juurisolmussa
- Käy oikean alipuun kaikissa solmuissa
Lineaarisilla tietorakenteilla, kuten pino, taulukko, jono jne., on vain yksi tapa kulkea datan läpi. Mutta hierarkkisissa tietorakenteissa, kuten puu, on useita tapoja kulkea dataa. Tässä käsitellään toista tapaa kulkea puutietorakenteen läpi, eli järjestysläpikulkua.
Inorder-läpikulkuun käytetään kahta lähestymistapaa:
- Tilaa läpikulku Recursionilla
- Järjestä läpikulku iteratiivisella menetelmällä
Inorder-läpikulkutekniikka seuraa Vasen juuri Oikea käytäntö. Tässä Left Root Right tarkoittaa, että juurisolmun vasen alipuu ajetaan ensin, sitten juurisolmu ja sitten juurisolmun oikea alipuu. Tässä itse järjestyksen nimi viittaa siihen, että juurisolmu tulee vasemman ja oikean alipuun väliin.
Käsittelemme järjestyksen läpikulkua sekä rekursiivisilla että iteratiivisilla tekniikoilla. Aloitetaan ensin inorder traversal käyttäen rekursio.
Järjestä läpikulku rekursion avulla
Step 1: Recursively traverse the left subtree Step 2: Now, visit the root Step 3: Traverse the right subtree recursively
Esimerkki järjestyksen läpikäymisestä
Katsotaanpa nyt esimerkkiä järjestyksen läpikäymisestä. Inorder traversal -menettely on helpompi ymmärtää esimerkin avulla.
postinkantaja
Keltaisilla solmuilla ei ole vielä käyty. Nyt kuljemme yllä olevan puun solmut inorder traversalilla.
- Tässä 40 on juurisolmu. Siirrymme vasempaan alipuuhun 40, eli 30, ja siinä on myös alipuu 25, joten siirrymme jälleen 25:n vasempaan alipuuhun, joka on 15. Tässä 15:llä ei ole alipuuta, joten tulostaa 15 ja siirry kohti sen pääsolmua, 25.
- Nyt, tulostaa 25 ja siirry 25:n oikeaan alipuuhun.
- Nyt, tulostaa 28 ja siirry 25:n juurisolmuun, joka on 30.
- Joten 30:n vasemmassa alipuussa käydään. Nyt, tulostaa 30 ja siirry oikean 30-vuotiaan lapsen luo.
- Nyt, tulostaa 35 ja siirry 30:n juurisolmuun.
- Nyt, tulosta juurisolmu 40 ja siirry sen oikeaan alipuuhun.
- Siirry nyt rekursiivisesti oikean alipuun läpi 40, joka on 50.
50:llä on alipuu, joten ohita ensin 50:n vasen alipuu, joka on 45. 45:llä ei ole lapsia, joten tulostaa 45 ja siirry sen juurisolmuun.
- Nyt tulostaa 50 ja siirry oikeaan alipuuhun 50, joka on 60.
- Käytä nyt rekursiivisesti oikean alipuun läpi 50, joka on 60. 60:lla on alipuu, joten käytä ensin vasen alipuu 60, joka on 55. 55:llä ei ole lapsia, joten tulostaa 55 ja siirry sen juurisolmuun.
- Nyt tulostaa 60 ja siirry oikeaan alipuuhun 60, joka on 70.
- Nyt tulostaa 70.
Järjestyksen läpikäynnin jälkeen lopullinen tulos on -
{15, 25, 28, 30, 35, 40, 45, 50, 55, 60, 70}
Inorderin läpikulun monimutkaisuus
Inorder-läpikulun aikamonimutkaisuus on Päällä), missä 'n' on binääripuun koko.
Sitä vastoin järjestyksen läpikulun avaruuden monimutkaisuus on O(1), jos emme ota huomioon funktiokutsujen pinon kokoa. Muuten järjestyksen läpikulun monimutkaisuus on Vai niin), missä 'h' on puun korkeus.
java arraylist lajittelu
Inorder-läpiviennin toteutus
Katsotaanpa nyt inorder traversalin toteutusta eri ohjelmointikielillä.
Ohjelmoida: Kirjoita ohjelma inorder traversalin toteuttamiseksi C-kielellä.
#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 Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); printf(' %d ', root->element); traverseInorder(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 Inorder traversal of given binary tree is -
'); traverseInorder(root); return 0; } Lähtö
Ohjelmoida: Kirjoita ohjelma inorder traversalin toteuttamiseksi C++:ssa.
#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 Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); cout<<' '<element<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 inorder traversal of given binary tree is -
'; traverseinorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-14.webp" alt="Inorder Traversal"> <p> <strong>Program:</strong> Write a program to implement inorder 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 traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); Console.Write(node.value + ' '); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(36); bt.root.left = new Node(26); bt.root.right = new Node(46); bt.root.left.left = new Node(21); bt.root.left.right = new Node(31); bt.root.left.left.left = new Node(11); bt.root.left.left.right = new Node(24); bt.root.right.left = new Node(41); bt.root.right.right = new Node(56); bt.root.right.right.left = new Node(51); bt.root.right.right.right = new Node(66); Console.WriteLine('The Inorder traversal of given binary tree is - '); bt.traverseInorder(); } } </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-15.webp" alt="Inorder Traversal"> <p> <strong>Program:</strong> Write a program to implement inorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class InorderTraversal { Node root; InorderTraversal() { root = null; } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + ' '); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } public static void main(String args[]) { InorderTraversal pt = new InorderTraversal(); pt.root = new Node(35); pt.root.left = new Node(25); pt.root.right = new Node(45); pt.root.left.left = new Node(20); pt.root.left.right = new Node(30); pt.root.left.left.left = new Node(10); pt.root.left.left.right = new Node(23); pt.root.right.left = new Node(40); pt.root.right.right = new Node(55); pt.root.right.right.left = new Node(50); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Inorder traversal of given binary tree is - '); pt.traverseInorder(); System.out.println(); } } </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-16.webp" alt="Inorder Traversal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'
></'> Lähtö
Ohjelmoida: Kirjoita ohjelma inorder traversalin toteuttamiseksi Javassa.
class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class InorderTraversal { Node root; InorderTraversal() { root = null; } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + ' '); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } public static void main(String args[]) { InorderTraversal pt = new InorderTraversal(); pt.root = new Node(35); pt.root.left = new Node(25); pt.root.right = new Node(45); pt.root.left.left = new Node(20); pt.root.left.right = new Node(30); pt.root.left.left.left = new Node(10); pt.root.left.left.right = new Node(23); pt.root.right.left = new Node(40); pt.root.right.right = new Node(55); pt.root.right.right.left = new Node(50); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Inorder traversal of given binary tree is - '); pt.traverseInorder(); System.out.println(); } } Lähtö
Eli siinä kaikki artikkelista. Toivottavasti artikkeli on hyödyllinen ja informatiivinen sinulle.