logo

TechCodeview

Inorder Traversal of Binary Tree

Kārtības šķērsošana ir definēts kā veids koku šķērsošanas tehnika kas seko modelim Left-Root-Right, lai:

  • Vispirms tiek šķērsots kreisais apakškoks
  • Pēc tam tiek šķērsots šī apakškoka saknes mezgls
  • Visbeidzot, tiek šķērsots pareizais apakškoks
Kārtības šķērsošana

Kārtības šķērsošana



Algoritms binārā koka nepareizai apbraukšanai

Inorder šķērsošanas algoritms ir parādīts šādi:

Kārtība (sakne):

  1. Izpildiet 2. līdz 4. darbību, līdz sakne != NULL
  2. Kārtība (sakne -> pa kreisi)
  3. Ierakstiet saknes -> datus
  4. Kārtot (sakne -> pa labi)
  5. Beigu cilpa

Kā darbojas Inorder Traversal of Binary Tree?

Apsveriet šādu koku:



Binārā koka piemērs

Binārā koka piemērs

Ja mēs šajā binārajā kokā veicam secīgu šķērsošanu, tad šķērsošana būs šāda:

1. darbība: Apbraukšana tiks veikta no 1 uz kreiso apakškoku, t.i., 2, pēc tam no 2 uz kreiso apakškoka sakni, t.i., 4. Tagad 4. nav kreisā apakškoka, tāpēc tas tiks apmeklēts. Tam arī nav neviena pareizā apakškoka. Tātad vairs nav jāpārvietojas no 4



4. mezgls ir apmeklēts

4. mezgls ir apmeklēts

2. darbība: Tā kā 2. kreisais apakškoks ir apmeklēts pilnībā, tagad tas nolasīja 2. mezgla datus, pirms pāriet uz labo apakškoku.

pandas loc
2. mezgls ir apmeklēts

2. mezgls ir apmeklēts

3. darbība: Tagad tiks šķērsots labais apakškoks no 2, t.i., pārejiet uz 5. mezglu. 5. mezglam nav kreisā apakškoka, tāpēc tas tiek apmeklēts, un pēc tam šķērsošana atgriežas, jo 5. mezglā nav labā apakškoka.

5. mezgls ir apmeklēts

5. mezgls ir apmeklēts

4. darbība: Tā kā ir 1. mezgla kreisais apakškoks, tiks apmeklēta pati sakne, t.i., mezgls 1.

1. mezgls ir apmeklēts

1. mezgls ir apmeklēts

5. darbība: Tiek apmeklēts 1. mezgla kreisais apakškoks un pats mezgls. Tātad tagad tiks šķērsots 1. labais apakškoks, t.i., pārejiet uz 3. mezglu. Tā kā 3. mezglam nav kreisā apakškoka, tas tiek apmeklēts.

3. mezgls ir apmeklēts

3. mezgls ir apmeklēts

6. darbība: Tiek apmeklēts mezgla 3 kreisais apakškoks un pats mezgls. Tātad pārejiet uz labo apakškoku un apmeklējiet 6. mezglu. Tagad šķērsošana beidzas, jo visi mezgli ir šķērsoti.

Tiek šķērsots viss koks

Tiek šķērsots viss koks

Tātad mezglu šķērsošanas secība ir 4 -> 2 -> 5 -> 1 -> 3 -> 6 .

Programma binārā koka Inorder Traversal ieviešanai:

Tālāk ir norādīta kārtības apbraukšanas koda ieviešana:

C++

java string Charat




// C++ program for inorder traversals> #include> using> namespace> std;> // Structure of a Binary Tree Node> struct> Node {> >int> data;> >struct> Node *left, *right;> >Node(>int> v)> >{> >data = v;> >left = right = NULL;> >}> };> // Function to print inorder traversal> void> printInorder(>struct> Node* node)> {> >if> (node == NULL)> >return>;> >// First recur on left subtree> >printInorder(node->pa kreisi);> >// Now deal with the node> >cout ' '; // Then recur on right subtree printInorder(node->pa labi); } // Draivera kods int main() { struct Node* root = new Node(1); sakne->pa kreisi = jauns mezgls(2); sakne->pa labi = jauns mezgls (3); sakne->pa kreisi->pa kreisi = jauns mezgls(4); sakne->pa kreisi->pa labi = jauns mezgls(5); sakne->labais->pa labi = jauns mezgls(6); // Funkcijas izsaukums<< 'Inorder traversal of binary tree is: '; printInorder(root); return 0; }> 

>

>

Java




// Java program for inorder traversals> import> java.util.*;> // Structure of a Binary Tree Node> class> Node {> >int> data;> >Node left, right;> >Node(>int> v)> >{> >data = v;> >left = right =>null>;> >}> }> // Main class> class> GFG {> >// Function to print inorder traversal> >public> static> void> printInorder(Node node)> >{> >if> (node ==>null>)> >return>;> >// First recur on left subtree> >printInorder(node.left);> >// Now deal with the node> >System.out.print(node.data +>' '>);> >// Then recur on right subtree> >printInorder(node.right);> >}> >// Driver code> >public> static> void> main(String[] args)> >{> >Node root =>new> Node(>1>);> >root.left =>new> Node(>2>);> >root.right =>new> Node(>3>);> >root.left.left =>new> Node(>4>);> >root.left.right =>new> Node(>5>);> >root.right.right =>new> Node(>6>);> >// Function call> >System.out.println(> >'Inorder traversal of binary tree is: '>);> >printInorder(root);> >}> }> // This code is contributed by prasad264> 

>

>

Python3


java savienojamība



# Structure of a Binary Tree Node> class> Node:> >def> __init__(>self>, v):> >self>.data>=> v> >self>.left>=> None> >self>.right>=> None> # Function to print inorder traversal> def> printInorder(node):> >if> node>is> None>:> >return> ># First recur on left subtree> >printInorder(node.left)> ># Now deal with the node> >print>(node.data, end>=>' '>)> ># Then recur on right subtree> >printInorder(node.right)> # Driver code> if> __name__>=>=> '__main__'>:> >root>=> Node(>1>)> >root.left>=> Node(>2>)> >root.right>=> Node(>3>)> >root.left.left>=> Node(>4>)> >root.left.right>=> Node(>5>)> >root.right.right>=> Node(>6>)> ># Function call> >print>(>'Inorder traversal of binary tree is:'>)> >printInorder(root)> 

>

>

C#

java virkne uz Būla




// C# program for inorder traversals> using> System;> // Structure of a Binary Tree Node> public> class> Node {> >public> int> data;> >public> Node left, right;> >public> Node(>int> v)> >{> >data = v;> >left = right =>null>;> >}> }> // Class to store and print inorder traversal> public> class> BinaryTree {> >// Function to print inorder traversal> >public> static> void> printInorder(Node node)> >{> >if> (node ==>null>)> >return>;> >// First recur on left subtree> >printInorder(node.left);> >// Now deal with the node> >Console.Write(node.data +>' '>);> >// Then recur on right subtree> >printInorder(node.right);> >}> >// Driver code> >public> static> void> Main()> >{> >Node root =>new> Node(1);> >root.left =>new> Node(2);> >root.right =>new> Node(3);> >root.left.left =>new> Node(4);> >root.left.right =>new> Node(5);> >root.right.right =>new> Node(6);> >// Function call> >Console.WriteLine(> >'Inorder traversal of binary tree is: '>);> >printInorder(root);> >}> }> 

>

>

kaudzes kārtošanas algoritms

Javascript




// JavaScript program for inorder traversals> // Structure of a Binary Tree Node> class Node {> >constructor(v) {> >this>.data = v;> >this>.left =>null>;> >this>.right =>null>;> >}> }> // Function to print inorder traversal> function> printInorder(node) {> >if> (node ===>null>) {> >return>;> >}> > >// First recur on left subtree> >printInorder(node.left);> > >// Now deal with the node> >console.log(node.data);> > >// Then recur on right subtree> >printInorder(node.right);> }> // Driver code> const root =>new> Node(1);> root.left =>new> Node(2);> root.right =>new> Node(3);> root.left.left =>new> Node(4);> root.left.right =>new> Node(5);> root.right.right =>new> Node(6);> // Function call> console.log(>'Inorder traversal of binary tree is: '>);> printInorder(root);> 

>

>

Izvade 

Inorder traversal of binary tree is: 4 2 5 1 3 6>

Paskaidrojums:

Kā darbojas pasūtījuma šķērsošana

Kā darbojas pasūtījuma šķērsošana

Sarežģītības analīze:

Laika sarežģītība: O(N), kur N ir kopējais mezglu skaits. Jo tas vismaz vienu reizi šķērso visus mezglus.
Palīgtelpa: O(1), ja netiek ņemta vērā rekursijas steka vieta. Pretējā gadījumā O(h), kur h ir koka augstums

  • Sliktākajā gadījumā, h var būt tāds pats kā N (kad koks ir šķībs koks)
  • Labākajā gadījumā, h var būt tāds pats kā mierīgs (kad koks ir pilnīgs koks)

Inorder Traversal lietošanas gadījumi:

BST (binārās meklēšanas koka) gadījumā, ja jebkurā laikā ir nepieciešams iegūt mezglus nesamazināmā secībā, labākais veids ir ieviest inorder šķērsošanu.

Saistītie raksti:

  • Koku pārvietošanās veidi
  • Iteratīva kārtības šķērsošana
  • Izveidojiet bināro koku no priekšpasūtīšanas un pasūtījuma šķērsošanas
  • Morisa šķērsošana koka šķērsošanai
  • Kārtības šķērsošana bez rekursijas